Hosted by The Math Forum

# Putnam Problem Notes

Fall 97 Archive || MacPOW Home || Math Forum POWs || Search MacPOW

Last Saturday [Decmeber 6] saw the annual Putnam competition. Since many on my PoW list do work on the Putnam problems, I am sending out this non-PoW mailing. The problems were nicely interesting, and B-5 especially caught my interest. This was the problem:

B-5: Let aj denote a tower of j 2s: 222.·'2. Prove that an = an-1 (mod n).

I was able to prove it using little more than Euler's formula that 2Phi(n) = 1 (mod n) when n is odd.

My proof was constructive in that it allowed me to write some Mathematica code to get, given j and m, the value of Mod[a_j, m]. It is always nice to see how to deal with such ridiculously large integers. And, naturally, computations lead to further questions, in particular, where does the congruence stop? Examples:

• j = 2: aj = 4 and aj-1 = 2. They are congruent mod 1 and 2, but not 3 (so B-5 as stated is best possible).
• j = 3: aj = 16 and aj-1 = 4; they are congruent mod 1, 2, 3, and 4, but not 5.
• j = 4: First failure at modulus 11.
• j = 5: First failure at mod 23 (= 2*11 + 1)
• j = 6: First failure at mod 47 (= 2*47 + 1)
• j = 7: First failure at mod 283 (= 6*47 + 1)
• j = 8: First (I think) failure is at 1699 (= 6*1699+1)
• j = 9: First (I think) failure is at 1699*360 + 1
There seems to be some pattern here. In particular, it looks like B-5 can be strengthened at least to
If n > 3, then an = an-1 (mod k) for each k = 1, 2, 3, ..., n, n+1.
Now, I have to admit it is possible my code is incorrect, so these observations should be taken with a grain of salt.

Challenges:

1. Prove the assertion about n+1 above. (This might make a nice journal submission if true; on the other hand, it might follow from the solution of B-5; I will have to look at that carefully. Right now my solution proves:
aj = aj-1 (mod n) whenever j > n.
And the present question is whether this can be extended to j > n - 1.)

2. Say somethimg intelligent (either conjecture or proof) about the least k for which aj and aj-1 are not congruent mod k.

More...I think I can define a simple TowerMod function. Recall that PowerMod[a,n,m] gives an mod m. My TowerMod gives aaa.·'a (n terms) mod m.

This is still work-in-progress. As usual, I have more questions than answers.

I would love some independent confirmation of these computations so that I can know my code is correct.