Given a number, find a multiplier to make a product whose digits are increasing or decreasing

Question

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

Answer 1

Here are some comments:

1. You should not compare to None using ==. Always use is in this case.
2. Have a look at Python's official style-guide, PEP8. It recommends surrounding operators with spaces for readability and (a consistent use of) four spaces for indentation.
3. You don't need your innermost loop, because you already know the value j needs to take for the sum to be the target number: j = numbersum - (a + b + c + d + e + f + g + h + i)
4. range has 0 as its implicit first argument, so you can just write range(numbersum).
5. You should not use string addition here. Rather accumulate the strings in a list and ''.join(x) them to one string. Call int on the result of that.
6. Try to come up with a better name for nr. Maybe number_reversed?
7. Use str.format: print("{} {} {}".format(div[ind], int(best)/div[ind], int(best))). Or, even simpler: print(div[ind], int(best)/div[ind], int(best)), because the print function separates its arguments with spaces.

---

You might want to try to come up with a better algorithm, though. Maybe something like this:

import itertools

def is_ascending_or_descending(n):
    n = list(str(n))
    n_sorted = sorted(n)
    return n == n_sorted or n == n_sorted[::-1]

def smallest_sorted(n):
    for i in itertools.count(1):
        if is_ascending_or_descending(i * n):
            return i

if __name__ == "__main__":
    numbers = [...]
    for n in numbers:
        best = smallest_sorted(n)
        print(n, best, n * best)

This takes less than a second on my machine for the first two numbers. It takes a lot longer for the next number, though, so there should be an even better algorithm possible.

---

Another way to go at it is generating an i and seeing if it is the right one for any of the numbers:

def all_smallest_sorted(numbers):
    numbers = set(numbers)
    i = 1
    while numbers:
        found = set()
        for n in numbers:
            if is_ascending_or_descending(i * n):
                found.add(n)
                # yield n, i, i * n
                print(n, i, i * n)
        numbers -= found
        i += 1

After letting this run for a while, it found most of the integers. The ones it found are all below 34M. However, I had to stop the script at that point and it did not find them for some of the numbers: 1089, 2178, 3267, 4356, 5445, 6534, 7623, 8712, 9801, 9898, 4107, 8214, 8991

Answer 2

The initial strategy that I thought of was iterating through possible multiplicands, and checking whether the product is monotonic. You seem to be instead iterating through monotonic numbers, and checking whether they're divisible. This may be a better way of doing it, but it can be implemented in a simpler manner. For one thing, you seem to be re-generating the list of monotonic numbers for each number in div. Instead, you should generate a monotonic number, and then check it against all the numbers in div. You can speed this up even more by deleting numbers from div as solutions are found. Another issue is how you're generating monotonic numbers. Your method is rather convoluted and I don't fully understand it, but I'm pretty sure it's not optimal. Monotonic numbers can be generated through the following algorithm:

1. If the number consists solely of n nines, then the next number consists of n+1 ones.
2. Otherwise: a) find the last non-nine digit. b) Add one to this digit. c) Replace the original digit, and all following, with this sum.

For instance, suppose you have 11239. The last non-nine digit is 3. Add one and get 4. Then replace the 3 and all digits after it with 4, and get 11244.

The following code found solutions for 147 out of the 162 target numbers in 86 seconds. Presumably, increasing max_number_length would get more of them. (and making it less verbose would probably save some time)

start = time.time()
max_number_length = 20
not_found = div.copy()
found = 0
for number_length in range(1,max_number_length):
    print("Checking length {}".format(number_length))
    product_as_str = '1'*number_length
    product_as_int = int(product_as_str)
    while True:        
       reverse_product = int(product_as_str[::-1]) 
       for num in not_found:
           if not product_as_int%num:
               found = found+1
               print(num, product_as_int//num, product_as_int,found, time.time()-start)
               not_found.remove(num)                 
           elif not reverse_product%num:
               found = found+1
               print(num, reverse_product//num, reverse_product, found, time.time()-start)
               not_found.remove(num)                  
       if product_as_str == '9'*number_length: break
       for last_non_nine_position in range(number_length-1,-1,-1):
           if product_as_str[last_non_nine_position] !='9': break                  
       next_value = str(int(product_as_str[last_non_nine_position])+1)
       product_as_str = product_as_str[: last_non_nine_position]+ next_value*(number_length-last_non_nine_position)
       product_as_int = int(product_as_str)
print(time.time()-start)

EDIT: the above find decreasing numbers with reverse_product = int(product_as_str[::-1]), but it will look at higher numbers first. To get decreasing numbers, I believe this algorithm will work:

1. If the number is n nines, then the next number should be n+1 ones
2. Otherwise: a) find the first digit that's smaller than the one before it. If there are no such numbers, use the first digit. b) add one to that digit c)replace every digit after that one with ones.

Answer 3

main guard

Put the main section of the program begind a if __name__ == "__main__": guard, so you can import this module if needed.

Spacing

Your code is very inconsistent about spacing before and after operators and commas. Use a code formatter (like black or yapf) to help you.

Looping

Don't loop over the index;

for k in range(0,len(numbers)):
    number = numbers[k]

can be expressed as:

for number in numbers:

Special return value

You return -1 to signal no number has been found. A better return signal would be None, or you could raise a custom exception to signal this.

itertools

Use itertools.count if you need to iterate over an ever increasing number;

a = -1
i= 1
while a == -1:
    if a % 10 != 0:
        a = find_smallest_increasing(number,i)
    i = i + 1

can be a lot cleaner:

a = None
for i in count(1):
    a = find_smallest_increasing(number,i)
    if a is not None:
        break

I suggest you see the talk "looping like a pro".

Control flow

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)

can be simplified:

digits = one, two, three, four, five, six, seven, eight, nine
if any(digits):
    num = int("".join(s * d for s, d in zip("123456789", digits))))
    if not num % number:
        if ehd is None or ehd > num:
            ehd = num

Alternative approach

In addition to the previous answers, here are 2 generators that generate the sorted numbers that are descending or ascending:

def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)

def make_int(numbers):
"""generates an int from an interable of digits"""
    return int("".join(map(str, numbers)))


def monotonic_naive():
    for i in count():
        number_str = str(i)
        if any(b < a for a, b in pairwise(number_str)):
            if not i % 10:
                if all(a >= b for a, b in pairwise(number_str)):
                    yield i
            continue
        yield i
        if number_str != number_str[::-1]:
            yield int(number_str[::-1])


def monotonic_length(number_length=3):
    if number_length == 0:
        yield 0
        return
    number_list = [0] * number_length
    last_not_9 = number_length - 1

    while True:
        number_list[last_not_9] += 1
        if number_list[0]:
            yield make_int(number_list)
        if number_list[-1] and number_list != number_list[::-1]:
            yield make_int(number_list[::-1])

        for last_not_9 in reversed(range(number_length)):
            if number_list[last_not_9] != 9:
                break
            new_num = number_list[last_not_9 - 1] + 1
            number_list[last_not_9:] = [new_num] * len(number_list[last_not_9:])
        else:  # all 9's
            return


def monotonic():
    yield from range(1, 100) # all numbers with 1 or 2 digits are automatically ascending or descending
    for i in count(3):
        yield from sorted(monotonic_length(i))

The second form is based on Accumulation's technique. Especially for larger numbers this will go faster than the naive approach.

You can use it like this:

start = time.time()
number_set = set(numbers)
found = 1
for result in monotonic():
    results = set()
    for number in number_set:
        if not result % number:
            print(
                f"{found:03}/{len(numbers)}", 
                round(time.time()-start, 2),  
                number, 
                result, 
                result/number,
            )
            found += 1
            results.add(number)
    number_set -= results

    if not number_set:
        break

This took about 7 seconds to find the first 151 numbers:

151/162 7.18 9898 555544442222 56126939.0

But the next 5 numbers took 1000s more:

156/162 1034.38 2178 99999999999999999999990 4.591368227731864e+19

after which I stopped it running.