A110502 Numbers n such that n in binary representation has a block of exactly a nontrivial square number of zeros.

16, 33, 48, 66, 67, 80, 97, 112, 132, 133, 134, 135, 144, 161, 176, 194, 195, 208, 225, 240, 264, 265, 266, 267, 268, 269, 270, 271, 272, 289, 304, 322, 323, 336, 353, 368, 388, 389, 390, 391, 400, 417, 432, 450, 451, 464, 481, 496, 512, 528, 529, 530, 531

Offset: 1

Author

Jonathan Vos Post, Sep 11 2005

Keywords

• base
• easy
• nonn

Comments

a(n) is the index of zeros in the complement of the square analog of the Baum-Sweet sequence, which is b(n) = 1 if the binary representation of n contains no block of consecutive zeros of exactly a nontrivial square number length; otherwise b(n) = 0.

Examples

			a(1) = 16 because 16 (base 2) = 10000, which has a block of 4 = 2^2 zeros.
a(2) = 33 because 33 (base 2) = 100001, which has a block of 4 zeros.
a(3) = 48 because 48 (base 2) = 110000, which has a block of 4 zeros.
a(49) = 512 because 512 (base 2) = 1000000000, with a block of 9 = 3^2 zeros.
Similarly, there are blocks of exactly 9 zeros in 1025, 1536, 2050, 2051, 3073, 3584, 7149, 8196, 8197, 8198, 8199.
65536, 131073, 196608, 262146 and 262147 are in this sequence because (base 2) they each have a block of 16 = 4^2 zeros.
33554432 has a block of 25 = 5^2 zeros.
		

References

• J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 157.

Links

• Robert Israel, Table of n, a(n) for n = 1..10000
• J.-P. Allouche, Finite Automata and Arithmetic, Séminaire Lotharingien de Combinatoire, B30c (1993), 23 pp.

Crossrefs

Cf. A000290, A037011, A086747, A110471, A110472, A110474.

Programs

Maple

filter:= proc(n) local L,nL,A,B;
  L:= convert(n,base,2);
  nL:= nops(L);
  A:= select(t -> L[t]=0 and (t=1 or L[t-1]=1), [$1..nL]);
  B:= select(t -> L[t]=1 and L[t-1]=0, [$2..nL]);
  ormap(t -> t>3 and issqr(t),B-A)
end proc:select(filter, [$1..1000]); # Robert Israel, Sep 01 2021

Mathematica

Select[Range[531], Or @@ (First[ # ] == 0 && Length[ # ] > 1 && IntegerQ[Length[ # ]^(1/2)] &) /@ Split[IntegerDigits[ #, 2]] &] (* Ray Chandler, Sep 12 2005 *)

Python

from math import isqrt
from itertools import groupby
def is_nt_sqr(n): # is nontrivial square
    return n > 1 and isqrt(n)**2 == n
def ok(n):
    b = bin(n)[2:]
    return any(k == '0' and is_nt_sqr(len(list(g))) for k, g in groupby(b))
print(list(filter(ok, range(532)))) # Michael S. Branicky, Sep 01 2021

Formula

a(n) is in this sequence iff n (base 2) has a block (not a sub-block) of k^2 = A000290(k) consecutive zeros for k>1.

Extensions

Corrected and extended by Ray Chandler, Sep 12 2005