A304747 -id:A304747 - 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

A304749 A303769 shown in binary.

Original entry on oeis.org

0, 1, 11, 10, 110, 100, 101, 111, 1111, 1110, 1100, 1000, 1001, 1011, 1010, 11010, 11000, 10000, 10001, 10011, 10010, 10110, 10100, 10101, 10111, 11111, 11110, 11100, 11101, 11001, 11011, 111011, 111010, 111000, 110000, 100000, 100001, 100011, 100010, 100110, 100100, 100101, 100111, 101111, 101110, 101100, 101000, 101001, 101011, 101010, 1101010, 1101000

Offset: 0

Antti Karttunen, May 23 2018

			The code can be constructed by the rule: a(n+1) is either the largest number obtained from a(n) by toggling one 1-bit off if no such number is yet in the sequence, otherwise the least number not yet in sequence that can be obtained from a(n) by toggling one 0-bit on. In both cases the bit to be toggled is the rightmost possible that results yet an unencountered code. Note that this code doesn't cover all binary sequences, for example 1101 is missing:
   0       0
   1       1
   2      11
   3      10
   4     110
   5     100
   6     101
   7     111
   8    1111
   9    1110
  10    1100
  11    1000
  12    1001
  13    1011
  14    1010
  15   11010
  16   11000
  17   10000
  18   10001
  19   10011
  20   10010
  21   10110
  22   10100
  23   10101
  24   10111
  25   11111
  26   11110
  27   11100
  28   11101
  29   11001
  30   11011
  31  111011
  32  111010
  33  111000
  34  110000
  35  100000
  36  100001
  37  100011
  38  100010
  39  100110
  40  100100
  41  100101
  42  100111
  43  101111
  44  101110
  45  101100
  46  101000
  47  101001
  48  101011
  49  101010
  50 1101010
  51 1101000
  52 1100000
  53 1000000

Index entries for sequences related to binary expansion of n

Cf. A007088, A303769.

Cf. also A304747.

a(n) = A007088(A303769(n)).

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI