A336460 -id:A336460 - cp's OEIS frontend

A305801 Lexicographically earliest infinite sequence such that a(i) = a(j) => f(i) = f(j), where f(n) = 0 if n is an odd prime, with f(n) = n for all other n.

1, 2, 3, 4, 3, 5, 3, 6, 7, 8, 3, 9, 3, 10, 11, 12, 3, 13, 3, 14, 15, 16, 3, 17, 18, 19, 20, 21, 3, 22, 3, 23, 24, 25, 26, 27, 3, 28, 29, 30, 3, 31, 3, 32, 33, 34, 3, 35, 36, 37, 38, 39, 3, 40, 41, 42, 43, 44, 3, 45, 3, 46, 47, 48, 49, 50, 3, 51, 52, 53, 3, 54, 3, 55, 56, 57, 58, 59, 3, 60, 61, 62, 3, 63, 64, 65, 66, 67, 3, 68, 69, 70, 71, 72, 73, 74, 3, 75, 76, 77, 3, 78, 3, 79, 80

Offset: 1

Antti Karttunen, Jun 14 2018

nonn

The original name was: "Filter sequence for a(odd prime) = constant sequences", which stemmed from the fact that for all i, j, a(i) = a(j) => b(i) = b(j) for any sequence b that obtains a constant value for all odd primes A065091.
For example, we have for all i, j:
  a(i) = a(j) => A305800(i) = A305800(j),
  a(i) = a(j) => A007814(i) = A007814(j),
  a(i) = a(j) => A305891(i) = A305891(j) => A291761(i) = A291761(j).
There are several filter sequences "above" this one (meaning that they have finer equivalence class partitioning), for example, we have, for all i, j:
[where odd primes are further distinguished by]
  A305900(i) = A305900(j) => a(i) = a(j),   [whether p = 3 or > 3]
  A319350(i) = A319350(j) => a(i) = a(j),   [A007733(p)]
  A319704(i) = A319704(j) => a(i) = a(j),   [p mod 4]
  A319705(i) = A319705(j) => a(i) = a(j),   [A286622(p)]
  A331304(i) = A331304(j) => a(i) = a(j),   [parity of A000720(p)]
  A336855(i) = A336855(j) => a(i) = a(j).   [distance to the next larger prime]

Antti Karttunen, Table of n, a(n) for n = 1..100000

Cf. A000720, A065091, A305800, A305900.
Cf. A305900, A319350, A319704, A319705, A331304, A336855 (sequences with finer equivalence class partitioning).
Cf. A305800, A305890, A305891, A305896, A318500, A318888, A319346, A319347, A319349, A319701, A322591, A322809, A322810, A323078, A323367, A323082, A323369, A323370, A323371, A323374, A323400, A324401, A326199, A326201, A326203, A326203, A328470, A329608, A331174, A331730, A331301 (sequences with coarser equivalence class partitioning).
Cf. also A003602, A103391, A295300, A305795, A324400, A331300, A336460 (for similar constructions or similarly useful sequences).

Array[If[# <= 2, #, If[PrimeQ[#], 3, 2 + # - PrimePi[#]]] &, 105] (* Michael De Vlieger, Oct 18 2021 *)

A305801(n) = if(n<=2,n,if(isprime(n),3,2+n-primepi(n)));

a(1) = 1, a(2) = 2; for n > 2, a(n) = 3 for odd primes, and a(n) = 2+n-A000720(n) for composite n.

For n > 2, a(n) = 1 + A305800(n).

Name changed and Comment section rewritten by Antti Karttunen, Oct 17 2021

A336466 Fully multiplicative with a(p) = A000265(p-1) for any prime p, where A000265(k) gives the odd part of k.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 5, 1, 3, 3, 1, 1, 1, 1, 9, 1, 3, 5, 11, 1, 1, 3, 1, 3, 7, 1, 15, 1, 5, 1, 3, 1, 9, 9, 3, 1, 5, 3, 21, 5, 1, 11, 23, 1, 9, 1, 1, 3, 13, 1, 5, 3, 9, 7, 29, 1, 15, 15, 3, 1, 3, 5, 33, 1, 11, 3, 35, 1, 9, 9, 1, 9, 15, 3, 39, 1, 1, 5, 41, 3, 1, 21, 7, 5, 11, 1, 9, 11, 15, 23, 9, 1, 3, 9, 5, 1, 25, 1, 51, 3, 3

Offset: 1

Antti Karttunen, Jul 22 2020

For the comment here, we extend the definition of the second kind of Cunningham chain (see Wikipedia-article) so that also isolated primes for which neither (p+1)/2 nor 2p-1 is a prime are considered to be in singular chains, that is, in chains of the length one. If we replace one or more instances of any particular odd prime factor p in n with any odd prime q in such a chain, so that m = (q^k)*n / p^(e-k), where e is the exponent of p of n, and k <= e is the number of instances of p replaced with q, then it holds that a(m) = a(n), and by induction, the value stays invariant for any number of such replacements. Note also that A001222, but not necessarily A001221 will stay invariant in such changes.
For example, if some of the odd prime divisors p of n are in A005382, then replacing it with 2p-1 (i.e., the corresponding terms of A005383), gives a new number m, for which a(m) = a(n). And vice versa, the same is true for any of the prime divisors > 3 of n that are in A005383, then replacing any one of them with (p+1)/2 will not affect the result. For example, a(37*37*37) = a(19*37*73) = 729 as 37 is both in A005382 and in A005383.
a(n) = A053575(n) for squarefree n (A005117). - Antti Karttunen, Mar 16 2021

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537
Wikipedia, Cunningham chain

Cf. A000265, A003958, A005117, A005382, A005383, A053575, A329697, A333787, A335915, A336396, A336467, A336468, A339870, A339876 [= a(A122111(n))], A339903 [= a(A003961(n))], A340084 [= gcd(n-1, a(n))], A340085, A340086.

Cf. also A336460, A336470, A339974.

Array[Times @@ Map[If[# <= 2, 1, (# - 1)/2^IntegerExponent[# - 1, 2]] &, Flatten[ConstantArray[#1, #2] & @@@ FactorInteger[#]]] &, 105] (* Michael De Vlieger, Jul 24 2020 *)

A000265(n) = (n>>valuation(n,2));
A336466(n) = { my(f=factor(n)); prod(k=1,#f~,A000265(f[k,1]-1)^f[k,2]); };

a(n) = A000265(A003958(n)) = A000265(A333787(n)).
a(A000010(n)) = A336468(n) = a(A053575(n)).
A329697(a(n)) = A336396(n) = A329697(n) - A087436(n).
a(n) = A335915(n) / A336467(n). - Antti Karttunen, Mar 16 2021

A336470 Lexicographically earliest infinite sequence such that a(i) = a(j) => A336466(i) = A336466(j) and A336158(i) = A336158(j), for all i, j >= 1.

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 3, 1, 4, 2, 5, 2, 3, 3, 6, 1, 2, 4, 7, 2, 8, 5, 9, 2, 4, 3, 10, 3, 11, 6, 12, 1, 13, 2, 8, 4, 7, 7, 8, 2, 5, 8, 14, 5, 15, 9, 16, 2, 17, 4, 6, 3, 18, 10, 13, 3, 19, 11, 20, 6, 12, 12, 21, 1, 8, 13, 22, 2, 23, 8, 24, 4, 7, 7, 15, 7, 25, 8, 26, 2, 27, 5, 28, 8, 6, 14, 29, 5, 9, 15, 19, 9, 25, 16, 19, 2, 3, 17, 30, 4, 31, 6, 32, 3, 33

Offset: 1

Antti Karttunen, Jul 24 2020

nonn

Restricted growth sequence transform of the ordered pair [A336466(n), A336158(n)].
For all i, j:
  A336460(i) = A336460(j) => a(i) = a(j),
  a(i) = a(j) => A329697(i) = A329697(j),
  a(i) = a(j) => A336471(i) = A336471(j).

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A336158, A336466.

Cf. also A329697, A336160, A336471.

up_to = 65537;
rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,invec[i],i); outvec[i] = u; u++ )); outvec; };
A000265(n) = (n>>valuation(n,2));
A336466(n) = { my(f=factor(n)); prod(k=1,#f~,if(2==f[k,1],1,(A000265(f[k,1]-1))^f[k,2])); };
A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); };  \\ From A046523
A336158(n) = A046523(A000265(n));
Aux336470(n) = [A336466(n), A336158(n)];
v336470 = rgs_transform(vector(up_to, n, Aux336470(n)));
A336470(n) = v336470[n];

A336473 Lexicographically earliest infinite sequence such that a(i) = a(j) => A278222(i) = A278222(j) and A329697(i) = A329697(j), for all i, j >= 1.

Original entry on oeis.org

1, 1, 2, 1, 3, 2, 4, 1, 5, 3, 6, 2, 6, 4, 7, 1, 3, 5, 8, 3, 9, 6, 10, 2, 6, 6, 11, 4, 10, 7, 12, 1, 13, 3, 8, 5, 9, 8, 10, 3, 14, 9, 15, 6, 16, 10, 17, 2, 18, 6, 19, 6, 16, 11, 20, 4, 21, 10, 22, 7, 23, 12, 24, 1, 13, 13, 18, 3, 25, 8, 21, 5, 9, 9, 16, 8, 15, 10, 17, 3, 25, 14, 16, 9, 26, 15, 27, 6, 16, 16, 28, 10, 27, 17, 29, 2, 6, 18, 30, 6, 16, 19, 20, 6, 15

Offset: 1

Antti Karttunen, Jul 24 2020

Restricted growth sequence transform of the ordered pair [A278222(n), A329697(n)].

For all i, j: A336460(i) = A336460(j) => a(i) = a(j).

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A278222, A329697.

Cf. also A286622, A336394, A336460, A336470, A336471, A336472, A336474.

up_to = 65537;
rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,invec[i],i); outvec[i] = u; u++ )); outvec; };
A005940(n) = { my(p=2, t=1); n--; until(!n\=2, if((n%2), (t*=p), p=nextprime(p+1))); t };
A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); };  \\ From A046523
A278222(n) = A046523(A005940(1+n));
A329697(n) = if(!bitand(n,n-1),0,1+A329697(n-(n/vecmax(factor(n)[, 1]))));
Aux336473(n) = [A278222(n), A329697(n)];
v336473 = rgs_transform(vector(up_to, n, Aux336473(n)));
A336473(n) = v336473[n];

A336472 Lexicographically earliest infinite sequence such that a(i) = a(j) => A278222(i) = A278222(j) and A336466(i) = A336466(j), for all i, j >= 1.

Original entry on oeis.org

1, 1, 2, 1, 3, 2, 4, 1, 3, 3, 5, 2, 6, 4, 7, 1, 3, 3, 8, 3, 9, 5, 10, 2, 11, 6, 12, 4, 13, 7, 14, 1, 15, 3, 6, 3, 16, 8, 17, 3, 18, 9, 19, 5, 20, 10, 21, 2, 8, 11, 12, 6, 22, 12, 23, 4, 24, 13, 25, 7, 26, 14, 27, 1, 28, 15, 29, 3, 30, 6, 31, 3, 16, 16, 20, 8, 32, 17, 33, 3, 34, 18, 35, 9, 36, 19, 37, 5, 38, 20, 39, 10, 40, 21, 41, 2, 6, 8, 42, 11, 43, 12, 44, 6, 45

Offset: 1

Antti Karttunen, Jul 24 2020

nonn

Restricted growth sequence transform of the ordered pair [A278222(n), A336466(n)].

For all i, j: A336460(i) = A336460(j) => a(i) = a(j).

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A278222, A336466.

Cf. also A336162, A336460, A336470, A336471, A336473.

up_to = 65537;
rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,invec[i],i); outvec[i] = u; u++ )); outvec; };
A005940(n) = { my(p=2, t=1); n--; until(!n\=2, if((n%2), (t*=p), p=nextprime(p+1))); t };
A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); };  \\ From A046523
A278222(n) = A046523(A005940(1+n));
A000265(n) = (n>>valuation(n,2));
A336466(n) = { my(f=factor(n)); prod(k=1,#f~,if(2==f[k,1],1,(A000265(f[k,1]-1))^f[k,2])); };
Aux336472(n) = [A278222(n), A336466(n)];
v336472 = rgs_transform(vector(up_to, n, Aux336472(n)));
A336472(n) = v336472[n];

cp's OEIS Frontend

A305801 Lexicographically earliest infinite sequence such that a(i) = a(j) => f(i) = f(j), where f(n) = 0 if n is an odd prime, with f(n) = n for all other n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A336466 Fully multiplicative with a(p) = A000265(p-1) for any prime p, where A000265(k) gives the odd part of k.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A336470 Lexicographically earliest infinite sequence such that a(i) = a(j) => A336466(i) = A336466(j) and A336158(i) = A336158(j), for all i, j >= 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A336473 Lexicographically earliest infinite sequence such that a(i) = a(j) => A278222(i) = A278222(j) and A329697(i) = A329697(j), for all i, j >= 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A336472 Lexicographically earliest infinite sequence such that a(i) = a(j) => A278222(i) = A278222(j) and A336466(i) = A336466(j), for all i, j >= 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI