cp's OEIS Frontend

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

%I A386395 #27 Jul 27 2025 05:49:28
%S A386395 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,
%T A386395 27,28,23,30,31,32,33,32,35,6,37,38,33,20,21,22,23,22,5,26,27,28,7,50,
%U A386395 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
%N A386395 Smallest final number reachable from n by successively replacing a substring of digits with its square root.
%C A386395 The substring replaced must be a square and cannot begin with a 0 digit.
%C A386395 There may be multiple different replacements possible and the aim is whatever steps reach the smallest final value.
%H A386395 Michael S. Branicky, <a href="/A386395/b386395.txt">Table of n, a(n) for n = 1..10000</a>
%H A386395 Michael S. Branicky, <a href="/A386395/a386395.png">Scatter plot of n, a(n) for n = 1..10^6.</a>
%e A386395 425 -> 25 -> 5.
%e A386395 1004 -> 102.
%e A386395 6251 -> 251 -> 51.
%e A386395 9616 -> 3616 -> 196 -> 136 -> 16 -> 4 -> 2.
%e A386395 9996 -> 9936 -> 996 -> 936 -> 96 -> 36 -> 6.
%o A386395 (Python)
%o A386395 from math import isqrt
%o A386395 def children(n):
%o A386395     s = str(n)
%o A386395     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)
%o A386395 def a(n):
%o A386395     reach, expand = {n}, [n]
%o A386395     while expand:
%o A386395         q = expand.pop()
%o A386395         for c in children(q):
%o A386395             if c not in reach:
%o A386395                 reach.add(c)
%o A386395                 expand.append(c)
%o A386395     return min(reach)
%o A386395 print([a(n) for n in range(1, 85)]) # _Michael S. Branicky_, Jul 20 2025
%Y A386395 Cf. A000290, A048385.
%K A386395 nonn,base
%O A386395 1,2
%A A386395 _Ali Sada_, Jul 20 2025