cp's OEIS Frontend

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

%I A338209 #28 Jun 20 2025 08:12:11
%S A338209 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,
%T A338209 39,36,34,38,43,44,47,21,51,52,55,29,60,68,42,59,37,63,46,76,67,71,84,
%U A338209 75,92,100,79,45,108,116,124,53,132,50,83,140,87,61,69,91,77
%N 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).
%C A338209 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).
%C A338209 Likely a permutation of the natural numbers.
%C A338209 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.
%C A338209 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.
%C A338209 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.
%C A338209 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.
%C A338209 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.
%C A338209 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.
%C A338209 2^4 appears at index 47201. - _Michael S. Branicky_, Dec 16 2020
%C A338209 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
%H A338209 Michael De Vlieger, <a href="/A338209/b338209.txt">Table of n, a(n) for n = 1..16385</a>
%H A338209 Michael De Vlieger, <a href="/A338209/a338209.png">Annotated plot</a> (n, a(n)) for 1 <= n <= 2^8, color coded to show k (mod 8).
%H A338209 Michael De Vlieger, <a href="/A338209/a338209_1.png">Enlarged plot</a> (n, a(n)) for 1 <= n <= 2^14, color coded to show k (mod 8).
%H A338209 Michael De Vlieger, <a href="/A338209/a338209_2.png">Log-log plot</a> (n, a(n)) for 1 <= n <= 2^14, color coded to show k (mod 8), showing branching points.
%H A338209 Michael De Vlieger, <a href="/A338209/a338209_3.png">Persistence plot</a> (n, a(n)) for 1 <= n <= 2^8, color coded to show consecutive repetitions of the same binary weight.
%H A338209 Wikipedia, <a href="https://en.wikipedia.org/wiki/Hamming_weight">Hamming weight</a>
%H A338209 Wolfram Research, <a href="http://functions.wolfram.com/NumberTheoryFunctions/DigitCount/31/01/ShowAll.html">Numbers in Pascal's triangle</a>
%H A338209 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%e A338209 a(2) = 3 since the binary weight of 1 is 1, and 3 = 1 (mod 2^1).
%e A338209 a(3) = 2 since wt(3) = 2, and 2 = 2 (mod 2^2).
%e A338209 a(4) = 5 since wt(2) = 1, 5 = 1 (mod 2^1), etc.
%t A338209 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]
%o A338209 (Python)
%o A338209 def aupto(n):
%o A338209   alst, used = [1], {1}
%o A338209   for i in range(2, n+1):
%o A338209     binprev = bin(alst[-1])[2:]
%o A338209     binwt = binprev.count("1")
%o A338209     pow2 = 2**(len(bin(binwt))-2)
%o A338209     while binwt in used: binwt += pow2
%o A338209     alst.append(binwt); used.add(binwt)
%o A338209   return alst    # use alst[n-1] for a(n)
%o A338209 print(aupto(66)) # _Michael S. Branicky_, Dec 16 2020
%Y A338209 Cf. A000120, A049773, A339024, A339607.
%K A338209 nonn,base,easy
%O A338209 1,2
%A A338209 _Michael De Vlieger_, Dec 16 2020