A303763 -id:A303763 - cp's OEIS frontend

A303767 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.

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, 24, 25, 27, 26, 30, 28, 60, 32, 33, 35, 34, 38, 36, 37, 39, 47, 40, 41, 43, 42, 46, 44, 45, 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

Offset: 0

Antti Karttunen, May 02 2018

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)

			From _Michael De Vlieger_, May 23 2018: (Start)
Table below shows the initial 17 terms at right. First column is index n,
second shows "." if A303760(n) = largest divisor of A303760(n-1), or factor p.
   n     p\d  m=A303760(n)  A054841(m)    a(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)

Cf. A303768 (inverse), A304747 (terms shown in base-2).
Cf. A006519, A019565, A048675, A303760, A303771.
Cf. also A303763, A303765, A303769, A303775, A304083 (similar sequences).

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

A209229(n) = (n && !bitand(n,n-1));
A053644(n) = { my(k=1); while(k<=n, k<<=1); (k>>1); }; \\ From A053644
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

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

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
a(n) = A048675(A303760(n)).
a(n) = A052331(A303771(n)).
For all n >= 1, A000523(a(n)) = A000523(n), A007088(a(n)) = A304747(n).

Name replaced with an equivalent, but simpler definition by Antti Karttunen, May 06 2018

A303765 Permutation of nonnegative integers: a(n) = A048675(A303761(n)); see comments for an equivalent alternative description.

Original entry on oeis.org

0, 1, 3, 2, 7, 4, 5, 15, 8, 9, 11, 10, 31, 16, 17, 19, 18, 23, 6, 63, 32, 33, 35, 34, 39, 36, 37, 47, 12, 13, 127, 64, 65, 67, 66, 71, 68, 69, 79, 14, 255, 128, 129, 131, 130, 135, 132, 133, 143, 136, 137, 139, 138, 159, 20, 21, 511, 256, 257, 259, 258, 263, 260, 261, 271, 264, 265, 267, 266, 287, 24, 25, 27, 26, 1023, 512, 513, 515, 514, 519, 516, 517, 527

Offset: 0

Antti Karttunen, May 02 2018

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 cumulatively filling the successive vacant bits of a(n-1) from the least significant end of its binary representation (by toggling 0's to 1's, possibly also one or more leading zeros).
Shares with permutations like A003188, A006068, A300838, A302846, A303763, and A303767 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.
A300829 gives the positions of records (terms of A000225 in ascending order), that for cases n=2..79 are followed by 2^(n-1).

			For a(2), a(1) = 1, and the only subset mask (a number k for which bitor(k,1) = k) is 1 itself, already present, so we start toggling 0's to 1's with binary expansion "...00001" of 1, and we get "11" (= binary representation of 3), and 3 is not yet present, thus a(2) = 3.
For a(3), previous a(2) = 3, "...011" in binary, and "10" (= 2) is the least and only submask that is not already present, thus a(3) = 2.
For a(4), previous = 2, "...010" in binary, and there are no submasks that are not already used, thus we start toggling 0's to 1's from the right, and "11" (3) is already present, but "111" (7) is not, thus a(4) = 7.
For a(5), previous = 7, with seven submasks "1", "10", "11", "100", "101", "110", "111" (binary representations for 1 - 7), and of these "100", "101", "110" (4, 5 and 6) are not yet present. A019565(4) = 5, A019565(5) = 10 and A019565(6) = 15, so we choose the first one, thus a(5) = 4.
For a(6), previous = 4, "..0100" in binary, and no submasks that wouldn't have been already used, thus by toggling from the right, we first obtain "...0101" = 5, which is still free, so a(6) = 5.
For a(7), previous = 5, "..0101" in binary, and no submasks that would be free (both 1 and 4 are already present), thus by toggling from the right, we first obtain "...0111" = 7, which also has been used, so we continue filling the zeros, to next obtain "...1111" = 15, which is still free, so a(7) = 15.
For a(8), previous = 15, "..1111" in binary, and the submasks not used are "110" = 6, "1000" = 8, "1001" = 9, "1010" = 10, "1011" = 11, "1100" = 12, "1101" = 13 and "1110" = 14. Applying A019565 to these numbers, A019565(8) = 7 gives the smallest value, thus a(8) = 8.

Cf. A303766 (inverse).
Cf. A006519, A019565, A048675, A303761.
Cf. A303763, A303767 (variants).
Cf. A300829 (positions of records).

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; };
v303765 = vector(up_to);
m303766 = Map();
w=1; for(n=1,up_to,s = Set([]); for(m=1,w, if((bitor(w,m)==w) && !mapisdefined(m303766,m), s = setunion(Set([A019565(m)]),s))); if(length(s)>0, w = A048675(vecmin(s)), while(mapisdefined(m303766,w), w += A006519(1+w))); v303765[n] = w; mapput(m303766,w,n));
A303765(n) = if(!n,n,v303765[n]);
A303766(n) = if(!n,n,mapget(m303766,n));

a(n) = A048675(A303761(n)).

For all n >= 0, A019565(a(n)) = A303761(n).

A304083 Permutation of nonnegative integers: Minimal subset/superset bitmask transform of A054429.

Original entry on oeis.org

0, 1, 3, 2, 7, 6, 4, 5, 15, 14, 12, 8, 13, 9, 11, 10, 31, 30, 28, 24, 16, 29, 25, 17, 27, 26, 18, 23, 22, 20, 21, 63, 19, 59, 58, 56, 48, 32, 62, 60, 52, 36, 61, 57, 49, 33, 55, 54, 50, 34, 51, 35, 47, 46, 44, 40, 45, 41, 43, 42, 127, 53, 37, 39, 38, 126, 124, 120, 112, 96, 64, 125, 121, 113, 97, 65, 123, 122, 114, 98, 66, 119, 118, 116, 100, 68, 117, 101

Offset: 0

Antti Karttunen, May 06 2018

In "minimal subset/superset bitmask 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) = A054429(n).

Shares with permutations like A003188, A006068, A163252, A300838, A302846, A303763, A303765, A303767, A303773 and A303775 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. Note that A303767 is obtained when the same transform is applied to A001477, and A303775 when it is applied to A193231.

			After a(3) = 2, "10" in binary, there are no submasks that wouldn't have been used, so one selects from supermasks h_i = "110" (6), "111" (7), "1010" (10), "1011" (11), "1110" (14), "1111" (15), "10010" (18), "10011" (19), etc. that one for which A054429(h_i) is minimized, which happens to be at 6 (as A054429(6) = 5, but A054429(7) = 4, and for n >= 8, A054429(n) >= 8), thus a(4) = 7.
After a(4) = 7, "111" in binary, the submasks "1", "10", and "11" (1-3) are already present in sequence, while submasks "100", "101", "110" (4-6) are not present, and because A054429 is minimized on these three at 6, a(5) = 6.

Cf. A304084 (inverse).
Cf. A054429.
Cf. also A303767, A303775, A304085, A304087, A304088, A304089.

allocatemem(2^30);
default(parisizemax,2^31);
up_to = (2^17)+2;
A054429(n) = ((3<<#binary(n\2))-n-1);
find_minimal_submask_for_A054429(n,m_inverses) = { my(minval=0,minmask=0); for(m=1,n,if((bitor(m,n)==n) && !mapisdefined(m_inverses,m) && (!minval || (A054429(m) < minval)), minval = A054429(m); minmask = m)); (minmask); };
find_minimal_supermask_for_A054429(n,m_inverses) = { my(minval=0,minmask=0); for(m=1,(1<<(1+#binary(n)))-1,if((bitand(m,n)==n) && !mapisdefined(m_inverses,m) && (!minval || (A054429(m) < minval)), minval = A054429(m); minmask = m)); (minmask); };
v304083 = vector(up_to);
m304084 = Map();
w=1; for(n=1,up_to,s = Set([]); if((submask = find_minimal_submask_for_A054429(w,m304084)), w = submask, w = find_minimal_supermask_for_A054429(w,m304084)); v304083[n] = w; mapput(m304084,w,n));
A304083(n) = if(!n,n,v304083[n]);
A304084(n) = if(!n,n,mapget(m304084,n));

Derived sequences:
A052330(a(n)) = A304085(n).
A019565(a(n)) = A304087(n).
A000120(a(n)) = A304089(n).

A303775 Permutation of nonnegative integers: Minimal subset/superset bitmask transform of Blue code, A193231.

Original entry on oeis.org

0, 1, 3, 2, 6, 4, 5, 7, 15, 14, 12, 8, 13, 9, 11, 10, 30, 16, 17, 19, 18, 23, 20, 21, 31, 22, 54, 50, 48, 32, 51, 49, 33, 55, 53, 52, 36, 60, 28, 24, 29, 25, 27, 26, 63, 61, 57, 56, 40, 62, 58, 34, 59, 35, 39, 38, 46, 44, 45, 37, 47, 41, 43, 42, 106, 64, 85, 84, 80, 86, 82, 66, 87, 81, 65, 83, 67, 91, 90, 88, 72, 89, 73, 95, 94, 92, 68, 93, 69

Offset: 0

Antti Karttunen, May 05 2018

Shares with permutations like A003188, A006068, A163252, A300838, A302846, A303763, A303765, A303767, A303773 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. Note that A303767 is obtained when the same transform is applied to A001477, and A304083 when it is applied to A054429.

			After a(3) = 2, "10" in binary, there are no submasks that wouldn't have been used, so one selects from supermasks h_i = "110" (6), "111" (7), "1010" (10), "1011" (11), "1110" (14), "1111" (15), "10010" (18), "10011" (19), etc. that one for which A193231(h_i) is minimized, which happens to be at 6 (as A193231(6) = 6, but A193231(7) = 7, and for n >= 8, A193231(n) >= 8), thus a(4) = 6.
After a(4) = 6, "110" in binary, the submask "10" (2) is already present in sequence, while submask "100" (4) is only one which is not present, thus 4 is selected to be the value of a(5).
After a(8) = 15, "1111" in binary, none of the submasks "1000" (8), "1001" (9), "1010" (10), "1011" (11), "1100" (12), "1101" (13) or "1110" (14) are present, and as A193231 obtains its minimum value in the range [8 .. 14] at 14 (A193231(14) = 9), we have a(9) = 14.

Cf. A303776 (inverse).
Cf. A193231, A303778, A303779, A303780.
Cf. also A303767, A304083.

up_to = (2^18)+2;
A193231(n) = { my(x='x); subst(lift(Mod(1, 2)*subst(Pol(binary(n), x), x, 1+x)), x, 2) }; \\ From A193231
v303775 = vector(up_to);
m303776 = Map();
find_minimal_submask_for_A193231(n,m_inverses) = { my(minval=0,minmask=0); for(m=1,n,if((bitor(m,n)==n) && !mapisdefined(m_inverses,m) && (!minval || (A193231(m) < minval)), minval = A193231(m); minmask = m)); (minmask); };
find_minimal_supermask_for_A193231(n,m_inverses) = { my(minval=0,minmask=0); for(m=1,(1<<(1+#binary(n)))-1,if((bitand(m,n)==n) && !mapisdefined(m_inverses,m) && (!minval || (A193231(m) < minval)), minval = A193231(m); minmask = m)); (minmask); };
w=1; for(n=1,up_to,s = Set([]); if((submask = find_minimal_submask_for_A193231(w,m303776)), w = submask, w = find_minimal_supermask_for_A193231(w,m303776)); v303775[n] = w; mapput(m303776,w,n));
A303775(n) = if(!n,n,v303775[n]);
A303776(n) = if(!n,n,mapget(m303776,n));

Derived sequences:
A019565(a(n)) = A303778(n).
A000120(a(n)) = A303780(n).

A303773 Permutation of nonnegative integers constructed with a greedy algorithm producing either-subset-or-superset-mask type of walk in binary lattice (see comments for the exact definition).

Original entry on oeis.org

0, 1, 3, 2, 6, 4, 5, 7, 15, 11, 10, 8, 9, 13, 12, 14, 30, 22, 20, 16, 17, 19, 18, 26, 24, 25, 27, 31, 23, 21, 29, 28, 60, 44, 40, 32, 33, 35, 34, 38, 36, 37, 39, 47, 41, 43, 42, 46, 62, 58, 50, 48, 49, 51, 55, 53, 52, 54, 118, 82, 66, 64, 65, 67, 71, 69, 68, 70, 78, 74, 72, 73, 75, 79, 77, 76, 92, 88, 80, 81, 83, 87, 85, 84, 86, 94, 90, 91, 89, 93, 95, 127

Offset: 0

Antti Karttunen, May 05 2018

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 A003961(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, A163252, A300838, A302846, A303763, A303765, A303767 and A303775 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, in this case always only a single bit), 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.

Cf. A303774 (inverse).
Cf. A303770.
Cf. A303763, A303765, A303767, A303775 for similar constructions.

up_to = (2^18)-1;
A006519(n) = (2^valuation(n, 2));
A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ From A003961
A064989(n) = {my(f); f = factor(n); if((n>1 && f[1,1]==2), f[1,2] = 0); for (i=1, #f~, f[i,1] = precprime(f[i,1]-1)); factorback(f)};
v303773 = vector(up_to);
m303774 = Map();
w=1; for(n=1,up_to,s = Set([]); for(m=1,w, if((bitor(w,m)==w) && !mapisdefined(m303774,m), s = setunion(Set([A003961(m)]),s))); if(length(s)>0, w = A064989(vecmin(s)), b=A006519(1+w); while(bitand(w,b) || mapisdefined(m303774,w+b), b <<= 1); w += b); v303773[n] = w; mapput(m303774,w,n));
A303773(n) = if(!n,n,v303773[n]);
A303774(n) = if(!n,n,mapget(m303774,n));

For all n >= 0, A019565(a(n)) = A303770(n).

cp's OEIS Frontend

A303764 Inverse permutation to A303763.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A303767 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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A303765 Permutation of nonnegative integers: a(n) = A048675(A303761(n)); see comments for an equivalent alternative description.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A304083 Permutation of nonnegative integers: Minimal subset/superset bitmask transform of A054429.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A303775 Permutation of nonnegative integers: Minimal subset/superset bitmask transform of Blue code, A193231.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A303773 Permutation of nonnegative integers constructed with a greedy algorithm producing either-subset-or-superset-mask type of walk in binary lattice (see comments for the exact definition).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula