A387975 Number of distinct positive integers reachable from n by successively dividing any contiguous substring of at least two digits by an integer d in 2..9, including n itself.

1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 5, 1, 3, 3, 4, 1, 5, 1, 5, 3, 2, 1, 7, 2, 2, 3, 5, 1, 7, 1, 5, 2, 2, 3, 8, 1, 2, 2, 7, 1, 7, 1, 3, 5, 2, 1, 9, 2, 5, 2, 3, 1, 7, 2, 7, 2, 2, 1, 11, 1, 2, 5, 6, 2, 4, 1, 3, 2, 7, 1, 11, 1, 2, 5, 3, 2

Offset

1,10

Comments

The substring may not begin with a zero digit and must be wholly divisible by the chosen digit.

Links

Michael S. Branicky, Table of n, a(n) for n = 1..10000

Example

a(10) = 3 since 10 -> 5 or 10 -> 2, so there are 3 reachable numbers: {10, 5, 2}.
a(127) = 0 as follows. Its possible substrings to replace are 12 and 27.
  From 12:
    12/2 = 6 -> 67 (terminal)
    12/3 = 4 -> 47 (terminal)
    12/4 = 3 -> 37 (terminal)
    12/6 = 2 -> 27
  From 27:
    27/3 = 9 -> 19 (terminal)
    27/9 = 3 -> 13 (terminal)
  Further reductions:
    27 -> 9, 3; all others (67, 47, 37, 19, 13) are terminal.
  9 distinct integers reachable (including 127): {127, 67, 47, 37, 27, 19, 13, 9, 3}.

Prog

(Python)
def children(s):
    return set(int(s[:i]+str(q//d)+s[j:]) for i in range(len(s)-1) for j in range(i+2, len(s)+1) if (w:=s[i:j])[0]!='0' for d in range(2, 10) if (q:=int(w))%d==0)
def a(n):
    reach, expand = {n}, [n]
    while expand:
        q = expand.pop()
        for c in children(str(q)):
            if c not in reach:
                reach.add(c)
                expand.append(c)
    return len(reach)
print([a(n) for n in range(1, 78)])

Crossrefs

Cf. A389140, A387819, A387963, A389399.

Sequence in context: A056753 A385047 A396262 * A385073 A243158 A154723

Adjacent sequences: A387972 A387973 A387974 * A387976 A387977 A387978

Keyword

nonn,base

Author

Michael S. Branicky and Ali Sada, Oct 12 2025

Status

approved