A303769 -id:A303769 - cp's OEIS frontend

A304749 A303769 shown in binary.

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

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.

Original entry on oeis.org

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

A303762 a(0) = 1, and for n >= 1, a(n) is either the largest divisor of a(n-1) not already present in the sequence, or (if all divisors already used), a(n-1) * {the least prime p such that p does not divide a(n-1) and p*a(n-1) is not already present}.

Original entry on oeis.org

1, 2, 6, 3, 15, 5, 10, 30, 210, 105, 35, 7, 14, 42, 21, 231, 77, 11, 22, 66, 33, 165, 55, 110, 330, 2310, 1155, 385, 770, 154, 462, 6006, 3003, 1001, 143, 13, 26, 78, 39, 195, 65, 130, 390, 2730, 1365, 455, 91, 182, 546, 273, 4641, 1547, 221, 17, 34, 102, 51, 255, 85, 170, 510, 3570, 1785, 595, 119, 238, 714, 357, 3927, 1309, 187, 374, 1122, 561, 2805, 935

Offset: 0

Antti Karttunen, May 03 2018

nonn

Each a(n+1) is either a divisor or a multiple of a(n).
The construction is otherwise like that of A303760, except here we choose the largest divisor instead of the smallest one. In contrast to A303760, this sequence is NOT permutation of A005117: 70 = A019565(13) is the first missing squarefree number. See also comments in A303769, A303749 and A302775.
Index of greatest prime factor of a(n) is monotonic and increments at n = {0, 1, 2, 4, 8, 15, 31, 50, 102, 157, 317, 480, 964, 1451, 2907, 4366, 8738, 13113, 26233, 39356, ...} - Michael De Vlieger, May 22 2018

			From _Michael De Vlieger_, May 23 2018: (Start)
Table below shows the initial 31 terms at right. First column is index n. Second shows "." if a(n) = largest divisor of a(n-1), or factor p. Third shows presence "1" or absence "." of prime k among prime divisors of a(n).
   n   p\d    MN(n)      a(n)
  ---------------------------
   0     .    .            1
   1     2    1            2
   2     3    11           6
   3     .    .1           3
   4     5    .11         15
   5     .    ..1          5
   6     2    1.1         10
   7     3    111         30
   8     7    1111       210
   9     .    .111       105
  10     .    ..11        35
  11     .    ...1         7
  12     2    1..1        14
  13     3    11.1        42
  14     .    .1.1        21
  15    11    .1.11      231
  16     .    ...11       77
  17     .    ....1       11
  18     2    1...1       22
  19     3    11..1       66
  20     .    .1..1       33
  21     5    .11.1      165
  22     .    ..1.1       55
  23     2    1.1.1      110
  24     3    111.1      330
  25     7    11111     2310
  26     .    .1111     1155
  27     .    ..111      385
  28     2    1.111      770
  29     .    1..11      154
  30     3    11.11      462
  31    13    11.111    6006
  ...  (End)

Antti Karttunen, Table of n, a(n) for n = 0..26232

Subset of A005117.
Cf. also A019565, A302774, A302775, A303749, A303769.
Cf. A303760, A303761 (variants).

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}, 75] (* Michael De Vlieger, May 22 2018 *)

default(parisizemax,2^31);
up_to = 2^14;
A053669(n) = forprime(p=2, , if (n % p, return(p))); \\ From A053669
v303762 = vector(up_to);
m_inverses = Map();
prev=1; for(n=1,up_to,fordiv(prev,d,if(!mapisdefined(m_inverses,(prev/d)),v303762[n] = (prev/d);mapput(m_inverses,(prev/d),n);break)); if(!v303762[n], apu = prev; while(mapisdefined(m_inverses,try = prev*A053669(apu)), apu *= A053669(apu)); v303762[n] = try; mapput(m_inverses,try,n)); prev = v303762[n]);
A303762(n) = v303762[n+1];

a(n) = A019565(A303769(n)). [Conjectured]

A302774 a(n) is the position of the first term in A303762 that has prime(n) as one of its prime factors.

Original entry on oeis.org

1, 2, 4, 8, 15, 31, 50, 102, 157, 317, 480, 964, 1451, 2907, 4366, 8738, 13113, 26233, 39356, 78720, 118087, 236183, 354282, 708574, 1062869

Offset: 1

Antti Karttunen, May 04 2018

nonn

Equivalently, a(n) is the position of the first term k in A303769 for which 1+A000523(k) = n.

The first differences A303749 indicate how many terms were produced in each round of A303762 before the algorithm started outputting numbers with next larger prime as their greatest prime factor.

Cf. A061395, A302775, A303749, A303762, A303769.

prev=0; for(n=0,2^16,if(1==((p2=A061395(A303762(n)))-prev),print1(n,", ")); prev=p2);

allocatemem(2^30);
default(parisizemax,2^31);
up_to = (2^25)+2;
A053669(n) = forprime(p=2, , if (n % p, return(p))); \\ From A053669
A061395(n) = if(1==n, 0, primepi(vecmax(factor(n)[, 1])));
m_inverses = Map();
q2 = 0; prev=1; for(n=1,up_to,found_it = 0; fordiv(prev,d,if(!mapisdefined(m_inverses,(prev/d)),found_it = (prev/d);mapput(m_inverses,(prev/d),n);break)); if(!found_it, apu = prev; while(mapisdefined(m_inverses,try = prev*A053669(apu)), apu *= A053669(apu)); found_it = try; mapput(m_inverses,try,n)); if((q1=A061395(found_it)) != q2, write("b302774.txt", q1, " ", n-1); write("b302775.txt", q1, " ", found_it)); prev = found_it; q2 = q1);

cp's OEIS Frontend

A304749 A303769 shown in binary.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

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

A303762 a(0) = 1, and for n >= 1, a(n) is either the largest divisor of a(n-1) not already present in the sequence, or (if all divisors already used), a(n-1) * {the least prime p such that p does not divide a(n-1) and p*a(n-1) is not already present}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A302774 a(n) is the position of the first term in A303762 that has prime(n) as one of its prime factors.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

PARI