Le Monde puzzle [#1104]
A palindromic Le Monde mathematical puzzle:
In a monetary system where all palindromic amounts between 1 and 10⁸ have a coin, find the numbers less than 10³ that cannot be paid with less than three coins. Find if 20,191,104 can be paid with two coins. Similarly, find if 11,042,019 can be paid with two or three coins.
Which can be solved in a few lines of R code:
coin=sort(c(1:9,(1:9)*11,outer(1:9*101,(0:9)*10,"+"))) amounz=sort(unique(c(coin,as.vector(outer(coin,coin,"+"))))) amounz=amounz[amounz<1e3]
and produces 9 amounts that cannot be paid with one or two coins.
21 32 43 54 65 76 87 98 201
It is also easy to check that three coins are enough to cover all amounts below 10³. For the second question, starting with n¹=20,188,102, a simple downward search of palindromic pairs (n¹,n²) such that n¹+n²=20,188,102 led to n¹=16,755,761 and n²=3,435,343. And starting with 11,033,011, the same search does not produce any solution, while there are three coins such that n¹+n²+n³=11,042,019, for instance n¹=11,022,011, n²=20,002, and n³=6.
Xi'an's Og 
June 19, 2019 at 5:04 am
I tried to write the code to get the 10 amounts, but can’t get it to work.
Here’s what I tried:
amounz[!(seq(1:999) %in% amounz)]
result:
22 34 46 58 70 82 94 106 210
That does not look right.
June 19, 2019 at 8:31 am
Thanks! There is a slight mistake in your R code as it should have been
(1:999)[!(1:999)%in%amounz]
which returns the right sequence (see my update).
June 18, 2019 at 9:10 am
Cilleruelo, Luca & Baxter (2016): “Every positive integer is a sum of three palindromes”. https://arxiv.org/abs/1602.06208 (proven in base 10, and also in any base ≥5).