A simple integer function

[bonanova]

There is a function f (n) on the positive integers n = 1, 2, 3, ...

It is defined solely by these properties:

1. f (n) is itself a positive integer
2. f  is strictly increasing: f (n+1) > f (n)
3. applying f twice returns the argument multiplied by 3:  f ( f (n) ) = 3n

Work out the values of f  for the first 30 integers or so: f (1),  f (2),  f (3), … , f (30).

Start, of course, with 1 and 2.

 

When you see some patterns, find f (2015).

 

Credit: Recent Math Olympiad.

[gavinksong]

ƒ(2015) = 3858

[gavinksong]

ƒ(1) = 2

ƒ(2) = 3

ƒ(3) = 6

ƒ(4) = 7

ƒ(5) = 8

ƒ(6) = 9

ƒ(7) = 12

ƒ(8) = 15

ƒ(9) = 18

ƒ(10) = 19

ƒ(11) = 20

ƒ(12) = 21

ƒ(13) = 22

ƒ(14) = 23

ƒ(15) = 24

ƒ(16) = 25

ƒ(17) = 26

ƒ(18) = 27

ƒ(19) = 30

ƒ(20) = 33

ƒ(21) = 36

ƒ(22) = 39

ƒ(23) = 42

ƒ(24) = 45

ƒ(25) = 48

ƒ(26) = 51

ƒ(27) = 54

ƒ(28) = 55

ƒ(29) = 56

ƒ(30) = 57

[bonanova]

Great job.

 

[bonanova]

Solution:

 

f (1) = 1? Can't be, since f (1) = f ( f (1) ) = 1, but it must be 3.

f (1) = 2? Could be, since f (2) would then be f ( f (1) ) = 3.

Must be. If f (1) were 3, then f (3) would also be 3. Non-increasing.

Continue to use  f ( f (n) ) = 3n:

 

1. f (1) = 2
2. f (2) = 3
3. f (3) = 6 = f ( f (2) )
4. f (4) =
5. f (5) =
6. f (6) = 9 = f ( f (3) )
7. f (7) =
8. f (8) =
9. f (9) = 18 = f ( f (6) )
10. f (10) =

 

We can fill in 4 and 5 because there are exactly two positive integers in the interval n = (3, 6),  and exactly two other positive integers between f = (6, 9).

Values for n = 7 and 8 are then found using   f ( f (n) ) = 3n:

 

1. f (1) = 2
2. f (2) = 3
3. f (3) = 6 = f ( f (2) )
4. f (4) = 7
5. f (5) = 8
6. f (6) = 9 = f ( f (3) )
7. f (7) = 12 = f ( f (4) )
8. f (8) = 15 = f ( f (5) )
9. f (9) = 18 = f ( f (6) )
10. f (10) =

 

Looking ahead to n = 12 we will have f = 21.

That constrains n = 10 and 11 to give f = 19 and 20.

Proceeding in this manner we obtain

 

1. f (1) = 2
2. f (2) = 3 = f ( f (1) )
3. f (3) = 6 = f ( f (2) )
4. f (4) = 7
5. f (5) = 8
6. f (6) = 9 = f ( f (3) )
7. f (7) = 12 = f ( f (4) )
8. f (8) = 15 = f ( f (5) ) 
9. f (9) = 18 = f ( f (6) )
10. f (10) = 19
11. f (11) = 20
12. f (12) = 21 = f ( f (7) )
13. f (13) = 22
14. f (14) = 23
15. f (15) = 24 =  f ( f (8) )
16. f (16) = 25
17. f (17) = 26
18. f (18) = 27 =  f ( f (9) )
19. f (19) = 30 =  f ( f (10) )
20. f (20) = 33 =  f ( f (11) )
21. f (21) = 36 =  f ( f (12) )
22. f (22) = 39 =  f ( f (13) )
23. f (23) = 42 =  f ( f (14) )
24. f (24) = 45 =  f ( f (15) )
25. f (25) = 48 =  f ( f (16) )
26. f (26) = 51 =  f ( f (17) )
27. f (27) = 54 =  f ( f (18) )
28. f (28) = 55
29. f (29) = 56
30. f (30) = 57 =  f ( f (19) )

 

We notice that when n is a power of 3, {1, 3, 9, 27, …}

f doubles it:  f (3^p) = 2x3^p. e.g., f (27) = 54

 

We also notice than when n is twice a power of 3, {2, 6, 18, …}

f returns the next higher power of 3: f (2x3^p) = 3^p+1. e.g. f (2x9) = 27

 

To show that these relations hold for all p, we note first that they hold for p = 0 and 1 in the table.

The inductive step is completed by noting that

 

f (3^p+1) = f ( f (2x3^p) ) = 2x3^p+1

f (2x3^p+1) = f ( f ( 3^p+1) ) = 3^p+2

 

Now the intervening numbers (black numbers in the table) need to be accounted for.

There are 3^p - 1 integers q in the interval q = (3^p, 2x3^p) and

there are 3^p - 1 integers g in the interval g = (f (3^p) = 2x3^p, 3^p+1 =  f(2x3^p)).

So there are always just enough numbers to go around.

Thus, for q in [0, 3^p],

 

f (3^p + q) = 2x3^p + q and

f (2x3^p + q) = f ( f (3^p + q) ) = 3x(3^p + q).

 

Since 3⁶ = 729, we find that 2015 = 2x3⁶ + 557.

Thus f (2015) = 3x(3⁶ + 557) = 3,858.