A303762 -id:A303762 - cp's OEIS frontend

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

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

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

Original entry on oeis.org

2, 6, 15, 210, 231, 6006, 4641, 176358, 119301, 6919458, 4663113, 345070362, 228191691, 19624485426, 11248180671, 1192307151126, 748362999111, 91300285891542, 51839992836723, 7361278982814666, 4010248998100527, 633619341699883266, 360208255897878843, 64117069549822434054, 37465998471884193393

Offset: 1

Antti Karttunen, May 05 2018

nonn

It seems that A002110(2n+1)/a(2n+1) = A066205(n).

Cf. A002110, A066205, A302774, A303762.

PARI
```
\\ See program in A302774.
```

a(n) = A303762(A302774(n)).

A303749 First differences of A302774; Number of terms in A303762 that have prime(n) as their largest prime factor (A006530).

Original entry on oeis.org

1, 2, 4, 7, 16, 19, 52, 55, 160, 163, 484, 487, 1456, 1459, 4372, 4375, 13120, 13123, 39364, 39367, 118096, 118099, 354292, 354295

Offset: 1

Antti Karttunen, May 05 2018

nonn

For n >= 1, the difference A000079(n-1) - a(n): 0, 0, 0, 1, 0, 13, 12, 73, 96, 349, 540, 1561, 2640, 6733, 12012, 28393, 52416, 117949, 222780, 484921, 930480, 1979053, 3840012, ..., indicates how many squarefree numbers A303762 misses in each round. The first of these is 70 missed at the round 4.

The first differences of these terms is: 1, 2, 3, 9, 3, 33, 3, 105, 3, 321, 3, 969, 3, 2913, 3, 8745, 3, 26241, 3, 78729, 3, 236193, 3, ... which after the first two initial terms seem to be an interleaving of sequences A010701 and A036543.

Cf. A010701, A036543, A302774, A303762.

a(n) = A302774(n+1) - A302774(n).

A303760 Divisor-or-multiple permutation of squarefree numbers: a(0) = 1, and for n >= 1, a(n) is either the least 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, 7, 14, 42, 21, 105, 35, 70, 770, 11, 22, 66, 33, 165, 55, 110, 330, 2310, 77, 154, 462, 231, 1155, 385, 5005, 13, 26, 78, 39, 195, 65, 130, 390, 2730, 91, 182, 546, 273, 1365, 455, 910, 10010, 143, 286, 858, 429, 2145, 715, 1430, 4290, 30030, 1001, 2002, 6006, 3003, 15015, 255255, 17, 34, 102, 51, 255, 85, 170, 510, 3570, 119

Offset: 0

Antti Karttunen, May 02 2018

nonn

Each a(n+1) is either a divisor or a multiple of a(n).
If a(n+1) > a(n), then A001222(a(n+1)) = 1 + A001222(a(n)).
From Antti Karttunen, May 23 2018: (Start)
For n >= 1, A006530(a(n)) = A000040(A070939(n)), thus the greatest prime dividing n, or equally, its index (A061395), is monotonic and follows the length of binary representation of n. This follows by induction on the size of the binary representation of n, and the fact that the "least possible unused divisor" part of a greedy rule can find all the unused divisors of A002110(k) before the next larger prime A000040(1+k) is needed as a factor.
For n >= 1, a((2^k)+1) = A000040(k+1), that is, after the first term with the next larger prime factor, which always occurs at 2^k, the next term is that prime itself, which is prime(k+1).
(A) For r in range 1 .. (2^(k-1)), a((2^k)+r) = A000040(k+1) * a(r-1), and prime A000040(k) is not present in the factorization. Because we cannot divide prime(k+1) out, as that would give a term already encountered, and because every term in this range has it as a largest prime factor, the relative magnitude-wise order of the terms in this range follows the relative magnitude-wise order of terms in a(0) .. a((2^(k-1))-1).
(B) For r in range (2^(k-1))+1 .. (2^k)-1, a((2^k)+r) = A000040(k+1) * a(r-1), and prime A000040(k) is present in the factorization.
Now it might be case that prime(k) > a product m of some subset of primes prime(k-1) .. prime(1). Even though the algorithm in those cases "would like" to divide by prime(k) instead of dividing by that product m, because then the divisor would be smaller, it cannot, because dividing by prime(k) (or by any other divisor containing it) would give an already used term.
(End)

			From _Michael De Vlieger_, May 23 2018: (Start)
Table below shows the initial 32 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       .      ...1          7
  10       2      1..1         14
  11       3      11.1         42
  12       .      .1.1         21
  13       5      .111        105
  14       .      ..11         35
  15       2      1.11         70
  16      11      1.111       770
  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       .      ...11        77
  27       2      1..11       154
  28       3      11.11       462
  29       .      .1.11       231
  30       5      .1111      1155
  31       .      ..111       385
  ... (End)

Antti Karttunen, Table of n, a(n) for n = 0..16383
Michael De Vlieger, Patterns in the multiplicities of prime divisors of terms m in A303760.
Michael De Vlieger, Image of multiplicities of distinct prime divisors of first 1024 terms, vertical axis increases downward, horizontal axis increases rightward and exaggerated 20 x.

Cf. A005117, A019565, A303767, A303771.

Cf. also A303761, A303762 (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}, 71] (* Michael De Vlieger, May 23 2018 *)

up_to = 2^7;
A053669(n) = forprime(p=2, , if (n % p, return(p))); \\ From A053669
v303760 = vector(up_to);
m_inverses = Map();
prev=1; for(n=1,up_to,fordiv(prev,d,if(!mapisdefined(m_inverses,d),v303760[n] = d;mapput(m_inverses,d,n);break)); if(!v303760[n], apu = prev; while(mapisdefined(m_inverses,try = prev*A053669(apu)), apu *= A053669(apu)); v303760[n] = try; mapput(m_inverses,try,n)); prev = v303760[n]);
A303760(n) = v303760[n+1];

a(n) = A019565(A303767(n)).
a(n) = A019565(A052331(A303771(n))).
A052330(A048675(a(n))) = A303771(n).

A303761 Divisor-or-multiple permutation of squarefree numbers: a(0) = 1, and for n >= 1, a(n) is either the least divisor of a(n-1) not already present, or (if all divisors already used), a(n) is obtained by iterating the map x -> x*A053669(x), starting from x = a(n-1), until x is found which is not already present in the sequence.

Original entry on oeis.org

1, 2, 6, 3, 30, 5, 10, 210, 7, 14, 42, 21, 2310, 11, 22, 66, 33, 330, 15, 30030, 13, 26, 78, 39, 390, 65, 130, 2730, 35, 70, 510510, 17, 34, 102, 51, 510, 85, 170, 3570, 105, 9699690, 19, 38, 114, 57, 570, 95, 190, 3990, 133, 266, 798, 399, 43890, 55, 110, 223092870, 23, 46, 138, 69, 690, 115, 230, 4830, 161, 322, 966, 483, 53130, 77

Offset: 0

Antti Karttunen, May 02 2018

nonn

Each a(n+1) is either a divisor or a multiple of a(n).
The primorials (A002110) occur in ascending order, in positions given by A300829, and each is then followed by the least unused term up to that point. For n = 2 .. 79 this is the highest prime factor of the said primorial, but note that for A300829(80) = 4965, a(4965) = A002110(80), but a(4966) = 407 = 11*37, instead of prime(80) = 409. Note that 409 occurs at a(5043), where 5043 = 1+A300829(81).
For example, 11 comes after a(A300829(5)) = a(12) = 2310 = 2*3*5*7*11, and all squarefree numbers < 11: {1, 2, 3, 5, 6, 7, 10} occur before a(13).

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

Cf. A005117, A019565, A053669, A300829 (gives the positions of records), A303765.

Cf. also A303751, A303760, A303762.

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

a(n) = A019565(A303765(n)).
For n >= 0, a(A300829(n)) = A002110(n) [primorials are the records].
For n = 2 .. 79, a(1+A300829(n)) = A000040(n).

A303769 a(0) = 0, a(n+1) is either the largest number obtained from a(n) by toggling a single 1-bit off (to 0) 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 a single 0-bit on (to 1). In both cases the bit to be toggled is the rightmost possible that results yet an unencountered number.

Original entry on oeis.org

0, 1, 3, 2, 6, 4, 5, 7, 15, 14, 12, 8, 9, 11, 10, 26, 24, 16, 17, 19, 18, 22, 20, 21, 23, 31, 30, 28, 29, 25, 27, 59, 58, 56, 48, 32, 33, 35, 34, 38, 36, 37, 39, 47, 46, 44, 40, 41, 43, 42, 106, 104, 96, 64, 65, 67, 66, 70, 68, 69, 71, 79, 78, 76, 72, 73, 75, 74, 90, 88, 80, 81, 83, 82, 86, 84, 85, 87, 95, 94, 92, 93, 89, 91, 123, 122, 120, 112, 113, 97, 99

Offset: 0

Antti Karttunen, May 03 2018, with more direct definition from David A. Corneth, May 05 2018

The original, but now conjectural, alternative 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 maximal 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.
The above construction is otherwise identical to that of A303767, except that we choose k_i with the maximal instead of minimal value of A019565.
In contrast to A303767, this sequence is not surjective (and thus not a permutation of nonnegative integers). The first missing term is 13 = A048675(70). See also comments in A303762, A303749 and A302775.
From David A. Corneth, May 05 2018: (Start)
Another description: a(0) = 0. a(n + 1) is the largest a(n) - 2^j > 0 that's not already in the sequence. If no such value exists, a(n + 1) is the least a(n) + 2^j not already in the sequence.
Using this definition we can prove that 13 isn't in the sequence. (End)
The equivalence of these definitions is still conjectural. The official definition of this sequence follows the latter one. - Antti Karttunen, Jun 08 2018

Antti Karttunen, Table of n, a(n) for n = 0..26232
Index entries for sequences related to binary expansion of n

Cf. A000120, A019565, A048675, A302774, A302775, A303749, A303762, A304749 (terms shown in base-2).

Cf. A303767 (a variant).

Nest[Append[#1, Min@ Select[{#2, #3, 2^IntegerLength[Last@ #1, 2] + Last@ #1}, IntegerQ]] & @@ Function[{a, d}, {a, SelectFirst[Sort@ Map[FromDigits[ReplacePart[d, First@ # -> 1], 2] &, Position[d, 0]], FreeQ[a, #] &], SelectFirst[Sort[#, Greater] &@ Map[FromDigits[ReplacePart[d, First@ # -> 0], 2] &, Position[d, 1]], FreeQ[a, #] &]}] @@ {#, IntegerDigits[Last@ #, 2]} &, {0}, 90] (* Michael De Vlieger, Jun 11 2018 *)

prepare_v303769(up_to) = { my(v = vector(up_to), occurred = Map(), prev=0, b); mapput(occurred,0,0); for(n=1,up_to, b=1; while(b<=prev, if(bitand(prev,b) && !mapisdefined(occurred,prev-b), v[n] = prev-b; break, b <<= 1)); if(!v[n], b=1; while(bitand(prev,b) || mapisdefined(occurred,prev+b), b <<= 1); v[n] = prev+b); mapput(occurred,prev = v[n],n)); (v); };
v303769 = prepare_v303769(16384);
A303769(n) = if(!n,n,v303769[n]); \\ Antti Karttunen, Jun 08 2018

a(n) = A048675(A303762(n)). [The original definition, now conjectured]
For n >= 0, A007088(a(n)) = A304749(n).
From David A. Corneth, May 05 2018: (Start)
The number of ones in the binary expansion of a(n) and a(n + 1) differ by 1. So A000120(a(n)) = A000120(a(n + 1)) +- 1. Furthermore, a(n + 1) <= 3 * a(n).
The number of binary digits of a(n + 1) is 0 or 1 more than the number of binary digits of a(n). So A070939(a(n + 1)) = A070939(a(n)) + 0 or 1. (End)

cp's OEIS Frontend

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

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

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Formula

A303749 First differences of A302774; Number of terms in A303762 that have prime(n) as their largest prime factor (A006530).

Views

Author

Keywords

Comments

Crossrefs

Formula

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula