[Tutor] OverflowError in lucky numbers script

[Steven D'Aprano]

On Mon, Jan 23, 2012 at 06:43:50PM +0530, Shreesh bhat wrote:

> The program should check the islucky condition between range of (1,10**18)
> numbers and iterate over that 10**5 times.

How is the islucky condition defined?

The only version I have found is based on something quite similar to 
primes, where you start by writing all the numbers down:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ...

Then delete every second number:

1   3   5   7   9    11    13    15    17    ...

Now the next lowest number is 3, so delete every third number:

1   3       7   9          13    15          ...

The next survivor is 7, so delete every seventh number, and so on. The 
first few lucky numbers by this definition are:

1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 
69, 73, 75, 79, 87, 93, 99, ... (sequence A000959 in OEIS).

(See also the Wikipedia article on Lucky Numbers.) 

Is this the same definition of "lucky number" that your puzzle uses? If 
so, you will need to think about a clever way to test which numbers are 
lucky.

Quite frankly, if this is the definition of lucky numbers you are 
supposed to use, the only possible way you can calculate all the lucky 
numbers between 1 and 10**18, not once, but 10**5 times, in sixteen 
seconds, is to find some incredibly clever algorithm. Given the 
straight-forward algorithm above, I don't believe any supercomputer on 
earth could solve the problem as given.

Perhaps I have misunderstood the problem. Is it explained on some 
website?


-- 
Steven