Let $p(n)$ be A000041 i.e. the number of partitions of $n$ (the partition numbers).
Let $$ \ell(n)=\left\lfloor\log_2 n\right\rfloor $$
Let $\operatorname{wt}(n)$ be A000120 i.e. number of $1$'s in binary expansion of $n$ (or the binary weight of $n$). Here $$ \operatorname{wt}(2n)=\operatorname{wt}(n), \\ \operatorname{wt}(2n+1)=\operatorname{wt}(n)+1, \\ \operatorname{wt}(0)=0 $$
Let $a(n)$ be an integer sequence such that $$ a(n) = (2g(n) + 1)2^{\ell(n)-h(n)}, \\ a(0) = 0 $$ where $$ g(n) = a(n-2^{\ell(n)}), \\ h(n) = [g(n)=0]\cdot0+[g(n)>0]\cdot(\operatorname{wt}(g(n))-1) $$
Let $b(n)$ be an integer sequence such that $b(0)=0$, $b(n)>b(n-1)$ and it contain all numbers from the sequence $a(n)$.
I conjecture that for $n>0$ we have $$b(p(n))=2^{n-1}.$$
Here is the PARI/GP prog to check it numerically:
upto(n) = my(v1); v1 = vector(n + 1, i, 0); for(i = 1, n, my(A = 2^logint(i, 2), B = v1[i - A + 1]); v1[i + 1] = (2 * B + 1) * A / 2 ^ if(B == 0, 0, hammingweight(B) - 1)); v1 = vecsort(v1)
my(v1, n = 15); v1 = upto(2 ^ n); for(i = 1, n + 1, print(v1[numbpart(i) + 1]))
UPD1: To reproduce the sequence $b(n)$ through itself, use the following rule: if binary $1xyz$ is a term then so are $110xyz$ and $1XYZ$ where the last one is the same as $1xyz$ with rewrite $1 \to 10$.
So here is a new prog:
b1(n) = my(A = n, B, wt = hammingweight(n), v1); v1 = []; for(i=1, wt, B = valuation(A, 2); v1 = concat(binary(2^(B+1)), v1); A \= 2^(B + 1)); fromdigits(v1, 2) \\ transforms 1xyz to 1XYZ
upto1(n) = my(A = 1, v1); while(numbpart(A) < n, A++); v1 = vector(n, i, i == 1); if(n > 1, v1[2] = 2); for(i = 3, A - 1, my(N1 = numbpart(i), v2); v2 = []; for(j = 1, N1 - 1, my(B = b1(v1[j])); if((logint(B, 2) + 1) == i, v2 = concat(v2, B))); my(N2 = numbpart(i - 2)); v2 = concat(vecsort(v2), vector(numbpart(i - 1) - N2, j, v1[N2 + j - 1] + 5*2^(i-3))); for(j=1, min(n - N1 + 1, numbpart(i+1) - N1), v1[N1 + j - 1] = v2[j])); v1
upto2(n) = my(i = 3, s, v1); v1 = [1]; if(n > 1, v1 = [[1], [2]]); s = sum(j=1, #v1, #v1[j]); while(s < n, my(v2); v2 = []; for(j=1, #v1, for(k=1, #v1[j], my(B = v1[j][k]); if((logint(B, 2) + hammingweight(B) + 1) == i, v2 = concat(v2, b1(B))))); v2 = concat(vecsort(v2), vector(#v1[i-2], j, v1[i-2][j] + 5*2^(i-3))); my(C = n - s); v1 = if(C > #v2, concat(v1, [v2]), concat(v1, vector(C, j, [v2[j]]))); s += #v2; i++); my(v3); v3=[]; for(i=1, #v1, v3 = concat(v3, v1[i])); v3
UPD2: Possibly simplest prog:
b2(n) = my(L = logint(n, 2), A = n); A-=2^L; L - if(A==0, 0, logint(A, 2)) - 1
b3(n) = my(A = n); n/2 + 2^(logint(n, 2) - 1)
upto3(n) = my(v0, v1, v2); v0 = [1, 2, 4, 6, 8, 12, 16, 20, 24, 26, 32]; v1 = vector(n, i, if(i <= #v0, v0[i])); v2 = [1, 2, 3, 5, 7, 11]; my(k = 6, j = 3, q = 0); for(i = 12, n, my(A = v2[j] + q); if(A >= v2[k-1], k++; v1[i] = 2^(k-1); j=k\2; q = 0; v2 = concat(v2, i), v1[i] = 2*b3(v1[A]) + 2^(k - 1); if((k - j - 2) >= b2(b3(v1[A+1])), j++; q = 0, q++))); v1
In this last program you can return v2 instead of v1 which gives you positions of powers of $2$ in $b(n)$ (that is, partition numbers).
Is there a way to prove it?
