COMC problem of the week

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

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

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

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

A verification using mathematica

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

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>