login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 3
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

LINKS

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

EXAMPLE

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.

MATHEMATICA

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]]

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")

    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

CROSSREFS

Cf. A000120, A049773, A339024, A339607.

Sequence in context: A331462 A308410 A286111 * A240574 A050061 A058638

Adjacent sequences:  A338206 A338207 A338208 * A338210 A338211 A338212

KEYWORD

nonn,base,easy

AUTHOR

Michael De Vlieger, Dec 16 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 8 08:16 EST 2021. Contains 341942 sequences. (Running on oeis4.)