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,2

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

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

Example

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.

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]

Prog

(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

Crossrefs

Cf. A000120, A338209, A339024.

Sequence in context: A362134 A232895 A274607 * A262374 A299442 A299440

Adjacent sequences: A339604 A339605 A339606 * A339608 A339609 A339610

Keyword

nonn,base,easy

Author

Michael De Vlieger, Dec 16 2020

Status

approved