Crazy Collapsible Collatz

A sensible approach to take in this problem is to generate all the possible numbers that can give 5 as the final result, and see which one is minimal. The resulting binary tree would have $2^7$ nodes in the worst case, but as we will see soon, this number is in effect much smaller.

Let's see how we can define the possible inverse of this function for an arbitrary $n$ . Since from an odd n we always get an even $f(n)$ and from an even $n$ we can get either an even and an odd $f(n)$ , it easily follows that $f^{-1}(n) = 2n$ always, or if $n$ is even and $(n-1)$ is divisible by 3, then $f^{-1}(n)$ can also be $\frac{n-1}{3}$ . [Note: The inverse of a function need not be a [function](http://blog.brilliant.org/2012/12/10/functions-definitions-and-terminology/). - Calvin]

If we were to represent this inverse function being repeatedly applied, starting from 5, as a tree, we can notice that there are only 21 nodes up to depth 7 (full tree is depicted in the problem), and five leaves: 17, 96, 104, 106 and 640. The smallest out of them is 17, hence this is the final solution.

When applying the inverse function of $f(n)$ , we note that we can reduce it to $\frac{n-1}{3}$ only if $n \equiv 4 \pmod{6}$ . This means that we can come up with a list of possibilities: One iteration: 10 Two iterations: 20, 3 Three iterations: 40, 6 Four: 13, 80, 12 Five: 26, 100, 24 Six: 52, 53, 320, 48 Seven: 17, 104, 106, 640, 96 The smallest of these is $\boxed{17}$ which is our answer.

Let $S_i$ be the set of integers $n$ such that $f^{(i)}(n)=5$ .

For $i=1$ to $7$ , we find $S_{i}$ by asking what integers $n$ there are such that $f(n)$ is in $S_{i-1}$ .

To do so, we note that each integer in $S_i$ must be either even and expressible as $2n$ or odd and expressible as $\frac{n-1}{3}$ for some integer $n$ in $S_{i-1}$ .

In this manner, we can for each iteration use the results obtained from the previous iteration to obtain values for the current iteration:

$S_0=\{5\}$
$S_1=\{10\}$
$S_2=\{20,3\}$
$S_3=\{40,6\}$
$S_4=\{80,13,12\}$
$S_5=\{160,26,24\}$
$S_6=\{320,53,52,48\}$
$S_7=\{640,106,104,17,96\}$

The smallest integer in $S_7$ is 17.

Given: f^7(n) = 5

f^x (n) = \frac {f^(x-1) (n)}{2} or 3 \cdot [f^(x-1) (n)] + 1

=> f^6 (n) = 20

=> f^5 (n) = 20 or 3

=> f^4 (n) = 40 or 6

=> f^3 (n) = 13 or 80 or 12

=> f^2 (n) = 4 or 26 or 160 or 24 ----> Here 4 is not possible as 4 is even which yields f^3 (n) = 2

=> f^2 (n) = 26 or 160 or 24

=> f (n) = 52 or 53 or 320 or 48

=> n = 17 or 104 or 106 or 640 or 96

Among these, least possible value is 17

Our goal is to find the seventh [7th] step in our process in order to find the possible values of n that will satisfy the given situation. The only way we can get 5 is from f(10) [1st] . We can get 10 from:

A) f(3)[2nd]. We can get 3 from f(6) [3rd]. We can get 6 from f(12) [4th]. We can get 12 from f(24) [5th]. We can get 24 from f(48) [6th]. We can get 48 from f(96) [7th].

B) f(20) [2nd], and 20 from f(40) [3rd]. We can get 40 from:

(a) f(80) [4th]. We can get 80 from f(160) [5th]. We can get 160 from:
    (i) f(320) [6th] . We can only get 320 from f(640) [7th]
    (ii)f(53) [6th]. We can only get 53 from f(106) [7th]


b) 13(4th). We can get 13 only from f(26) [5th].  We can get 26 from            f(52) [6th]. 
We can get 52 from both f(17) [7th] and f(104) [7th]

The possible values of n are 96, 640, 106, 17, and 104. So the smallest possible value of n is 17.

We show that $f^{(7)}(17)=5$ . It is not hard to see hat $f^{(k)}(17)=52,26,13,40,20,10,5$ for $k=1,2,3,4,5,6,7.$ We now show that $n\ge 17$ if $f^{(7)}(n)=5.$ (Note: if $b=3a+1$ we write $a=\frac{b-1}{3}.)$ So for $f(n)\equiv 4\pmod 6$ , $n=2f(n)$ or $n=\frac {f(n)-1}{3}$ and if $f(n)\not\equiv 4\pmod 6$ , $n=2f(n)$ .

First, if $f(n)=3n+1$ for $n$ odd, write $n=2a+1, a\in\mathbb N_{0}$ yields that $f(n)=6a+4\equiv 4\pmod {6}$ . So if $b\not\equiv 4\pmod {6}$ and $f(a)=b,$ then $b=\frac{a}{2}$ and $a$ even.

Now, if $f^{(7)}(n)=f(f^{(6)}(n))=5,$ since $5\not\equiv 4\pmod {6},$ $f^{(6)}(n)=2(5)=10$ . From this, we deduce that $f^{(5)}(n)=2(10)=20$ or $f^{(5)}(n)=\frac{10-1}{3}=3$ . Note that, if $3\mid f(a)$ for some $a$ , then by claim above we know that $f(a)=\frac{a}{2}$ and thus $3\mid a$ . Therefore, if $f^{(5)}(n)=3$ then we know that $f^{(k)}(n)=6,12,24,48,96$ for $k=4,3,2,1,0.$ Hence $n=96>17.$ It suffices to work on case where $f^{(5)}(n)=20$ now.

Now, since $f^{(5)}(n)=20\equiv 2\not\equiv 4\pmod {6},$ $f^{(4)}(n)=2(20)=40$ Thus we have: $f^{(3)}(n)=2(40)=80$ or $f^{(3)}(n)=\frac{40-1}{3}=13$ . We have: $13\equiv 1\not\equiv 4\pmod {6}$ and $80\equiv 2\not\equiv 4\pmod {6}.$ So if $f^{(3)}(n)=80,$ $f^{(2)}(n)=2(80)=160$ and if $f^{(3)}(n)=13,$ $f^{(2)}(n)=2(13)=26.$

If $f^{(2)}(n)=160, f(n)=160\times 2=320$ or $f(n)=\frac{160-1}{3}=53$ . Since $320\not\equiv 4\pmod {6}$ , if $f(n)=320$ then $n=2(320)=640>17$ . Since $53\not\equiv 4\pmod {6}$ , if $f(n)=53, n=2(53)=106>17.$

If $f^{(2)}(n)=26$ , since $26\not\equiv 4\pmod {6}$ , $f(n)=2(26)=52$ , hence $n=2(52)=104>17$ or $n=\frac{52-1}{3}=17.$ Since we have covered all the cases, we have proven that $n\ge 17$ , Q.E.D.

The algorithm I used was pretty straight forward but Im sure its inefficient for values far greater than 7. Here is what I did. I built a tree with 5 at the top. For each branch I double it and add it to a knew branch or if it yields a remainder of 1 when divided by 3, I subtract one and divide it by three and add it to a new branch.Practically the inverse of what the collatz does. I do this until I either reach one. I stop when have build a tree which extends to 7 branches vertically downwards. Using this method,I got the following tree. (Its split up because I dont know how to draw a tree here) 5-10-20-40-80-160-53-106 5-10-20-40-80-160-320-640 5-10-20-40-13- 26 - 52-17 5-10-3 - 6 - 12 - 24 - 48 - 96

If n is even, f(n) can be even or odd. But if n is odd, f(n) must be even (n1 (mod 2)  f(n)=3n+13 1+1=40 (mod 2)). Since f7(n)=5 is odd, f6(n) must be even. So, f6(n)=2 f7(n)=10. Now, f6(n) is even, so we have two cases for f5(n): 1. f5(n)=2* f6(n)=20. f4(n) can be 2* f5(n)=40, or it can be (f5(n)-1)/3=19/3. Since 19/3 isn’t an integer number, f4(n)=40. Again, we have two cases: 1.1. f3(n)=2* f4(n)=80 Since (f3(n)-1)/3=79/3 isn’t an integer number, f2(n)= 2* f3(n)=160. 1.1.1. f(n)= 2* f2(n)=320 n=(f(n)-1)/3=319/3 isn’t an integer number  n=640 1.1.2. f(n)= (f2(n)-1)/3=53  n=106 1.2. f3(n)=(f4(n)-1)/3=13 f2(n)= 2* f3(n)=26 f(n)=(f2(n)-1)/3=25/3 isn’t an integer number  f(n)= 2* f2(n)=52  n=104 or n=17 2. f5(n)= (f6(n)-1)/3=3 f4(n)= 2* f5(n)=6 f3(n)=12 f2(n)=24 f(n)=48  n=96

n{640, 106, 104, 17, 96} The smallest value of n is 17.

5 can be obtained from an even number only (since 3n+1 = 5 yields no integral value for n)

Hence, (n/2)=5 which yields n = 10. (7th step)

[Here, 7th step indicates the final step when the value of f (f (f (f (f (f(x))))) is put in the expression of f(x) to get 5]

Now, 10 can be obtained either from an odd number or an even number.

Case I: 10 is obtained from an even number.

Hence, (n/2) = 10, which yields n = 20 (6th step)

20 can be obtained from an even number only (since 3n+1 = 20 yields no integral value for n)

Hence, (n/2)=20 which yields n = 40 (5th step)

40 can be obtained from an even number or an odd number.

Sub case I: 40 is obtained from an odd number.

Hence, 3n+1 =40 which yields n =13 (4th step)

13 can be obtained from an even number only (since 3n+1 =13 yields an even integral value for n)

Hence, (n/2)=13 which yields n =26 (3th step)

26 can be obtained from an even number only (since 3n+1 =26 yields no integral value for n)

Hence, (n/2)=26 which yields n =52 (2nd step)

52 can be obtained from an even number or an odd number.

When it is even, (n/2)=52 which yields n =104 (1st step)

When it is odd, 3n+1 = 52 which yields n =17 (1st step)

Since, 17<104, we take n=17 in this case.

Sub case II: 40 is obtained from an even number.

Hence, (n/2)=40 which yields n=80 (4th step)

80 can be obtained from an even number only (since 3n+1 =80 yields no integral value for n)

Hence, (n/2)=80 which yields n=160 (3th step)

Since it is a very large value, we stop the process here as it can be seen that it would yield quite a large value for n for the 1st step.

Case II: 5 is obtained from an odd number.

Similar methods like the above ones can be adopted to find n.

In this case, n comes out to be 96.

Since 17<96,

The final answer is 17.

(i) n is an odd number, w.l.o.g, we'll assume that $x = 2k + 1$ . Hence f(x) = 6k + 2 = 2. (3k + 1), resulted in even number (divisible by 2) and $f(x) \equiv 1 \pmod{3}$

(ii) otherwise, n is an even number, and w.l.o.g, we'll assume that $x = 2k$ . Hence f(x) = k, for k = 1,2,3,...

We're simply getting its inverse by, that: $f^{-1}(n) \begin{cases} \frac {n-1}{3} , n \mbox{ even and } n \equiv 1\pmod{3} \\ 2n , n \mbox{ all positive integers} \\ \end{cases}$

Note that, for a case which first equality holds, it can be easily seen that second equality also holds (two conditions, multiple cases).

Now, we'll find the result of its $f^{-7}(n) .$

First : 5 (only second condition holds) -> 10

Second : 10 (both first and second condition hold) -> 3 or 20 Note that, $3 \equiv 0 \pmod{3}$ , which infer that $2^{n} * 3 \equiv 0 \pmod{3}$ . Hence, from this case, we'll get $f^{-7}(n) = 2^{5} * 3 =$ 96 .

Third : 20 (Only second condition holds) -> 40

Fourth : 40 (both first and second condition hold) -> 13 or 80 We'll divide it into two cases, 13 and 80.

(i) Case : 80

Fifth : 80 (Only second condition holds) -> 160

Sixth : 160 (both first and second condition hold) -> 53 and 320

Seventh: 53 -> 106 or 320 -> 640 . Both of them are greater than 96 .

(ii) Case : 13

Fifth : 13 (Only second condition holds) -> 26

Sixth : 26 (Only second condition holds) -> 52

Sixth : 52 (both first and second condition hold) -> 17 and 104 Since 17 < 96 and 96 < 104 , the most minimum value of n for $f^{-7}(n)$ is 17 .

A number $n$ may have up to 2 pre images. One of the preimage is $2n$ , and the other pre image is $\frac {n-1}{3}$ , if this number is odd.

The set of pre images of 5 is $\{ 10\}$ .
The set of pre images of $\{ 10\}$ is $\{ 3, 20\}$ .
The set of pre images of $\{ 3, 20\}$ is $\{ 6, 40 \}$ .
The set of pre images of $\{ 6, 40\}$ is $\{12, 13, 80\}$ .
The set of pre images of $\{12, 13, 80\}$ is $\{ 24, 26, 160 \}$ .
The set of pre images of $\{ 24, 26, 160 \}$ is $\{ 48, 52, 53, 320 \}$ .
The set of pre images of $\{ 48, 52, 53, 320 \}$ is $\{ 96, 17, 104, 106, 640 \}$ .

Hence, the smallest value of $n$ is 17.

We know that once the function is applied 7 times, it gives 5, so we have to find the original number, which is the function when applied 0 times:

F₍₇₎(n) = 5; (3n + 1 = 5) has no integer solution, so F₆(n) is even, multiply by 2.

F₍₆₎(n) = 10; (3n + 1 = 10) has a solution, but using the value, n = 3, leads into a 3-10-3-10 cycle which does not lead to 5, so F₅(n) is even.

F₍₅₎(n) = 20; (3n + 1 = 20) has no integer solution, so F₄(n) is even.

F₍₄₎(n) = 40; (3n + 1 = 40) has a solution, n = 13, so F₃(n) is odd.

F₍₃₎(n) = 13; (3n + 1 = 13) has a solution, n = 4, but this leads to a 1-2-4 cycle which will never reach 5, so F₂(n) is even.

F₍₂₎(n) = 26; (3n + 1 = 26) has no integer solution so F₁(n) is even.

F₍₁₎(n) = 52; (3n + 1 = 26) has an integer solution (n=17), so F₀(n) (or just n) is odd.

F₍₀₎(n) = n = 17, which is the answer.

This problem can be solved by working backwards starting from $f^7(n)=5$ :

Because $f^7(n)=5$ , by taking the inverses of the two functions we can find the value of n. When the result is even, $g^{-1}(m)=2m$ , for which because $2m$ is multiplied by $2$ the inverse will be true no matter what the actual outcome is. On the other hand, when the result is odd, $g^{-1}(m)=\frac{m-1}{3}$ , which can give fractions or even numbers as results, which null its effect. We will be checking for the odd inverse formula as we move on. For the rest of this solution, I will be using $g_1$ to indicate the even inverse and $g_2$ to indicate the odd inverse.

Because $f^7(n)=5$ , $g_1(f^7(n))=f^6(n)=10, g_2(f^7(n))=f^6(n)=4/3$ . The second solution is a fraction, not an integer, and will be disregarded.

$g_1(f^6(n))=f^5(n)=20, g_2(f^6(n))=f^5(n)=3$ .

Notice that we received two valid answers at this point. I won't go through all of the inverses again, but following $f^5(n)=3$ , we get that $f^4(n)=6, f^3(n)=12, f^2(n)=24, f(n)=48, n=96$ . This is one solution, but let's look at the other branch and see what we get.

Following $f^5(n)=20$ , we get $f^4(n)=40, g_1(f^4(n))=f^3(n)=80, g_2(f^4(n))=f^3(n)=13$ . Following the second chain, we start with $f^3(n)=13, g_1(f^3(n))=f^2(n)=26, g_2(f^3(n))=f^2(n)=4$ . However, 4 is not odd and thus is not a correct inverse. Continuing, $f^2(n)=26, f(n)=52, g_1(f(n))=n=106, g_2(f(n))=\boxed{n=17}$ .

At this point it's much easier to confirm by testing numbers under 17, since these are relatively small. You can also work out the other chains, and the final answer you get is $\boxed{n=17}$ .