[Tutor] OverflowError in lucky numbers script

Alan Gauld alan.gauld at btinternet.com
Mon Jan 23 19:20:15 CET 2012

On 23/01/12 13:13, Shreesh bhat wrote:
> I tried optimizing everything all things you guys pointed out and still
> its orders of magnitude away from the expected result.

That's what I suspected. It means the fundamental approach of testing 
every number can probably never work.

> Which approach should I follow?

You will need to go back to the math.
Find a better algorithm than testing all numbers. Maybe
you can find a way to generate the numbers rather than
eliminate them?

This may be a problem somebody else has solved so a Google/Wikipedia 
search may turn up some useful algorithms?

Since it seems to be a homework type assignment it would be normal
for it to be related to your classwork. So what have you been studying 
recently that might help?

One thing that might help is to generate all the primes you need in 
advance? For example if the max number is 10**18 that implies 18 digits, 
so the the max of the squares sum can only be 18*(9*9)=1458. Rather than 
checking for primeness it might be faster to calculate all primes up to 
that value and test for inclusion in that set.
Similarly the primes for addition are max 18*9 = 162, a very small set 
of primes...

Just a random thought, I have no idea how much that would help, if at 

Alan G
Author of the Learn to Program web site

More information about the Tutor mailing list