|
|
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
|
|
|
|