A386395 Smallest final number reachable from n by successively replacing a substring of digits with its square root.

1, 2, 3, 2, 5, 6, 7, 8, 3, 10, 11, 12, 13, 12, 15, 2, 17, 18, 13, 20, 21, 22, 23, 22, 5, 26, 27, 28, 23, 30, 31, 32, 33, 32, 35, 6, 37, 38, 33, 20, 21, 22, 23, 22, 5, 26, 27, 28, 7, 50, 51, 52, 53, 52, 55, 56, 57, 58, 53, 60, 61, 62, 63, 8, 65, 66, 67, 68, 63, 70, 71, 72, 73, 72, 75, 76, 77, 78, 73, 80, 3, 82, 83, 82

Offset: 1

Author

Ali Sada, Jul 20 2025

Keywords

• nonn
• base

Comments

The substring replaced must be a square and cannot begin with a 0 digit.

There may be multiple different replacements possible and the aim is whatever steps reach the smallest final value.

Examples

			425 -> 25 -> 5.
1004 -> 102.
6251 -> 251 -> 51.
9616 -> 3616 -> 196 -> 136 -> 16 -> 4 -> 2.
9996 -> 9936 -> 996 -> 936 -> 96 -> 36 -> 6.
		

Links

• Michael S. Branicky, Table of n, a(n) for n = 1..10000
• Michael S. Branicky, Scatter plot of n, a(n) for n = 1..10^6.

Crossrefs

Cf. A000290, A048385.

Programs

Python

from math import isqrt
def children(n):
    s = str(n)
    return set(int(s[:i]+str(r)+s[j:]) for i in range(len(s)) for j in range(i+1, len(s)+1) if (w:=s[i:j])[0]!='0' and (r:=isqrt(t:=int(w)))**2 == t)
def a(n):
    reach, expand = {n}, [n]
    while expand:
        q = expand.pop()
        for c in children(q):
            if c not in reach:
                reach.add(c)
                expand.append(c)
    return min(reach)
print([a(n) for n in range(1, 85)]) # Michael S. Branicky, Jul 20 2025