

A035237


Smallest number that has exactly n substrings which are square.


0



2, 0, 10, 49, 100, 1000, 1441, 4900, 11449, 104900, 144100, 490000, 1440000, 1144900, 11144900, 16810000, 114490049, 156250000, 114490000, 1114490000, 1681000000
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,1


COMMENTS

No leading 0's allowed in substrings, except for the number 0.
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


LINKS



EXAMPLE

a(3)=49 since 4, 9 and 49 are squares and no smaller number works.


PROG

(Python)
LIMIT = 10**7
ss = set(str(i*i) for i in range(int(LIMIT**.5)+2))
def num_square_substrings(s):
return sum(s[i:j] in ss for i in range(len(s)) for j in range(i+1, len(s)+1))
def agen():
n, k, data = 0, 0, dict()
while True:
if n in data: yield data[n]; n += 1; continue
while True:
if k > LIMIT: assert False, "LIMIT exceeded"
nss = num_square_substrings(str(k))
if nss == n: data[n] = k; yield k; break
elif nss > n:
if nss not in data: data[nss] = k
k += 1
n += 1
g = agen()


CROSSREFS



KEYWORD

nonn,base,more


AUTHOR



EXTENSIONS

a(0) corrected, a(8)a(14) added, and title made more specific by Sean A. Irvine, Oct 01 2020


STATUS

approved



