|
%I #23 Dec 16 2020 08:48:43
%S 2,0,10,49,100,1000,1441,4900,11449,104900,144100,490000,1440000,
%T 1144900,11144900,16810000,114490049,156250000,114490000,1114490000,
%U 1681000000
%N Smallest number that has exactly n substrings which are square.
%C No leading 0's allowed in substrings, except for the number 0.
%C a(15+5k+j) <= 1681*10^(4+2k+j) for j = 0, 1. In particular, a(21) <= 16810000000. Similar upper bounds can be derived using numbers of the form 49*10^k, 144*10^k, 1149*10^k, etc. - _Michael S. Branicky_, Dec 15 2020
%e a(3)=49 since 4, 9 and 49 are squares and no smaller number works.
%o (Python)
%o LIMIT = 10**7
%o ss = set(str(i*i) for i in range(int(LIMIT**.5)+2))
%o def num_square_substrings(s):
%o return sum(s[i:j] in ss for i in range(len(s)) for j in range(i+1, len(s)+1))
%o def agen():
%o n, k, data = 0, 0, dict()
%o while True:
%o if n in data: yield data[n]; n += 1; continue
%o while True:
%o if k > LIMIT: assert False, "LIMIT exceeded"
%o nss = num_square_substrings(str(k))
%o if nss == n: data[n] = k; yield k; break
%o elif nss > n:
%o if nss not in data: data[nss] = k
%o k += 1
%o n += 1
%o g = agen()
%o for i in range(13): print(next(g)) # _Michael S. Branicky_, Dec 15 2020
%Y Cf. A035222.
%K nonn,base,more
%O 0,1
%A _Erich Friedman_
%E a(0) corrected, a(8)-a(14) added, and title made more specific by _Sean A. Irvine_, Oct 01 2020
%E a(15)-a(20) from _Michael S. Branicky_, Dec 15 2020
| 