A035237 Smallest number that has exactly n substrings which are square.

2, 0, 10, 49, 100, 1000, 1441, 4900, 11449, 104900, 144100, 490000, 1440000, 1144900, 11144900, 16810000, 114490049, 156250000, 114490000, 1114490000, 1681000000

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

Table of n, a(n) for n=0..20.

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()
for i in range(13): print(next(g)) # Michael S. Branicky, Dec 15 2020

Crossrefs

Cf. A035222.

Sequence in context: A065624 A086890 A167387 * A189423 A342287 A230696

Adjacent sequences: A035234 A035235 A035236 * A035238 A035239 A035240

Keyword

nonn,base,more

Author

Erich Friedman

Extensions

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

a(15)-a(20) from Michael S. Branicky, Dec 15 2020

Status

approved