Putnam 2002, Problem B-5

A palindrome in base $b$ is a positive integer whose base-$b$ digits read the same backwards and forwards; for example, 2002 is a 4-digit palindrome in base 10. Note that 200 is not a palindrome in base 10, but it is the 3-digit palindrome 242 in base 9, and 404 in base 7. Prove that there is an integer which is a 3-digit palindrome in base $b$ for at least 2002 different values of $b$.

Solution:
(due to Dan Bernstein) Put \( N = 2002! \). Then for \( d = 1, \ldots, 2002 \), the number \( N^2 \) written in base \( b = N/d - 1 \) has digits \( d^2, 2d^2, d^2 \). (Note that these really are digits because \( 2(2002)^2 < (2002!)^2 / 2002 - 1 \).)  

Note: one can also produce an integer \( N \) which has base \( b \) digits \( 1, *, 1 \) for \( n \) different values of \( b \), as follows. Choose \( c \) with \( 0 < c < 2^{1/n} \). For \( m \) a large positive integer, put \( N = 1 + (m + 1) \cdots (m + n) \lfloor cm \rfloor^{n - 2} \). For \( m \) sufficiently large, the bases  
\[ b = \frac{N - 1}{(m + i)m^{n - 2}} = \prod_{j \neq i} (m + j) \]  
for \( i = 1, \ldots, n \) will have the properties that \( N \equiv 1 \pmod{b} \) and \( b^2 < N < 2b^2 \) for \( m \) sufficiently large.  

Note (due to Russ Mann): one can also give a “nonconstructive” argument. Let \( N \) be a large positive integer. For \( b \in (N^2, N^3) \), the number of 3-digit base-\( b \) palindromes in the range \( [b^2, N^6 - 1] \) is at least  
\[ \left\lfloor \frac{N^6 - b^2}{b} \right\rfloor - 1 \geq \frac{N^6}{b^2} - b - 2, \]  
since there is a palindrome in each interval \( [kb, (k + 1)b - 1] \) for \( k = b, \ldots, b^2 - 1 \). Thus the average number of bases for which a number in \( [1, N^6 - 1] \) is at least  
\[ \frac{1}{N^6} \sum_{b=N^2 + 1}^{N^3 - 1} \left( \frac{N^6}{b^2} - b - 2 \right) \geq \log(N) - c \]  
for some constant \( c > 0 \). Take \( N \) so that the right side exceeds 2002; then at least one number in \( [1, N^6 - 1] \) is a base-\( b \) palindrome for at least 2002 values of \( b \).