PyPE solution to PE problem 55
PyPE solution to PE problem 55
Blueprint information
- Status:
- Complete
- Approver:
- None
- Priority:
- Undefined
- Drafter:
- None
- Direction:
- Needs approval
- Assignee:
- None
- Definition:
- Approved
- Series goal:
- None
- Implementation:
- Implemented
- Milestone target:
- None
- Started by
- Scott Armitage
- Completed by
- Scott Armitage
Related branches
Related bugs
Sprints
Whiteboard
ProjectEule
===
If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.
Not all numbers produce palindromes so quickly. For example,
349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337
That is, 349 took three iterations to arrive at a palindrome.
Although no one has proved it yet, it is thought that some numbers,
like 196, never produce a palindrome. A number that never forms a
palindrome through the reverse and add process is called a Lychrel
number. Due to the theoretical nature of these numbers, and for the
purpose of this problem, we shall assume that a number is Lychrel
until proven otherwise. In addition you are given that for every
number below ten-thousand, it will either (i) become a palindrome
in less than fifty iterations, or, (ii) no one, with all the computing
power that exists, has managed so far to map it to a palindrome. In
fact, 10677 is the first number to be shown to require over fifty
iterations before producing a palindrome:
Surprisingly, there are palindromic numbers that are themselves Lychrel
numbers; the first example is 4994.
How many Lychrel numbers are there below ten-thousand?
NOTE: Wording was modified slightly on 24 April 2007 to emphasise the theoretical nature of Lychrel numbers.
Solution
--------
We employ a brute-force recursion approach. We pass each starting number
into the isLychrel function, counting how many return True. Within the
function, we keep a depth counter (which starts at 0). We are told that
a number may still be a Lychrel number even if it is palindromic, so if
our depth is 0 (we haven't started yet), we don't worry about palindromicity.
If the current depth passes the limit case (here, 50), then we return True,
otherwise we reverse and add the number, increment the depth counter, and
call isLychrel on the resulting number.
Answer
------
249