A339024 -id:A339024 - cp's OEIS frontend

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

Michael De Vlieger, Dec 16 2020

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

			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.

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

Cf. A000120, A338209, A339024.

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]

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

A338209 a(1) = 1, a(n) is the least m not already in the sequence whose binary expansion ends with the binary expansion of the binary weight of a(n-1).

Original entry on oeis.org

1, 3, 2, 5, 6, 10, 14, 7, 11, 15, 4, 9, 18, 22, 19, 23, 12, 26, 27, 20, 30, 28, 31, 13, 35, 39, 36, 34, 38, 43, 44, 47, 21, 51, 52, 55, 29, 60, 68, 42, 59, 37, 63, 46, 76, 67, 71, 84, 75, 92, 100, 79, 45, 108, 116, 124, 53, 132, 50, 83, 140, 87, 61, 69, 91, 77

Offset: 1

Michael De Vlieger, Dec 16 2020

Define binary weight wt(n) as A000120(n), the number of 1s in the binary expansion of n. Let w = A000120(a(n-1)) the binary weight of the previous term. In other words, a(n) is the least m not already in the sequence such that m mod 2^k = w, where k = floor(1 + log_2 w).
Likely a permutation of the natural numbers.
The numbers m = 2^k with 0 <= k <= 3 appear at indices {1, 3, 11, 222}. The term 16 has not appeared for n <= 2^14 and may not until n approaches 2^16.
The numbers m = (2^k + 1) appear at indices {2, 4, 12, 223, ...}. The numbers m = 2^k or (2^k + 1) require n approximately equal to 2^m in order to appear in the sequence.
The numbers m = (2^k - 1) with 1 <= k <= 14 appear at indices {1, 2, 8, 10, 23, 43, 130, 278, 447, 758, 1390, 2525, 4719, 9333}, respectively.
The plot exhibits dendritic streams of residues r (mod 2^k). We can identify coordinates (x, y) = (n, a(n)) on the plot where the streams branch.
The branches of the tree in the plot contain m congruent to r (mod 2^k), where r is a term (except the last term) in row (k-1) of A049773.
Given 2^14 terms of this sequence, we see 2 or 3 successive invocations of w, otherwise, w appears just once before a different value succeeds it in the next term.
2^4 appears at index 47201. - Michael S. Branicky, Dec 16 2020
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

			a(2) = 3 since the binary weight of 1 is 1, and 3 = 1 (mod 2^1).
a(3) = 2 since wt(3) = 2, and 2 = 2 (mod 2^2).
a(4) = 5 since wt(2) = 1, 5 = 1 (mod 2^1), etc.

Michael De Vlieger, Table of n, a(n) for n = 1..16385
Michael De Vlieger, Annotated plot (n, a(n)) for 1 <= n <= 2^8, color coded to show k (mod 8).
Michael De Vlieger, Enlarged plot (n, a(n)) for 1 <= n <= 2^14, color coded to show k (mod 8).
Michael De Vlieger, Log-log plot (n, a(n)) for 1 <= n <= 2^14, color coded to show k (mod 8), showing branching points.
Michael De Vlieger, Persistence plot (n, a(n)) for 1 <= n <= 2^8, color coded to show consecutive repetitions of the same binary weight.
Wikipedia, Hamming weight
Wolfram Research, Numbers in Pascal's triangle
Index entries for sequences related to binary expansion of n

Cf. A000120, A049773, A339024, A339607.

Nest[Append[#, Block[{k = 1, r = DigitCount[#[[-1]], 2, 1], s}, s = IntegerLength[r, 2]; While[Nand[FreeQ[#, k], Mod[k, 2^s] == r], k++]; k]] & @@ {#, Length@ #} &, {1}, 2^7]

def aupto(n):
  alst, used = [1], {1}
  for i in range(2, n+1):
    binprev = bin(alst[-1])[2:]
    binwt = binprev.count("1")
    pow2 = 2**(len(bin(binwt))-2)
    while binwt in used: binwt += pow2
    alst.append(binwt); used.add(binwt)
  return alst    # use alst[n-1] for a(n)
print(aupto(66)) # Michael S. Branicky, Dec 16 2020

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python