Maths Olympiad Prep

Library / /341 of 462

Number theory Difficulty 6.4 National Olympiad Prove it Ireland

Determine the least positive integer kk such that 20102010 can be written as a sum of kk palindromic primes.
[A palindromic number is a positive integer—like 1636116361—whose decimal representation remains the same when its digits are reversed.]

Solution

Since 20102010 is neither a prime nor a palindromic number, k>1k > 1. Suppose k=2k = 2. Then there are two palindromic primes a,ba, b such that 2010=a+b2010 = a + b. Since 10051005 isn't prime, aba \neq b. Say a<ba < b. Then 2a<1005<b20092 \le a < 1005 < b \le 2009. But palindromic numbers b>2b > 2 ending in 22 are even, and so can't be prime. Hence, b1991b \le 1991. Also, every number of the form 1ax11ax1, where x{0,1,,9}x \in \{0, 1, \dots, 9\}, is divisible by 1111. Hence, there are no palindromic primes of this form, and so b<999b < 999. This means that 2010=a+b<2b<20002010 = a + b < 2b < 2000, which is absurd. Hence, k3k \ge 3.

If k=3k = 3, then there are three palindromic primes a,b,ca, b, c such that 2010=a+b+c2010 = a + b + c. If one of a,b,ca, b, c is even, say a=2a = 2, then 2008=b+c2008 = b + c and the argument just given shows that this can't happen. But the sum of three odd numbers is always odd, hence never equal to 20102010. Thus, k4k \ge 4.

In fact, k=4k = 4, since
2010=11+929+919+151=11+929+757+313=11+919+727+353 2010 = 11 + 929 + 919 + 151 = 11 + 929 + 757 + 313 = 11 + 919 + 727 + 353
[It can be checked that 2,3,5,7,11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,9292, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929, constitute the complete list of palindromic primes less than 20102010.]

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.