[Tutor] OverflowError in lucky numbers script

[Dave Angel]

On 01/23/2012 05:55 PM, Steven D'Aprano wrote:
> On Mon, Jan 23, 2012 at 10:01:33PM +0000, Alan Gauld wrote:
>
>> Just to be clear this has nothing to do with Python. It doesn't matter
>> what programming language you choose there is not a PC on Earth that can
>> do what you want using the technique you are using in 16 seconds.
> I don't believe that you could do it with the fastest supercomputer on
> earth. If you have to test 10**18 numbers in 16/10**5 seconds, that
> gives you less than 0.0000000000002 nanoseconds per test.
>
> This isn't a question of tweaking the code to make it run faster, you
> need a fundamentally different approach to the problem, as Alan says.
> Either that, or we have completely misunderstood the constraints of the
> puzzle.
I gave such an example approach, at 1:42 (actually, much earlier, but I 
forgot to change my send-from field, so Tutor bounced my message).  You 
can search for the message using the string  "to do all the possible 18 
digit numbers".

I can solve the problem of finding how many lucky numbers in the entire 
range 1 through 10**18 in a reasonable time.  I haven't coded the entire 
algorithm, but most of it exists, and takes 97 seconds for generating 
and testing for luckiness the 4,686,824 possible distinct sets of 
digits.  Thus my outer loop goes around 4.6 million times, rather than 
10**18 times.  Incidentally, I made the 18 an argument to main(), so 
it's easy to test on smaller values.

What I generate are all possible lists of digits, all of length 18,  in 
which the digits are in sorted order.  All that remains is multiplying 
the 1 or 0 for each of these 4.7 million lists by a 
number-of-permutations figure, which shouldn't be too hard to get.  It 
would trivially be 18 factorial, except that there are variable numbers 
of duplicates among those 18 digits.  Anyway, I claim that it won't add 
more than a few percent to finish the task.  Call it 100 seconds.  lots 
more than the 16 seconds originally specified for doing it 10,000 
times.  There are undoubtedly ways to optimize my code;  I made no real 
attempt to be optimal.  I just was worried about the algorithm.

Only catch is that we might not want all 10**18 numbers.  If we want a 
few million of them, all around 10**17, the original approach will work 
fine.  And if we want them all, my approach will work.  I haven't come 
up with a way to generalize either for things like "solve it for the 
range 1234567890123456 through twice that value".


-- 

DaveA