%I #51 Jun 07 2018 22:11:07

%S 0,1,3,2,6,4,5,7,15,8,9,11,10,14,12,13,29,16,17,19,18,22,20,21,23,31,

%T 24,25,27,26,30,28,60,32,33,35,34,38,36,37,39,47,40,41,43,42,46,44,45,

%U 61,48,49,51,50,54,52,53,55,63,56,57,59,58,62,126,64,65,67,66,70,68,69,71,79,72,73,75,74,78,76,77,93,80,81

%N May code of n: a(0) = 0, and for n > 0, if n = 2^k, a(n) = n + a(n-1), otherwise, when n = 2^k + r (with 0 < r < 2^k), then a(n) = 2^k + a(r-1); see comments for equivalent alternative descriptions.

%C 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.

%C The original, equivalent definition is:

%C 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.

%C 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.

%C 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.

%C From _Antti Karttunen_, May 23 2018: (Start)

%C Outline of the proof that the definition involving A019565 is equivalent to the recurrent formula:

%C 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.

%C 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.

%C 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.

%C (End)

%H Antti Karttunen, <a href="/A303767/b303767.txt">Table of n, a(n) for n = 0..16383</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%F a(0) = 0, and for n > 0, if n = 2^k, a(n) = n + a(n-1), otherwise, when n = 2^k + r (with 0 < r < 2^k), then a(n) = 2^k + a(r-1). \\ _Antti Karttunen_, May 06 2018

%F a(n) = A048675(A303760(n)).

%F a(n) = A052331(A303771(n)).

%F For all n >= 1, A000523(a(n)) = A000523(n), A007088(a(n)) = A304747(n).

%e From _Michael De Vlieger_, May 23 2018: (Start)

%e Table below shows the initial 17 terms at right. First column is index n,

%e second shows "." if A303760(n) = largest divisor of A303760(n-1), or factor p.

%e n p\d m=A303760(n) A054841(m) a(n)

%e -------------------------------------------

%e 0 . 1 0 0

%e 1 2 2 1 1

%e 2 3 6 11 3

%e 3 . 3 10 2

%e 4 5 15 110 6

%e 5 . 5 100 4

%e 6 2 10 101 5

%e 7 3 30 111 7

%e 8 7 210 1111 15

%e 9 . 7 1000 8

%e 10 2 14 1001 9

%e 11 3 42 1011 11

%e 12 . 21 1010 10

%e 13 5 105 1110 14

%e 14 . 35 1100 12

%e 15 2 70 1101 13

%e 16 11 770 11101 29

%e ... (End)

%t 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 *)

%o (PARI)

%o A209229(n) = (n && !bitand(n,n-1));

%o A053644(n) = { my(k=1); while(k<=n, k<<=1); (k>>1); }; \\ From A053644

%o 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

%o (PARI)

%o up_to = (2^7)-1;

%o A006519(n) = (2^valuation(n, 2));

%o A019565(n) = {my(j,v); factorback(Mat(vector(if(n, #n=vecextract(binary(n), "-1..1")), j, [prime(j), n[j]])~))}; \\ From A019565

%o A048675(n) = { my(f = factor(n)); sum(k=1, #f~, f[k, 2]*2^primepi(f[k, 1]))/2; };

%o v303767 = vector(up_to);

%o m303768 = Map();

%o 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));

%o A303767(n) = if(!n,n,v303767[n]);

%o A303768(n) = if(!n,n,mapget(m303768,n));

%Y Cf. A303768 (inverse), A304747 (terms shown in base-2).

%Y Cf. A006519, A019565, A048675, A303760, A303771.

%Y Cf. also A303763, A303765, A303769, A303775, A304083 (similar sequences).

%K nonn,base

%O 0,3

%A _Antti Karttunen_, May 02 2018

%E Name replaced with an equivalent, but simpler definition by _Antti Karttunen_, May 06 2018