A320441 Numbers whose binary expansion is quasiperiodic.

3, 7, 10, 15, 21, 31, 36, 42, 45, 54, 63, 73, 85, 91, 109, 127, 136, 146, 153, 170, 173, 181, 182, 187, 204, 219, 221, 238, 255, 273, 292, 307, 341, 365, 375, 409, 438, 443, 477, 511, 528, 546, 561, 585, 594, 614, 627, 660, 682, 685, 693, 725, 726, 731, 750

Offset

1,1

Comments

The binary representation of a term (ignoring leading zeros) can be covered by (possibly overlapping) occurrences of one of its proper prefix.

This sequence contains A121016.

For any k > 0, there are A320434(k)/2 terms with binary length k.

Links

Michael S. Branicky, Table of n, a(n) for n = 1..10000

Rémy Sigrist, Scatterplot of the first difference of the first 100000 terms

Formula

A020330(a(n)) belongs to the sequence for any n > 0.

A297405(a(n)) belongs to the sequence for any n > 0.

Example

The first terms, alongside their binary representations and prefixes, are:
  n   a(n)  bin(a(n))  prefix
  --  ----  ---------  ------
   1     3         11       1
   2     7        111       1
   3    10       1010      10
   4    15       1111       1
   5    21      10101     101
   6    31      11111       1
   7    36     100100     100
   8    42     101010      10
   9    45     101101     101
  10    54     110110     110
  11    63     111111       1
  12    73    1001001    1001

Prog

(PARI) isok(w) = { my (tt=0); for (l=1, oo, my (t=w%(2^l)); if (t!=tt, if (t==w, return (0)); my (r=w, g=l); while (g-->=0 && r>=t, r \= 2; if (r%(2^l)==t, if (r==t, return (1), g=l))); tt = t)) }
(Python)
def qp(w):
    for i in range(1, len(w)):
        prefix, covered = w[:i], set()
        for j in range(len(w)-i+1):
            if w[j:j+i] == prefix:
                covered |= set(range(j, j+i))
        if covered == set(range(len(w))):
            return True
    return False
def ok(n): return qp(bin(n)[2:])
print([k for k in range(751) if ok(k)]) # Michael S. Branicky, Mar 20 2022

Crossrefs

Cf. A020330, A121016, A297405, A320434.

Sequence in context: A294477 A362829 A085145 * A353654 A143101 A307612

Adjacent sequences: A320438 A320439 A320440 * A320442 A320443 A320444

Keyword

nonn,base

Author

Rémy Sigrist, Jan 09 2019

Status

approved