PyPE solution to PE problem 92
PyPE solution to PE problem 92
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
===
A number chain is created by continuously adding the square of the digits
in a number to form a new number until it has been seen before.
For example,
44 -> 32 -> 13 -> 10 -> 1 -> 1
85 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89
Therefore any chain that arrives at 1 or 89 will become stuck in an endless
loop. What is most amazing is that EVERY starting number will eventually
arrive at 1 or 89.
How many starting numbers below ten million will arrive at 89?
Solution
--------
If we specify our upper limit in terms of 10**e_limit, then our numbers of
interest will have at most e_limit digits. Assuming all of these digits are
9, the maximum value for the next number in the sequence is e_limit*9**2.
For this particular case, the second number in any of the sequences will be
less than or equal to 567, so we need only calculate the entire sequence for
these numbers.
Next we generate a list of all possible sets of e_limit digits and take one
stop along the sequence (note that any of the numbers with the same digits
as this set will arrive at the same second number in the sequence). We then
calculate how many unique numbers can be generated from the set of digits
and add that value to the running sum of 1 or 89, whichever was the ending
value for the second number in the sequence which was pre-computed in step
one.
Answer
------
8581146