0
$\begingroup$

I saw the following programming problem in https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=lukut:

A positive integer $n$ will be called monotonic, if its decimal digits are in ascending or descending order. Suppose we are given a list of 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.

I heard that one can find an algorithm to find the least possible positive multipliers for every case that makes the numbers monotonic in less than second. What kind of algorithm would be suitable? I solved the problem by Python but the solution takes too much time:

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, 6534, 7623, 8712, 9801, 5445]

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)))

The existence of a such number is proved in Does every positive number $n$ have a multiple, which has a monotonic digits in decimal basis? .

$\endgroup$
3
  • $\begingroup$ Are you looking for a single multiplier that works for all numbers in your list, or a (possibly different) multiplier for each number? $\endgroup$ – Robert Israel Feb 4 '18 at 21:41
  • $\begingroup$ @RobertIsrael I am looking for a different multiplier for each number. $\endgroup$ – Jaakko Seppälä Feb 5 '18 at 5:20
  • $\begingroup$ Maybe one could make the program faster if one checks if the given number is divisible by 3, 9 or 11 and then one can say that number of eights is congruent to something mod 3, 9 or 11 but I think this does not make program so fast it solves the problem in seconds. $\endgroup$ – Jaakko Seppälä Feb 6 '18 at 14:09
0
$\begingroup$

Suppose, a number $N>1$ is given. Write $N$ in the form $$\large N=2^a\cdot 5^b\cdot n$$ with $\gcd(n,10)=1$. Then, the number $$\large (10^{\phi(n)}-1)\cdot 10^{max(a,b)}$$ is monotonic (it only has nines followed by zeros or only nines) and divisible by $N$. $\phi(n)$ denotes the totient-function.

$\endgroup$
3
  • $\begingroup$ With Euler's theorem, it is easy to see $$n|10^{\phi(n)}-1$$ $\endgroup$ – Peter Feb 5 '18 at 12:37
  • $\begingroup$ Yes, but I think it is not necessary the smallest possible. $\endgroup$ – Jaakko Seppälä Feb 5 '18 at 15:54
  • $\begingroup$ @user2219896 I overlooked this. But at least, my answer shows that such a number must exist. $\endgroup$ – Peter Feb 6 '18 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.