PyPE solution to PE problem 92

Registered by Scott Armitage

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

Sprints

Whiteboard

    ProjectEuler.net problem 92
    ===========================

    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

(?)

Work Items

This blueprint contains Public information 
Everyone can see this information.

Subscribers

No subscribers.