[Tutor] OverflowError in lucky numbers script

[Dave Angel]

On 01/23/2012 08:13 AM, Shreesh bhat wrote:
> I tried optimizing everything all things you guys pointed out and 
> still its
> orders of magnitude away from the expected result.
> The program should check the islucky condition between range of 
> (1,10**18)
> numbers and iterate over that 10**5 times.
> This program slows down more than 16 secs at (1,10**8) and 1 time.
> Which approach should i follow?
>
>
You said the two end points of the range were less than 10**18, but I 
didn't realize you really wanted to do the entire range, meaning first 
number is 1 and last is 10**18.  To do that 100,000 times in 10 secs 
would mean you have to process 10**12 items per CPU clock cycle.

That's so far beyond possible that it's clear another approach is 
necessary.

If you're literally going to do all the possible 18 digit numbers, then 
perhaps you should be doing a combinational approach.  For example, once 
you know whether 38 is lucky, you also know whether 83, 380, 300008000, 
and 80030 are lucky.  So you test all possible ordered strings the way 
you're doing it now, and multiply each (0 or 1) by the number of ways 
those digits could be permuted in an 18 digit space (adding zeroes in 
various places, and of course reordering numbers).

So we're looking for a bunch of lists of 18 ints, where each of the int 
is between 0 and 9, and with a further constraint that the digits 
increase in a non-strict monatonic way.  You could do that with an 18 
level nested for-loop, or you could do it with recursion.  Anyway, the 
number of total loops changes from 10**18 to something more manageable, 
basically a time roughty factorial complexity.

Once you've written that set of loops (prob. done with recursion, so it 
can do a variable-sized list), you need a function that tests "is-lucky" 
and another that calculates the number of permutations of that 
particular combinations of terms.

DaveA

-- 

DaveA