

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(n1) anywhere within its own binary expansion.


4



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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(n1)).
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"*(morebitslen(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[n1] for a(n)
print(aupto(68)) # Michael S. Branicky, Dec 16 2020


CROSSREFS

Cf. A000120, A338209, A339024.
Sequence in context: A297440 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



