OFFSET
0,3
COMMENTS
This is also "minimal subset/superset bitmask" transform of the nonnegative integers, A001477. In that transform, applicable to any N -> N injection f, we start from a(0) = 0, after which for n > 0, if there are one or more k_i that are not already present in the sequence among terms a(0) .. a(n-1), and for which bitor(k_i,a(n-1)) = a(n-1), then a(n) = that k_i for which f(k_i) is minimized; otherwise, a(n) = that h_i for which f(h_i) is minimized among the infinite set of numbers h_i for which bitand(h_i,a(n-1)) = a(n-1) and that are not yet present in the sequence. In this case f(n) = A001477(n) = n.
The original, equivalent definition is:
a(0) = 0 and for n > 0, if there are one or more k_i that are not already present in the sequence among terms a(0) .. a(n-1), and for which bitor(k_i,a(n-1)) = a(n-1), then a(n) = that k_i which gives minimum value of A019565(k_i) amongst them; otherwise, when no such k_i exists, a(n) = the least number not already present that can be obtained by toggling a single 0-bit of a(n-1) to 1. This is done by trying to toggle successive vacant bits from the least significant end of the binary representation of a(n-1), until such a sum a(n-1) + 2^h (= a(n-1) bitxor 2^h) is found that is not already present in the sequence.
Shares with permutations like A003188, A006068, A300838, A302846, A303765 and A304083 the property that when moving from any a(n) to a(n+1) either a subset of 0-bits are toggled on (changed to 1's), or a subset of 1-bits are toggled off (changed to 0's), but no both kind of changes may occur at the same step.
Also, like A003188, A006068 and many other base-2 representation related permutations, this permutation preserves the binary size of n (A000523(n)), and furthermore, a(n) seems to stay at most points (except at powers of 2) remarkably close to n.
From Antti Karttunen, May 23 2018: (Start)
Outline of the proof that the definition involving A019565 is equivalent to the recurrent formula:
Even though A019565 is nonmonotonic, for example A019565(4) = 5 = p_3 < A019565(3) = 6 = p_1 * p_2, and in general, although there are always primes p_k < p_{i1} * p_{i2} * ... * p_{ih}, with i1, i2, ..., ih < k, it doesn't matter here, because not just the position of the most significant 1-bit is monotonic in this sequence (see the binary representation at A304747), but also in each subrange (2^k)+2 .. (2^(k+1))-1 the position of the second most significant 1-bit moves only leftward, i.e., is monotonic, which follows from the recursive formula.
To see this, consider the first time in this sequence when in a batch of terms (of equal binary width) we have bits in position k (the most significant position) and (k-1) on (that is, both are 1's), the latter corresponding to prime p_k: while in principle a bit-based rule could choose to subtract 2^(k-1), in preference to any 1-bits to the right of it (that correspond to primes p_{i1} .. p_{ih}), it cannot do so at this stage, because it is the second most significant 1-bit, and then it would not move only leftward, contradicting what was said above. Neither this can occur later when more 1-bits have appeared to their left: the recursive formula guarantees it.
Also conversely, even though p_4 = 7 > 6 = p_1 * p_2, and in general, we always have such prime p_k > p_{i1} * p_{i2} * ... * p_{ih}, with i1, i2, ..., ih < k, and while here A019565-based rule (see comments in A303760) would prefer dividing p_k out instead of any subset of p_{i1} .. p_{ih}, it happens that in that rule, the index of the largest prime (A061395) grows monotonically, so at the stage where p_k is the largest prime of the batch of length 2^(k-1), p_k just cannot be divided out, and also here the structure of the later batches is strictly determined by recursion.
(End)
LINKS
FORMULA
EXAMPLE
From Michael De Vlieger, May 23 2018: (Start)
Table below shows the initial 17 terms at right. First column is index n,
-------------------------------------------
0 . 1 0 0
1 2 2 1 1
2 3 6 11 3
3 . 3 10 2
4 5 15 110 6
5 . 5 100 4
6 2 10 101 5
7 3 30 111 7
8 7 210 1111 15
9 . 7 1000 8
10 2 14 1001 9
11 3 42 1011 11
12 . 21 1010 10
13 5 105 1110 14
14 . 35 1100 12
15 2 70 1101 13
16 11 770 11101 29
... (End)
MATHEMATICA
Map[FromDigits[#, 2] &@ Reverse@ If[# == 1, {0}, Function[f, ReplacePart[Table[0, {PrimePi[f[[-1, 1]]]}], #] &@ Map[PrimePi@ First@ # -> Last@ # &, f]]@ FactorInteger@ #] &@# &, Nest[Append[#, Block[{d = Divisors@ #[[-1]], p = 2}, If[Complement[d, #] != {}, Complement[d, #][[1]], While[Nand[Mod[#[[-1]], p] != 0, FreeQ[#, p #[[-1]] ] ], p = NextPrime@ p]; p #[[-1]] ] ] ] &, {1}, 83]] (* Michael De Vlieger, May 23 2018 *)
PROG
(PARI)
A209229(n) = (n && !bitand(n, n-1));
A303767(n) = if(!n, n, if(A209229(n), n+A303767(n-1), A053644(n)+A303767(n-A053644(n)-1))); \\ Program based on new recurrence added May 06 2018
(PARI)
up_to = (2^7)-1;
A006519(n) = (2^valuation(n, 2));
A019565(n) = {my(j, v); factorback(Mat(vector(if(n, #n=vecextract(binary(n), "-1..1")), j, [prime(j), n[j]])~))}; \\ From A019565
A048675(n) = { my(f = factor(n)); sum(k=1, #f~, f[k, 2]*2^primepi(f[k, 1]))/2; };
v303767 = vector(up_to);
m303768 = Map();
w=1; for(n=1, up_to, s = Set([]); for(m=1, w, if((bitor(w, m)==w) && !mapisdefined(m303768, m), s = setunion(Set([A019565(m)]), s))); if(length(s)>0, w = A048675(vecmin(s)), b=A006519(1+w); while(bitand(w, b) || mapisdefined(m303768, w+b), b <<= 1); w += b); v303767[n] = w; mapput(m303768, w, n));
A303767(n) = if(!n, n, v303767[n]);
A303768(n) = if(!n, n, mapget(m303768, n));
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Antti Karttunen, May 02 2018
EXTENSIONS
Name replaced with an equivalent, but simpler definition by Antti Karttunen, May 06 2018
STATUS
approved