(19 votes, average: 4.79 out of 5)
Loading...
Project Euler 92: Investigating a square of the digits number chain with a surprising property
Project Euler 92 Problem Description
Project Euler 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?
Analysis
Project Euler 92: To begin, all chains that end in 1 are called happy numbers. Any chain that contains 89 or 4 will be destined to an endless loop of calculations and forever remain unhappy. Here’s more information from Wikipedia: Happy number
It would seem a simple task to loop through all 107 numbers, calculate a chain for each one and count those that reach 89 or 4. This can, in fact, be done in less than a minute, but falls short for trying a limit of 1099 instead.
So, several optimizations can be ferreted out quickly when you realize that there are only 495 possible ways a number from 1 – 107 can have it’s digits squared and summed. The range for these numbers is 1 to 567 (92 * 7).
This means that any number in the target range of 1 – 107 can be looked up from a small table that determines ahead of time which number will be happy or not. By extension, as we learned from Kristian’s excellent Math Blog is to take similar “digited” numbers and simply add the multinomial coefficient to include all permutations of that number.
For example, 424501 is the same result of the sum of the square of the digits as is 244501, 501244, (0)12445, etc. In fact there are a total of 2520 combinations instead of 5040:
If we only check 576 numbers and calculate the multinomial coefficient instead of adding 1 by checking all 10,000,000 we save many iterations and are able to calculate much more challenging limits, especially 1099.
This problem was solved using these ideas and dynamic programming in logarithmic time.
Project Euler 92 Solution
Runs < 0.010 seconds in Python 2.7.
Use this link to get the Project Euler 92 Solution Python 2.7 source.
Afterthoughts
-
No afterthoughts yet.
Less then 2 secs to calculate 10^99:
848621012961290009929016807175952691990221212867104144408323613154869710\
828195585404753698625209870
Afterthoughts
-
No afterthoughts yet.
Thank you so much for your help, you’re so kind!!!
Whish you the best!!!
Posted by Marcelo | September 28, 2020, 8:40 AMYour code for this problem is amazing, but I can’t find the multinomial theorem applied on it, how you can get all combinations from 567 values?, well the amount of which we get all combinations is 495, from 1 to 567, but some of them return 0 combinations, I see this lines in your code but I can´t understand:
for i in range(2, L+1):
for j in range(Lc):
t[j] = sum(solutions[j – k*k] for k in range(10) if k*k <= j)
solutions = list(t)
e.g. for number 203 we get 60480 combinations (this number ends in 1).
e.g. for number 204 we get 60725 combinations (this number ends in 89).
How can I calculate this number of combinations working only with number 203 or 204 as you do in the piece of code shown before.
As you say:
only check 576 numbers and calculate the multinomial coefficient…
???????
Posted by Marcelo | September 28, 2020, 7:35 AMYour code for this problem is amazing, but I can’t find the multinomial theorem applied on it, how you can get all combinations from 567 values?, well the amount of which we get all combinations is 495, from 1 to 567, but some of them return 0 combinations, I see this lines in your code but I can´t understand:
for i in range(2, L+1):
for j in range(Lc):
t[j] = sum(solutions[j – k*k] for k in range(10) if k*k <= j)
solutions = list(t)
e.g. for number 203 we get 60480 combinations.
How can I calculate this number of combinations working only with number 203 as you do in the piece of code shown before.
Posted by Marcelo Serrano | September 28, 2020, 3:59 AMThis function you’re talking to is named Perfect digital invariant function
and there’s a extensive post in the wiki:
def pdif(x: int, p: int, b: int) -> int:
“””Perfect digital invariant function.”””
total = 0
while x > 0:
total = total + pow(x % b, p)
x = x // b
return total
Posted by Marcelo | September 27, 2020, 10:07 AMEnjoy and learned so much from this site. Please keep on posting! Thank you, Judy
Posted by Judy | September 10, 2017, 11:22 AMThank you so much for your help, you’re so kind!!!
Whish you the best!!!
Posted by Marcelo | September 28, 2020, 8:39 AM“So, several optimizations can be ferreted out quickly when you realize that there are only 495 possible ways a number from 1 – 107 can have it’s digits squared and summed. The range for these numbers is 1 to 567 (92 * 7).”
How did you reach these conclusions? Could you explain how you reached these numbers?
Posted by Wayfaring Stranger | January 5, 2014, 10:14 PMFirst, happy new year! Second, thanks for asking this question.
Ok, if we ran this program:
from Euler import sos_digits n = {sos_digits(x) for x in range(1,10000000)} print len(n), min(n), max(n)We’d get: 495 1 567
This is the length of the set of unique sum of digits squared, the minimum and maximum of that set.
1 is the minimum because the smallest sum of digits squared comes from the fist number in our list: 1.
567 is the largest sum of digits squared for the largest 7 digit number, namely, 9,999,999, which is 9^2 * 7 or 567.
Posted by Dreamer | January 6, 2014, 11:49 AMHi,
Could you share the code for sos_digits
Posted by Rajul Singh | September 10, 2015, 11:27 PMHi,
I’m wondering if you are posting more solutions. I really like your site and appreciate your contribution to those who want to learn more stuff about simple and efficient programming, like me.
There is one improvement you can make about this problem.
you used string integer casting in your program. It really takes time to run.
def calc(n): s=0 while n: s+=(n%10)**2 n=n//10 return suse a function like above instead of using n = sum(int(t)**2 for t in str(i)) can really shorten the time it costs.
Thanks,
Po
Posted by Po | February 11, 2012, 5:43 AMHi Po,
Yeah, I have to post more. I started this because projecteuler closed the comments section for older problems. They have since corrected that bad decision. But now that I have the momentum I think I’ll post more often.
Thanks for your comment and suggestion to this solution. I will incorporate the changes and give you credit for making it better.
Mike
Posted by Mike | February 23, 2012, 1:19 PM