|
%I #13 Dec 28 2020 17:51:35
%S 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,
%T 27,28,29,32,30,33,34,35,31,37,38,39,36,40,41,43,44,45,48,42,46,49,47,
%U 52,50,51,56,53,57,60,64,54,65,55,58,66,59,61,69,62,74,63
%N 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.
%C Conjecture: permutation of the natural numbers.
%C 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 Michael De Vlieger, <a href="/A339607/b339607.txt">Table of n, a(n) for n = 1..16385</a>
%H Michael De Vlieger, <a href="/A339607/a339607.png">Plot of (n, b(n)) with b(n) = a(n)-n for 1 <= n <= 2^14</a>, highlighting and labeling maxima and local minima in b(n).
%H Michael De Vlieger, <a href="/A339607/a339607_1.png">Plot of (n, b(n)) with b(n) = a(n)-n for 1 <= n <= 2^14</a>, color function indicating wt(a(n-1)).
%H Michael De Vlieger, <a href="/A339607/a339607_2.png">Plot of (n, b(n)) with b(n) = a(n)-n for 1 <= n <= 2^14</a>, color function representing degree of consecutive repetition (persistence) of binary weight.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Hamming_weight">Hamming weight</a>
%H Wolfram Research, <a href="http://functions.wolfram.com/NumberTheoryFunctions/DigitCount/31/01/ShowAll.html">Numbers in Pascal's triangle</a>
%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%e Let wt(n) = A000120(n)
%e 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.
%e a(3) = 3 since wt(2) = 1, we find "1" as both first and last bit of yet unused 3 = "11"_2.
%e a(4) = 4 since wt(3) = 2 = "10"_2, we find yet unused 4 = "100"_2 starts with "10"_2.
%e a(5) = 5 since wt(4) = 1, and yet unused 5 = "101"_2 both starts and ends with 1.
%e a(6) = 6 since wt(5) = 2 = "10"_2, we find yet unused 6 = "110"_2 ends with "10"_2.
%e 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.
%e a(8) = 7 since wt(8) = 1, we find "1" in three places in the least unused number m = 7 = "111"_2.
%e 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.
%t 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]
%o (Python)
%o def aupto(n):
%o alst, used = [1], {1}
%o for i in range(2, n+1):
%o binprev = bin(alst[-1])[2:]
%o binwt = binprev.count("1")
%o targetstr = bin(binwt)[2:]
%o morebits, extra, ai = 0, 0, binwt
%o while ai in used:
%o morebits += 1
%o found = False
%o for k in range(2**morebits):
%o binstrk = bin(k)[2:]
%o binstrk = "0"*(morebits-len(binstrk)) + binstrk # pad to length
%o for msbs in range(morebits+1):
%o trystr = binstrk[:msbs] + targetstr + binstrk[msbs:]
%o if trystr[0] == "0": continue
%o trynum = int(trystr, 2)
%o if trynum not in used:
%o if not found: ai = trynum; found = True
%o else: ai = min(ai, trynum)
%o if found: break
%o alst.append(ai); used.add(ai)
%o return alst # use alst[n-1] for a(n)
%o print(aupto(68)) # _Michael S. Branicky_, Dec 16 2020
%Y Cf. A000120, A338209, A339024.
%K nonn,base,easy
%O 1,2
%A _Michael De Vlieger_, Dec 16 2020
|
