Back, Bigger, Better, Stronger

Relevant wiki: Induction - Functional Equations

(Warning: Very rough outline!)

We will prove by induction that

For $4^n \leq x \leq 3(4^n)$ , $f(x) = x+4^n$ ,

For $3(4^n) \leq x \leq 4^{n+1}$ , $f(x) = 4(x-2(4^n)$ .

We cannot have $f(1) = 1$ , as this implies $f(f(f(1))) = 1 = 4$ . Similarly, if $f(1) = 3$ , then $f(2) \geq 4, f(3) \geq 5, f(4) \geq 6, f(5) \geq 7$ , which implies $f(f(f(1))) = f(f(3)) = f(5) =4$ , creating a contradiction. This then forces $f(1) = 2, f(f(2)) = 4$ . Similarly, we can prove that if $f(2) = 4$ , then $f(4) = 4$ , implying $f(f(f(4))) = 4 = 16$ , contradiction. This then forces $f(2) = 3$ , $f(3) = 4$ . Also, $f(f(f(2))) = f(f(3)) = f(4) = 8$ .

Thus, $f(1) = 2, f(2) = 3, f(3) = 4, f(4) = 8$ . Thus we have proved the hypothesis above for $n = 0$ .

Consider when $x = 2(4^n)+a$ where $0 \leq a \leq 4^n$ . Then, we have

$f(f(f(x))) = f(f(x+4^n)) = f(4a+4^{n+1}) = 4a+2(4^{n+1})$

(The substitutions were based on the fact that $4^n \leq x \leq 3(4^n)$ and $3(4^n) \leq x + 4^n \leq 4^{n+1}$ )

This proves that $f(x) = x + 4^{n+1}$ for all $4^{n+1} \leq x \leq 2(4^{n+1})$ (The other small stuff can be proved by stating f is increasing)

Consider when $x = 3(4^n)+a$ where $0 \leq a \leq 4^n$ . Then, we have

$f(f(f(x))) = f(f(f(3(4^n) +a))) = f(f(4a+4^{n+1})) = f(4a+2(4^{n+1})) = 4a + 3(4^{n+1})$ .

(The substitutions were based on the fact that $3(4^n) \leq x \leq 3(4^{n+1})$ and the result above)

This proves that $f(x) = x + 4^{n+1}$ for all $2(4^{n+1}) \leq x \leq 3(4^{n+1})$ (The other small stuff can be proved by stating f is increasing)

Now, consider $x = a - 2(4^{n+1})$ for $3(4^{n+1}) \leq a \leq 4^{n+2}$

Now, $f(f(f(x))) = f(f(f(a - 2(4^{n+1})))) = f(f(a-4^{n+1})) = f(a) = 4(a - 2(4^{n+1}))$

(The substitutions were based on the fact that $4^{n+1} \leq a - 2(4^{n+1}) \leq a - 4^{n+1} \leq 4^{n+1}$ and the result above)

Thus, our proof is complete.We need only to substitute $x = 3171$ . Since $3(4^5) \leq 3171 \leq 4^6$ , our answer is

$\huge 4(3171 - 2(4^5)) = 4(3171 - 2048) = \boxed{4492}$

First, get the base case down. The function must go as follows:

• $f(1) = 2$
• $f(2) = 3$
• $f(3) = 4$

Then:

• $f(4) = 4 \cdot f(f(f(1))) = 8$
• $f(8) = 4 \cdot f(f(f(2))) = 12$ , and so on.

In some cases, as with f(4) and f(8), there will be "gaps." For example, using this method alone, f(5) will still be unknown. To fill the gaps, we notice that in some cases, the jump in the domain is the same as the jump the the range. In the above example, 12-8 = 8-4 = 4. This is easy to fill because we know the function is strictly increasing. Therefore $f(5)=9$ , $f(6)=10$ , and $f(7)=11$ .

Then there are the gaps where the domain jump is different than the range jump. E.g. $f(12)=16$ and $f(16)=32$ . $32-16=16$ and $16-12=4$ . We can fill these gaps as well by noticing that the second inverse is already defined. E.g. $f^{-1}(f^{-1}(13))=5$ so $f(13)=4*5=20$ . (As it so happens, these are evenly spaced by 4's.)

Thus the following Python code solves the problem:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# Base case:
fchain = {1:2, 2:3, 3:4}    # forward map 
ichain = {2:1, 3:2, 4:3}    # inverse map

# Iteration:
curx = 3
STOPHERE = 3171
while curx < STOPHERE:
    keynext = fchain[curx]
    valnext = ichain[ichain[keynext]]*4  # double inverse lookup
    fchain[keynext] = valnext
    ichain[valnext] = keynext
    if curx+1 != keynext:
        # Fill gap:
        while curx+1 <= keynext and curx < STOPHERE:
            # Determine gap size:
            if keynext-curx == valnext-fchain[curx]:
                fchain[curx+1] = fchain[curx]+1
            else:
                fchain[curx+1] = ichain[ichain[curx+1]]*4
            curx += 1
            ichain[fchain[curx]] = curx
    else:
        curx = keynext

# And the answer is:
print("Answer:" fchain[3171])

Which prints:

1

Answer: 4492

Solution in python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

"Back, Bigger, Better, Stronger"

f_=[0,2]

for k in range(len(f_), 3172):
    if k in f_ and f_.index(k) in f_:
        i = f_.index(k)
        f_.append(4*f_.index(i))
    else:
        f_.append(f_[-1] + 1)    

print(f_[-1])