如何找到最小的正整数，使得数字单调递增？

Question

我发现一个编程问题我无法解决。我有一组整数集合 A。对于 A 中的所有数字 x，找到最小的正整数 y，使得 x*y 的数字是递增或递减的，并且乘积 x*y 最小。例如，如果 A=(363, 726, 1089)，那么 n=(184573, 137588, 9182736455463728191) 给出了数字 (66999999, 99888888, 9999999999999999999999)。

但是有一些难以处理的数字，我的程序无法解决。所有情况都给出如下：

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

这是我的慢程序：

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)

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]

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)
        else:
            a = -1
        i = i + 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)))

它可以在合理的时间内解决一些问题：

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

第二次尝试：

def generate_all_numbers(length):
    l = list()
    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 ten 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:
                                                num1 = "1"*one+"2"*two+"3"*three+"4"*four+"5"*five+"6"*six+"7"*seven+"8"*eight+"9"*nine
                                                num2 = "9"*one+"8"*two+"7"*three+"6"*four+"5"*five+"4"*six+"3"*seven+"2"*eight+"1"*nine+"0"*ten
                                                l.append(int(num1)) 
                                                l.append(int(num2))
    return(list(set(l)))

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]

l = generate_all_numbers(20)
A = list()
for i in range(len(l)):
    for j in range(len(numbers)):
        if l[i] % numbers[j] == 0:
             A.append(l[i])
B = list()
for j in range(len(numbers)):
 best = int("9" * 20)
 for i in range(len(A)):
    if A[i] % numbers[j] == 0:
        if A[i] < best:
            best = A[i]
 print(str(numbers[j])+" "+str(best/numbers[j])+ " " + str(best))

这样可以得到更准确的值，但仍有一些结果是没有意义的，比如：

5445 18365472910927456382001836547291092745638200183654729109274563820018365472910927456382001836547291092745638200183654729109274563820018365472910927456382001836547291092745638200183654729109274563820 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

第三次尝试：我发现如果将简单和困难的情况分开处理，我可以解决更多的情况：

def generate_all_numbers(length):
    l = list()
    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 ten 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:
                                                num1 = "1"*one+"2"*two+"3"*three+"4"*four+"5"*five+"6"*six+"7"*seven+"8"*eight+"9"*nine
                                                num2 = "9"*one+"8"*two+"7"*three+"6"*four+"5"*five+"4"*six+"3"*seven+"2"*eight+"1"*nine+"0"*ten
                                                l.append(int(num1)) 
                                                l.append(int(num2))
    return(list(set(l)))

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)

numbers = [363,726, 1313, 1452, 1717, 1798, 1815, 1919, 2121, 2156, 2189, 2541, 2626, 2805,
2904, 2997, 3131, 3297, 3434, 3630, 3838, 3993, 4037, 4092, 4107, 4191, 4242, 4257, 4312,
4334, 4343, 4378, 4407, 4532, 4646, 4719, 4747, 4807, 4949, 5011, 5055, 5071, 5082, 5151,
5214, 5353, 5423, 5454, 5495, 5610, 5665, 5731, 5808, 5819, 5858, 5951, 5989, 5994, 6171,
6248, 6281, 6429, 6446, 6468, 6523, 6565, 6567, 6594, 6721, 6767, 6868, 6897, 6919, 7051,
7077, 7128, 7139, 7171, 7227, 7260, 7381, 7424, 7474, 7513, 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, 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, 9802, 9834, 9890,
9898, 9909]

hardnumbers = [1089, 2178, 3267, 4356, 5445, 6534, 7623, 8712, 9801]

l = generate_all_numbers(20)
A = list()
for i in range(len(l)):
    for j in range(len(numbers)):
        if l[i] % numbers[j] == 0:
             A.append(l[i])
B = list()
for j in range(len(numbers)):
 best = int("9" * 2000)
 for i in range(len(A)):
    if A[i] % numbers[j] == 0:
        if A[i] < best:
            best = A[i]
 print(str(numbers[j])+" "+str(best/numbers[j])+ " " + str(best))

for k in range(0,len(hardnumbers)):
    number = hardnumbers[k]
    a = -1
    b = -1
    i= 1
    j= 1
    while a == -1:
        if a % 5 != 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)))

一段时间后，缺少的数字是：5445、6534、7623、8712、9801。

但是，为了解决上述所有输入的问题，需要什么样的快速算法呢？

- Jaakko Seppälä

---

评论不适合进行深入的讨论；此对话已被移至聊天室。 - Bhargav Rao

Answer 1

我不确定你的算法输出结果，顺便说一下，获取数字N的下一个单调数字的可能算法如下：

def nextMonotoneDigits(self, N):
        if N < 10: return N
        n, inv_index = N, -1
        num = [int(d) for d in str(n)[::-1]] 

        for i in range(1, len(num)): 
            if num[i] > num[i - 1] or (inv_index != -1 and num[inv_index] == num[i]):
                inv_index = i

        if inv_index == -1: return N

        for i in range(inv_index): num[i] = 9
        num[inv_index] -= 1

        return int(''.join([ str(i) for i in num[::-1]])) 

在这个repl中尝试一下吧。

- loretoparisi

Answer 2

我们可以通过观察到任何一个十进制整数y由不同的部分组成，每个部分都无法影响最终乘积中右侧的数字，从而显著缩小搜索空间。

y = b_n*10^n + b_(n-1)*10^(n-1) ... + b_0*10^0

例如，以您的帖子中的数字363为例。所选y中的最右位数字仅设置最终乘积中的最右位数字：

3 * 363 = 1089

我们现在已经确定了b_0的一位数字，这也决定了最终x*y中最右边的数字，并且（可能）限制了我们对b_1的选择。如果我们想要后面再跟一个9，我们有：

b_1 * 3 + 8 = 9 (mod 10)
b_1 * 3 = 1 (mod 10)
b_1 = (10x + 1) / 3
b_1 = 7

等等。

- גלעד ברקן