Let

\(Let f(n) = \begin{cases} n^2+1 & \text{if }n\text{ is odd} \\ \dfrac{n}{2} & \text{if }n\text{ is even} \end{cases} \)

For how many integers n from 1 to 100, inclusive, does \(f ( f (\dotsb f (n) \dotsb )) = 1 \) for some number of applications of f ?

Guest Jul 7, 2021

#1

#3**0 **

if it's 12, then it's 12-6-3-10-5-26-13-170(which doesn't work) and a dead end there. You were correct on your intuition for 1, 2, 4, 8, and see if another pattern fits.

MathProblemSolver101
Jul 8, 2021

#2**0 **

We know that the last application has to be $\frac{n}{2}$ because if we used $n^2 + 1 = 1,$ that means $n^2 = 0 \Rightarrow n = 0$ though that is not allowed.

So that already removes 49 numbers(remember, 1 is allowed because $1^2 + 1 =2,$ $\frac{2}{2} = 1.$

We can further note that there has to be a $2^k$ for $k \geq 0$ so then they can go like 8-4-2-1.

Intuitively, we can only have integers that are in the form $2^k$ for some number $k.$ Here's why:

Assuming we can use odd numbers, we have $2^k = k^2 + 1.$

$2 = \sqrt[k]{k^2 + 1}$

This only works with $k=1$

Then observe this graph: https://www.desmos.com/calculator/t4hcdbhc3o

You will find that the only other solution is k = 4.125, but we specified with integers only.

Furthermore, to be evenly rooted, $k^2 + 1 = i^k$ for some integer $i.$

again, the only solution is $k=1.$

Note: $1 = 2^0.$

$2 = 2^1$

etc.

This works for 2^0 -> 2^6, so your answer is $6 -0+1 = \boxed{7}$

MathProblemSolver101 Jul 8, 2021