A339607 a(1) = 1, a(n) is the least m not already in the sequence that contains the binary expansion of the binary weight of a(n-1) anywhere within its own binary expansion.

1, 2, 3, 4, 5, 6, 8, 7, 11, 12, 9, 10, 13, 14, 15, 16, 17, 18, 19, 22, 23, 20, 21, 24, 25, 26, 27, 28, 29, 32, 30, 33, 34, 35, 31, 37, 38, 39, 36, 40, 41, 43, 44, 45, 48, 42, 46, 49, 47, 52, 50, 51, 56, 53, 57, 60, 64, 54, 65, 55, 58, 66, 59, 61, 69, 62, 74, 63

Offset: 1

Author

Michael De Vlieger, Dec 16 2020

Keywords

• nonn
• base
• easy

Comments

Conjecture: permutation of the natural numbers.

A permutation of the integers since n appears at or before index 2^n - 1, the first number with binary weight n. - Michael S. Branicky, Dec 16 2020

Examples

			Let wt(n) = A000120(n)
a(2) = 2 since wt(a(1)) = wt(1) = 1, and we find "1" at the beginning of the binary expansion of the yet unused 2 = "10"_2.
a(3) = 3 since wt(2) = 1, we find "1" as both first and last bit of yet unused 3 = "11"_2.
a(4) = 4 since wt(3) = 2 = "10"_2, we find yet unused 4 = "100"_2 starts with "10"_2.
a(5) = 5 since wt(4) = 1, and yet unused 5 = "101"_2 both starts and ends with 1.
a(6) = 6 since wt(5) = 2 = "10"_2, we find yet unused 6 = "110"_2 ends with "10"_2.
a(7) = 8 since wt(6) = 2 = "10"_2, we find that the least unused m = 7 only contains 1s in binary. The next term m = 8 furnishes "10"_2 at the start of its binary expansion "1000"_2.
a(8) = 7 since wt(8) = 1, we find "1" in three places in the least unused number m = 7 = "111"_2.
a(9) = 11 since wt(7) = 3 = "11"_2, The next unused numbers 9 and 10 are written "1001"_2 and "1010"_2, respectively. Only when we reach m = 11 = "1011"_2 do we find an unused binary number that contains the word "11"_2, etc.
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..16385
• Michael De Vlieger, Plot of (n, b(n)) with b(n) = a(n)-n for 1 <= n <= 2^14, highlighting and labeling maxima and local minima in b(n).
• Michael De Vlieger, Plot of (n, b(n)) with b(n) = a(n)-n for 1 <= n <= 2^14, color function indicating wt(a(n-1)).
• Michael De Vlieger, Plot of (n, b(n)) with b(n) = a(n)-n for 1 <= n <= 2^14, color function representing degree of consecutive repetition (persistence) of binary weight.
• Wikipedia, Hamming weight
• Wolfram Research, Numbers in Pascal's triangle
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A000120, A338209, A339024.

Programs

Mathematica

Nest[Append[#, Block[{k = 1, r = IntegerDigits[DigitCount[#[[-1]], 2, 1], 2]}, While[Nand[FreeQ[#, k], SequenceCount[IntegerDigits[k, 2], r] > 0], k++]; k]] & @@ {#, Length@ #} &, {1}, 2^7]

Python

def aupto(n):
  alst, used = [1], {1}
  for i in range(2, n+1):
    binprev = bin(alst[-1])[2:]
    binwt = binprev.count("1")
    targetstr = bin(binwt)[2:]
    morebits, extra, ai = 0, 0, binwt
    while ai in used:
      morebits += 1
      found = False
      for k in range(2**morebits):
        binstrk = bin(k)[2:]
        binstrk = "0"*(morebits-len(binstrk)) + binstrk # pad to length
        for msbs in range(morebits+1):
          trystr = binstrk[:msbs] + targetstr + binstrk[msbs:]
          if trystr[0] == "0": continue
          trynum = int(trystr, 2)
          if trynum not in used:
            if not found: ai = trynum; found = True
            else: ai = min(ai, trynum)
      if found: break
    alst.append(ai); used.add(ai)
  return alst    # use alst[n-1] for a(n)
print(aupto(68)) # Michael S. Branicky, Dec 16 2020