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

Author

Rémy Sigrist, Jan 09 2019

Keywords

• nonn
• base

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.

Examples

			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
		

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

Crossrefs

Cf. A020330, A121016, A297405, A320434.

Programs

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

Formula

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

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