I found a problem where I have been given a set of numbers. One has to find for each number the smallest positive integer such that the product of the number and the integer gives a number whose digits are either in ascending or descending order. I tried to do that in Python 3. But I found that my algorithm is too slow. How can I make the algorithm faster? The program seems to give the right multipliers but it is slow and it has some repetition:
def find_smallest_increasing(number, length):
ehd = -1
num = "0"
length += 1
for one in range(0,length):
for two in range(0,length-one):
for three in range(0,length-one-two):
for four in range(0,length-one-two-three):
for five in range(0,length-one-two-three-four):
for six in range(0,length-one-two-three-four-five):
for seven in range(0,length-one-two-three-four-five-six):
for eight in range(0,length-one-two-three-four-five-six-seven):
for nine in range(0,length-one-two-three-four-five-six-seven-eight):
if max(one,two,three,four,five,six,seven,eight,nine) > 0:
num = "1"*one+"2"*two+"3"*three+"4"*four+"5"*five+"6"*six+"7"*seven+"8"*eight+"9"*nine
if int(num) % number == 0:
if ehd == -1:
ehd = int(num)
if int(num) < ehd:
ehd = int(num)
return(ehd)
def find_smallest_decreasing(number, length):
ehd = -1
num = "0"
length += 1
for one in range(0,length):
for two in range(0,length-one):
for three in range(0,length-one-two):
for four in range(0,length-one-two-three):
for five in range(0,length-one-two-three-four):
for six in range(0,length-one-two-three-four-five):
for seven in range(0,length-one-two-three-four-five-six):
for eight in range(0,length-one-two-three-four-five-six-seven):
for nine in range(0,length-one-two-three-four-five-six-seven-eight):
for zero in range(0,length-one-two-three-four-five-six-seven-eight-nine):
if max(one,two,three,four,five,six,seven,eight,nine) > 0:
num = "9"*one+"8"*two+"7"*three+"6"*four+"5"*five+"4"*six+"3"*seven+"2"*eight+"1"*nine+"0"*zero
if int(num) % number == 0:
if ehd == -1:
ehd = int(num)
if int(num) < ehd:
ehd = int(num)
return(ehd)
a = -1
i = 1
numbers = [363,726,1089, 1313, 1452, 1717, 1798, 1815, 1919, 2121, 2156, 2178, 2189, 2541, 2626, 2805,
2904, 2997, 3131, 3267, 3297, 3434, 3630, 3838, 3993, 4037, 4092, 4107, 4191, 4242, 4257, 4312,
4334, 4343, 4356, 4378, 4407, 4532, 4646, 4719, 4747, 4807, 4949, 5011, 5055, 5071, 5082, 5151,
5214, 5353, 5423, 5445, 5454, 5495, 5610, 5665, 5731, 5808, 5819, 5858, 5951, 5989, 5994, 6171,
6248, 6281, 6429, 6446, 6468, 6523, 6534, 6565, 6567, 6594, 6721, 6767, 6868, 6897, 6919, 7051,
7077, 7128, 7139, 7171, 7227, 7260, 7381, 7424, 7474, 7513, 7623, 7678, 7831, 7858, 7878, 7881,
7909, 7986, 8041, 8063, 8074, 8088, 8107, 8129, 8162, 8173, 8184, 8195, 8214, 8283, 8316, 8349,
8382, 8415, 8453, 8484, 8514, 8624, 8649, 8712, 8756, 8778, 8814, 8932, 8987, 8989, 8990, 8991,
9053, 9064, 9075, 9099, 9101, 9119, 9141, 9156, 9191, 9213, 9251, 9292, 9309, 9328, 9361, 9393,
9438, 9493, 9515, 9546, 9595, 9597, 9603, 9614, 9667, 9678, 9757, 9797, 9801, 9802, 9834, 9890,
9898, 9909]
#numbers = [1815]
for k in range(0,len(numbers)):
number = numbers[k]
a = -1
b = -1
i= 1
j= 1
while a == -1:
if a % 10 != 0:
a = find_smallest_increasing(number,i)
i = i + 1
b = -1
j = 1
while b == -1:
b = find_smallest_decreasing(number,max(i,j))
j = j + 1
print(str(number)+" "+str(min(a,b)/number)+" " + str(min(a,b)))
But the output seems to give the right multipliers:
363 184573 66999999
726 137588 99888888
1089 9182736455463728191 9999999999999999999999
1313 16929 22227777
1452 68794 99888888
1717 12947 22229999
1798 12978 23334444
1815 550352 998888880
1919 11583 22227777
2121 15719 33339999
2156 30973 66777788
2178 45913682277318640955 99999999999999999999990
2189 507591 1111116699
2541 454939 1155999999
2626 12694 33334444
2805 35571 99776655
2904 34397 99888888
2997 333667 999999999
3131 10648 33338888
3267 69727578818487909397 227799999999999999999999
3297 20153 66444441
3434 22649 77776666