4
$\begingroup$

A positive integer is said to be “kind" if it is divisible by one of its digits other than 1 (https://oeis.org/A185186). A kind string of numbers is a finite sequence of numbers all of whose terms, except for the last, are kind, and in which every term after the first equals the previous term divided by one of its digits other than 1.

For all n up to 10, what is the smallest possible first term of a kind string of numbers of n terms?

564,480 is the first of a kind string of 10 numbers, but not the smallest possible for a string of that length.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Every term after the second, means, starting at third term? I think it's supposed to start at second term, as otherwise the answer is just 2, by tacking 2 at the beginning of any sequence of length n-1. $\endgroup$
    – justhalf
    Commented Feb 3 at 16:16
  • $\begingroup$ @justhalf Right! Clarified. $\endgroup$
    – Bernardo Recamán Santos
    Commented Feb 3 at 16:19
  • $\begingroup$ Is 1 a kind number? It's not divisible by "one of its digits other than 1" $\endgroup$
    – justhalf
    Commented Feb 8 at 4:45

2 Answers 2

Reset to default
2
$\begingroup$

Brute Force Computer Search (Dynamic Programming)

$$1$$ $$2\rightarrow1$$ $$12\rightarrow6\rightarrow1$$ $$24\rightarrow12\rightarrow6\rightarrow1$$ $$72\rightarrow36\rightarrow12\rightarrow6\rightarrow1$$ $$288\rightarrow144\rightarrow36\rightarrow12\rightarrow6\rightarrow1$$ $$1728\rightarrow864\rightarrow144\rightarrow36\rightarrow12\rightarrow6\rightarrow1$$ $$4992\rightarrow2496\rightarrow1248\rightarrow624\rightarrow312\rightarrow156\rightarrow26\rightarrow13$$ $$13824\rightarrow6912\rightarrow3456\rightarrow864\rightarrow144\rightarrow36\rightarrow12\rightarrow6\rightarrow1$$ $$27648\rightarrow13824\rightarrow6912\rightarrow3456\rightarrow864\rightarrow144\rightarrow36\rightarrow12\rightarrow6\rightarrow1$$ $$55296\rightarrow27648\rightarrow13824\rightarrow6912\rightarrow3456\rightarrow864\rightarrow144\rightarrow36\rightarrow12\rightarrow6\rightarrow1$$

Here's even more than requested:

$$110592\rightarrow55296\rightarrow27648\rightarrow13824\rightarrow6912\rightarrow3456\rightarrow864\rightarrow144\rightarrow36\rightarrow12\rightarrow6\rightarrow1$$ $$221184\rightarrow110592\rightarrow55296\rightarrow27648\rightarrow13824\rightarrow6912\rightarrow3456\rightarrow864\rightarrow144\rightarrow36\rightarrow12\rightarrow6\rightarrow1$$ $$442368\rightarrow221184\rightarrow110592\rightarrow55296\rightarrow27648\rightarrow13824\rightarrow6912\rightarrow3456\rightarrow864\rightarrow144\rightarrow36\rightarrow12\rightarrow6\rightarrow1$$ $$1327104\rightarrow442368\rightarrow221184\rightarrow110592\rightarrow55296\rightarrow27648\rightarrow13824\rightarrow6912\rightarrow3456\rightarrow864\rightarrow144\rightarrow36\rightarrow12\rightarrow6\rightarrow1$$ $$2654208\rightarrow1327104\rightarrow442368\rightarrow221184\rightarrow110592\rightarrow55296\rightarrow27648\rightarrow13824\rightarrow6912\rightarrow3456\rightarrow864\rightarrow144\rightarrow36\rightarrow12\rightarrow6\rightarrow1$$ $$7962624\rightarrow3981312\rightarrow1327104\rightarrow442368\rightarrow221184\rightarrow110592\rightarrow55296\rightarrow27648\rightarrow13824\rightarrow6912\rightarrow3456\rightarrow864\rightarrow144\rightarrow36\rightarrow12\rightarrow6\rightarrow1$$

Code:

k = {}
n = {}
r = {}

for _ in range(1, 10000000+1):
    m = -1
    n[_] = None
    for d in set(str(_)):
        d = int(d)
        if d < 2: continue
        if _ % d: continue
        z = k[_//d]
        if z > m:
            m = z
            n[_] = d
    k[_] = m + 1
    if m + 1 not in r: r[m + 1] = _

for _ in range(max(r)+1):
    z = r[_]
    print('>! $$', z, end='', sep='')
while n[z]:
    z //= n[z]
    print('\\rightarrow', z, end='', sep='')
print('$$')
Improve this answer
$\endgroup$
2
$\begingroup$

The first few are easy to find without computer assistance. Beyond those, a programmed search may be necessary to confirm optimality.

 (2) 2 1
 (3) 12 6 1
 (4) 24 12 6 1
 (5) 72 36 12 6 1
 (6) 288 144 36 12 6 1
 (7) 1728 864 216 36 12 6 1
 (8) 4992 2496 1248 624 312 156 26 13  (Hey! What are you doing here?)
 (9) 13824 6912 3456 864 216 36 12 6 1
 (10) 27648 13824 6912 3456 864 216 36 12 6 1

But why stop there?

 (11) 55296 27648 ...
 (12) 110592 55296 ...
 (13) 221184 110592 ...
 (14) 442368 221184 ...
 (15) 1327104 663552 331776 110592 ...
 (16) 2654208 1327104 ...
 (17) 7962624 3981312 1327104 ...
 (18) 15925248 7962624 ...
 (19) 42467328 21233664 10616832 5308416 1769472 884736 221184 ...
 (20) 99090432 49545216 24772608 12386304 6193152 3096576 442368 ...

 (21) 254803968
 (22) 573308928
 (23) 1585446912
 (24) 3170893824
 (25) 9172942848
 (26) 19025362944
 (27) 38050725888
 (28) 88785027072
 (29) 195689447424
 (30) 476993028096
 (31) 953986056192
 (32) 1907972112384
 (33) 3815944224768
 (34) 8523362598912
 (35) 17046725197824
 (36) 45791330697216
 (37) 91582661394432
 (38) 183165322788864
 (39) 366330645577728
 (40) 732661291155456
 (41) 1465322582310912
 (42) 2930645164621824
 (43) 5861290329243648
 (44) 11722580658487296
 (45) 23445161316974592
 (46) 46890322633949184
 (47) 93780645267898368
 (48) 187561290535796736
 (49) 375122581071593472
 (50) 750245162143186944

Improve this answer
$\endgroup$
2
  • $\begingroup$ How many of those end not in 1? $\endgroup$
    – justhalf
    Commented Feb 8 at 3:06
  • $\begingroup$ @justhalf #30 thru #33 and #36 onward end with 13. $\endgroup$
    – Daniel Mathias
    Commented Feb 8 at 3:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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