Lucky Numbers

  • + 0 comments

    We have

    7(x-4)+4(y+7)=7x+4y

    So if (x, y) is a solution, then (x-4,y+7) is also a solution. Hence if there is a solution then there is one with x<4. That's why you only need to test x=0..3 which runs in constant time.

    This can be extended to any equation of the form ax+by=n, you only need to test x=0..b-1.