# COMC problem of the week

A nice problem from the 2015 archive filed under week 9, dated 27th October 2015.

Define the function $t(n)$ on the nonnegative integers by $t(0)=t(1)=0, t(2)=1,$ and for $n>2$ let $t(n)$ be the smallest positive integer which does not divide $n$. Let $T(n)=t(t(t(n))).$ Find the value of $S$ if $S=T(1)+T(2)+T(3)+⋯+T(2006)$.

My answer is 1171. Here’s my solution.
It is easy to see that $t(n)=2$ for odd $n \ge 3$. Correspondingly, $T(n)=0$. Also $T(2)=0$ so we just need to sum over all even numbers from 4 to 2006.
Claim: $t(n) =p^k$, for some prime.
Pf of claim: Suppose $t(n)= ab , \gcd(a,b)=1, a, b > 1$. Since $a < ab \Rightarrow a \mid n$. Likewise we have $b\mid n \Rightarrow ab \mid n$ which is a contradiction.
Now if $t(n)$ is odd, $t(t(n))=2 \Rightarrow T(n)=1$. On the other hand if $t(n) = 2^k, k > 1$, $t(t(n))=3 \Rightarrow T(n)=2$.

So each term in the sum contributes either 1 or 2. Now $t(n)= 16$ is impossible as we would have $5, 7, 11, 13 \mid n \Rightarrow n \ge 5005$.
In the case where $t(n)= 8$ we have $4, 3, 5, 7 \mid n \Rightarrow n = 420(2k+1)$. Within the range of 4 to 2006, the only possible candidates are 420 and 1260.
Next for $t(n)= 4$ we have $2, 3 \mid n \Rightarrow n = 6(2k+1)$ and there are 167 choices in the range.
Finally, there are 1002 even numbers with a positive contribution to the sum, so
$S= 1002 + 167 + 2 = 1171$.

A verification using mathematica

This entry was posted in Number Theory, Problems. Bookmark the permalink.