Project Euler — Problem 55 Solution

Problem

If we take 47, reverse and add, 47 + 74 = 121, which is palin­dromic.

Not all num­bers pro­duce palin­dromes so quick­ly. For exam­ple,

349 + 943 = 1292,

1292 + 2921 = 4213

4213 + 3124 = 7337

That is, 349 took three iter­a­tions to arrive at a palin­drome.

Although no one has proved it yet, it is thought that some num­bers, like 196, nev­er pro­duce a palin­drome. A num­ber that nev­er forms a palin­drome through the reverse and add process is called a Lychrel num­ber. Due to the the­o­ret­i­cal nature of these num­bers, and for the pur­pose of this prob­lem, we shall assume that a num­ber is Lychrel until proven oth­er­wise. In addi­tion you are giv­en that for every num­ber below ten-thou­sand, it will either (i) become a palin­drome in less than fifty iter­a­tions, or, (ii) no one, with all the com­put­ing pow­er that exists, has man­aged so far to map it to a palin­drome. In fact, 10677 is the first num­ber to be shown to require over fifty iter­a­tions before pro­duc­ing a palin­drome: 4668731596684224866951378664 (53 iter­a­tions, 28-dig­its).

Sur­pris­ing­ly, there are palin­dromic num­bers that are them­selves Lychrel num­bers; the first exam­ple is 4994.

How many Lychrel num­bers are there below ten-thou­sand?

NOTE: Word­ing was mod­i­fied slight­ly on 24 April 2007 to empha­sise the the­o­ret­i­cal nature of Lychrel num­bers.

Solution