[Tutor] OverflowError in lucky numbers script

[Walter Prins]

Hi

On 23 January 2012 22:55, Steven D'Aprano <steve at pearwood.info> wrote:
>
>
> > >Can i work around that way in python or should i come up with a new
> > >algorithm?
> >
> > You definitely need a fundamentally different algorithm.
>
> I expect that this is some question from one of those annoying
> websites that offer extremely advanced mathematics puzzles disguised as
> a programming challenge. (Well I find them annoying. The answer almost
> always turns out to be something which took a genius of the level of
> Euler or Gauss to discover, and they expect you to come up with the
> answer on your own.)
>

The OP previously posted the question, and having reread it I think
perhaps he's too fixated on the maximum possible range in the
spec/question which gives rise to an practically impossible
computational burden.   To be precise, I think trying to feed A=1 and
B=10^18 seems to me to be asinine given that the the example test
cases given in the problem statement uses values of A and B that are
a) relatively small and b) quite close together.  That therefore gives
me the impression that being able to calculate all the answers for the
whole 1...10^18 range is rather not expected.  (The very fact that you
need to specify a sub-range within which to calculate the lucky
numbers in, implies that it's not expected, actually.)

Anyway, for reference I post the original question again:

> *Lucky Numbers*
> A number is called lucky if the sum of its digits, as well as the sum of
> the squares of its digits is a prime number. How many numbers between A
> and B are lucky?
> Input:
> The first line contains the number of test cases T. Each of the next T
> lines contains two integers, A and B.
> Output:
> Output T lines, one for each case containing the required answer for the
> corresponding case.
>
> Constraints:
> 1 <= T <= 10000
> 1 <= A <= B <= 10^18
> Sample Input:
> 2
> 1 20
> 120 130
> Sample Output:
> 4
> 1
> Explanation:
> For the first case, the lucky numbers are 11, 12, 14, 16.
> For the second case, the only lucky number is 120.

Walter