CODEWITHSUNDEEP
pythonfor-loop
Hanming Zeng
Hanming Zeng

Reputation: 367

Lucky Number Finder

All right, so I was helping my niece doing her elementary school fun math problem. The question is like this: A number is a lucky number given that starting from the third digit, every digit is the absolute difference of the previous two digits. Also, a lucky number cannot have duplicate digits. For example, 132,871, 54132 are lucky numbers but 8918 is not because it has duplicate "8". So the question is asking what is the largest lucky number.. I'm really bad at math.. but I am intrigued by this problem and I wrote a program for it: #lucky number

def is_lucky_number(n):
    n = str(n)
    islucky = False
    if len(n)>=3:
        for x in range(2,len(n)):
            if int(n[x]) != abs(int(n[x-1])-int(n[x-2])):
                return False
            else:
                islucky = True
    return islucky

def no_duplicate(n):
    n = str(n)
    for i in range(len(n)):
        sliced = n[i+1:]
        if n[i] in sliced:
            return False
    return True


for i in range(98176,9999999999):  #98176 is the largest lucky number I can think of
    if no_duplicate(i) == False:
        continue
    if is_lucky_number(i):
        print(i)

print("done")

The program is definitely correct but it's running forever... "done" never gets printed. Any ideas on solving this with a more efficient approach?

Upvotes: 1

Views: 1996

Answers (2)

dawg
dawg

Reputation: 104062

'Largest' is the max

You can start with all two digit numbers starting with 10 through 99 -- range(10, 100)

Then loop through the list adding a new digit each time that the the difference between the last two digits and eliminating those that are not lucky. When adding a digit results in no lucky numbers at all, we are done:

li=range(10,100)    
while True:
    new_li=[]
    for e in li:
        s=str(e)
        n=abs(int(s[-2])-int(s[-1]))
        if len(set(s+str(n)))==len(s)+1:
            new_li.append(int(s+str(n)))
    if new_li:
        li=new_li
    else:
        print max(li)
        break

prints 954132

If you want all the lucky numbers, add them to a list and then take the max of that:

# all two digit numbers that are not repeated digits
li=[e for e in range(10,100) if len(set(str(e)))==2]   
lucky=[]
while True:
    new_li=[]
    for e in li:
        s=str(e)
        ns=str(abs(int(s[-2])-int(s[-1])))
        if ns not in s:
            new_li.append(int(s+ns))
    if new_li:
        li=new_li
        lucky.extend(new_li)
    else:
        break   

print lucky     
print max(lucky)

Prints:

[132, 143, 154, 165, 176, 187, 198, 231, 253, 264, 275, 286, 297, 312, 321, 341, 352, 374, 385, 396, 413, 431, 451, 462, 473, 495, 514, 523, 532, 541, 561, 572, 583, 594, 615, 624, 642, 651, 671, 682, 693, 716, 725, 734, 743, 752, 761, 781, 792, 817, 826, 835, 853, 862, 871, 891, 918, 927, 936, 945, 954, 963, 972, 981, 4132, 4312, 5143, 5231, 5321, 5413, 6154, 6514, 7165, 7253, 7341, 7431, 7523, 7615, 8176, 8264, 8352, 8532, 8624, 8716, 9187, 9275, 9451, 9541, 9725, 9817, 54132, 65143, 74312, 75231, 76154, 85321, 87165, 95413, 97253, 98176, 954132]
954132

Upvotes: 1

Hugh Bothwell
Hugh Bothwell

Reputation: 56684

The first two digits "lock in" all following digits; follow the chain until you find a digit you have already used, then everything up to that point is the longest chain beginning with those digits. Do this on every pair of starting digits, and pick the highest result.

BAD = 0     # any actual lucky number will be higher than this

def make_num(digits):
    total = 0
    for d in digits:
        total = 10*total + d
    return total

def lucky_num_starting_with(a, b):
    if a == b:
        return BAD
    else:
        luckynum = [a, b]
        while True:
            c = abs(a - b)
            if c in luckynum:
                break
            else:
                luckynum.append(c)
                a, b = b, c
        return make_num(luckynum)

def main():
    largest = max(
        lucky_num_starting_with(a, b)
        for a in range(1, 10)
        for b in range(1, 10)
    )
    print("The largest lucky number is {}".format(largest))

if __name__=="__main__":
    main()

which takes about 15 milliseconds to return

The largest lucky number is 954132

A little more analysis shows that

[954132, 98176, 97253, 87165, 85321, 76154, 75231, 74312, 65143,
 9451, 9275, 9187, 8624, 8352, 8264, 7341, 963, 936, 891, 792,
 781, 693, 682, 671, 642, 594, 583, 572, 561, 495, 473, 462, 396,
 385, 374, 297, 286, 198]

are all the "primal" lucky numbers (every other lucky number is a substring of one of these).

Upvotes: 0

Related Questions