login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A262278 Number of binary strings of length 2n that are squares, but are not expressible as the concatenation of two or more squares. 1
0, 2, 2, 6, 10, 24, 40, 92, 164, 408, 704, 1674, 3036, 7002, 12688, 29040, 53034, 119502, 219152, 487924, 900686, 1984664, 3683632, 8039958, 15012858, 32477788, 60988590, 130889590, 247193588, 526601802, 999873640, 2115798292 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

Here by a "square" we mean a string of the form xx, where x is any string, like the English word "hotshots".

LINKS

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

EXAMPLE

For n = 4 the 10 strings are (0001)^2, (0010)^2, (0100)^2, (0110)^2, (0111)^2, and their complements.

PROG

(PARI)

MaxSquares(b, k)={if(b==0, k, my(r=-1); for(i=1, k, if(bitand(bitxor(b, b>>i), (1<<i)-1)==0, r=max(r, MaxSquares(b>>(2*i), k-i)))); if(r>=0, r+1, r))}

a(n)={my(s=0); for(i=0, 2^(n-1)-1, if(MaxSquares(bitor(i<<n, i), n)==1, s++)); 2*s} \\ Andrew Howroyd, Jun 18 2018

(Python)

from numba import njit

@njit() # comment out for n >= 32

def MS(b, k):

  if b == 0: return k

  r = -1

  for i in range(1, k+1):

    if ((b^(b>>i)) & ((1<<i)-1)) == 0:

      r = max(r, MS(b>>(2*i), k-i))

  return r+1 if r >= 0 else r

@njit() # comment out for n >= 32

def a(n):

  s = 0

  for i in range(int(2**(n-1))):

    s += MS((i<<n)|i, n)==1

  return 2*s

print([a(n) for n in range(18)]) # Michael S. Branicky, Dec 29 2020 after Andrew Hoyroyd

CROSSREFS

Cf. A262068.

Sequence in context: A078008 A151575 A284462 * A265639 A208900 A229733

Adjacent sequences:  A262275 A262276 A262277 * A262279 A262280 A262281

KEYWORD

nonn,more

AUTHOR

Jeffrey Shallit, Sep 17 2015

EXTENSIONS

Two more terms from Jeffrey Shallit, Dec 14 2015

a(12)-a(24) from Andrew Howroyd, Jun 18 2018

a(25)-a(31) from Michael S. Branicky, Dec 29 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 12 23:35 EDT 2021. Contains 343829 sequences. (Running on oeis4.)