A082449 -id:A082449 - cp's OEIS frontend

A056637 a(n) is the least prime of class n-, according to the Erdős-Selfridge classification of primes.

2, 11, 23, 47, 283, 719, 1439, 2879, 34549, 138197, 1266767, 14920303, 36449279, 377982107, 1432349099, 22111003847, 110874748763

Offset: 1

Robert G. Wilson v, Jan 31 2001

A prime p is in class 1- if p-1 has no prime factor larger than 3. If p-1 has other prime factors, p is in class (c+1)-, where c- is the largest class of its prime factors. See also A005109.
1432349099 < a(16) <= 25782283783.
a(18) <= 619108107719, a(19) <= 19811459447009, a(20) <= 152772264735359. These upper limits can be found by generating class (n+1)- primes from a list of n- class primes; if the latter is sufficiently complete, one can deduce that there is no smaller (n+1)- prime. - M. F. Hasler, Apr 05 2007

Cf. A005113, A005109, A005110, A005111, A005112, A081424, A081425, A081426, A081427, A081428, A081429, A081430.

Cf. A082449, A129246, A081640, A129248.

PrimeFactors[n_Integer] := Flatten[ Table[ #[[1]], {1}] & /@ FactorInteger[n]]; NextPrime[n_] := Block[{k = n + 1}, While[ !PrimeQ[k], k++ ]; k]; f[n_Integer] := Block[{m = n}, If[m == 0, m = 1, While[ IntegerQ[m/2], m /= 2]; While[ IntegerQ[m/3], m /= 3]]; Apply[Times, PrimeFactors[m] - 1]]; ClassMinusNbr[n_] := Length[NestWhileList[f, n, UnsameQ, All]] - 3; a = Table[0, {15}]; a[[1]] = 2; k = 5; Do[c = ClassMinusNbr[ k]; If[ a[[c]] == 0, a[[c]] = k]; k = NextPrime[k], {n, 3, 7223000}]; a

a(n+1) >= 2*a(n)+1, since a(n+1)-1 is even and must have a factor of class n- which is odd (n>1) and >= a(n). a(n+1) <= min { p = 2*k*a(n)+1 | k=1,2,3... such that p is prime }, since a(n) is a prime of class n-. - M. F. Hasler, Apr 05 2007

Extended by Robert G. Wilson v, Mar 20 2003
More terms from Don Reble, Apr 11 2003
a(16) and a(17) from M. F. Hasler, Apr 21 2007

A246497 Smallest k such that 9^^n is not congruent to 9^^(n-1) mod k, where 9^^n denotes the power tower 9^9^...^9 (in which 9 appears n times).

Original entry on oeis.org

3, 7, 23, 47, 283, 719, 1439, 2879, 34549, 138197, 1266767, 14619833, 36449279, 377982107, 1432349099

Offset: 1

Wayne VanWeerthuizen, Aug 27 2014

For general remarks regarding sequences of this type, see A246491.

This particular sequence shares all known terms with A082449. they might be identical.

Cf. A082449, A027763, A246491, A246492, A246493, A246494, A246495, A246496.

A019268 Let Dedekind's psi(m) = product of (p+1)p^(e-1) for primes p, where p^e is a factor of m. Iterating psi(m) eventually results in a number of form 2^a*3^b. a(n) is the smallest number that requires n steps to reach such a number.

Original entry on oeis.org

1, 5, 13, 37, 73, 673, 1993, 15013, 49681, 239233, 1065601, 8524807, 68198461, 545587687, 1704961513, 7811750017

Offset: 0

Jud McCranie

There is a remarkable and unexplained agreement: if 5 is dropped from the list, 2, 673, 1993 and 239233 are replaced by 1, 1021, 29173 and 532801, the result is sequence A005113 (least prime of class n+, according to the Erdős-Selfridge classification of primes).

A019269(a(n)) = n and A019269(m) != n for m < a(n). [Reinhard Zumkeller, Apr 12 2012]

Peter Giblin, "Primes and Programming - an Introduction to Number Theory with Computation", page 118.
R. K. Guy, "Unsolved Problems in Number Theory", section B41.

Cf. A005113, A082449.

import Data.List (elemIndex)
import Data.Maybe (fromJust)
a019268 = (+ 1) . fromJust . (`elemIndex` a019269_list)
-- Reinhard Zumkeller, Apr 12 2012

psi[m_] := ({pp, ee} = FactorInteger[m] // Transpose; If[Max[pp] == 3, m, Times @@ (pp+1)*Times @@ (pp^(ee-1))]); a[0] = 1; a[1] = 5; a[n_] := a[n] = For[k = a[n - 1] (* assuming monotony *), True, k++, If[Length @ FixedPointList[psi, k] == n+2, Return[k]]]; Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 0, 10}] (* Jean-François Alcover, Feb 19 2018 *)

More terms from Jud McCranie, Jan 15 1997

Initial element corrected by Reinhard Zumkeller, Apr 12 2012

A083647 For primes p: Number of steps to reach 2 when iterating f(p) = greatest prime divisor of p-1.

Original entry on oeis.org

0, 1, 1, 2, 2, 2, 1, 2, 3, 3, 2, 2, 2, 3, 4, 3, 4, 2, 3, 3, 2, 3, 3, 3, 2, 2, 2, 4, 2, 3, 3, 3, 2, 4, 3, 2, 3, 2, 4, 4, 4, 2, 3, 2, 3, 3, 3, 3, 4, 3, 4, 2, 2, 2, 1, 4, 4, 2, 4, 3, 5, 3, 2, 3, 3, 4, 3, 3, 5, 4, 3, 5, 3, 3, 3, 4, 3, 3, 2, 2, 3, 3, 4, 2, 3, 2, 3, 3, 4, 3, 5, 3, 2, 3, 4, 3, 4, 3, 4, 2, 3, 5, 4, 4, 3

Offset: 1

Klaus Brockhaus, May 01 2003

nonn

For smallest prime that requires n steps to reach 2 cf. A082449.

			59 is the 17th prime and takes four steps to reach 2 (59 -> 29 -> 7 -> 3 -> 2), so a(17) = 4.

Ruud H.G. van Tol, Table of n, a(n) for n = 1..10000

Cf. A006530, A023503, A082449.

Table[Length[NestWhileList[FactorInteger[#-1][[-1,1]]&,Prime[n], #!=2&]]-1,{n,110}] (* Harvey P. Dale, Feb 27 2012 *)

{forprime(p=2,571,q=p; c=0; while(q>2,fac=factor(q-1); q=fac[matsize(fac)[1],1]; c++); print1(c,","))}

A364332 a(n) = f(prime(n)), where f(2) = 0 and for an odd prime p, f(p) = max{f(q)+1: q ranges over all prime factors of p-1}.

Original entry on oeis.org

0, 1, 1, 2, 2, 2, 1, 2, 3, 3, 2, 2, 2, 3, 4, 3, 4, 2, 3, 3, 2, 3, 3, 3, 2, 2, 2, 4, 2, 3, 3, 3, 2, 4, 3, 2, 3, 2, 4, 4, 4, 2, 3, 2, 3, 3, 3, 3, 4, 3, 4, 3, 2, 2, 1, 4, 4, 2, 4, 3, 5, 3, 2, 3, 3, 4, 3, 3, 5, 4, 3, 5, 3, 3, 3, 4, 3, 3, 2, 2, 3, 3, 4, 2, 3, 3, 3, 3, 4, 3, 5, 4, 2, 3, 4, 3, 4, 3, 4

Offset: 1

Steven Lu, Jul 18 2023

nonn

This sequence is related to a problem about googology (see Zhihu).
There are three numbers named A, B and C, and initially A>1, and B=C=0.
Now take the following steps:
  Step 1. Let B=B+1, C=C+1.
  Step 2. Check if A is divisible by (B+1). If yes, go to Step 3; if no, go back to Step 1.
  Step 3. Let A=A/(B+1)*B^C.
  Step 4. Let B=0.
  Step 5. If A=1, then stop, otherwise go back to Step 1.
This program will always stop. When the program stops, C will be a very large number.
When Step 3 reached, B+1 will be the smallest prime factor of A, and this factor is eliminated while some smaller factors; i.e., factors of B, are added.
The properties of this problem rely on the prime factors of A. A can be described by the ordinal: O(A) = n_(k-1)*omega^(l_(k-1)) + ... + n_2*omega^(l_2) + n_1*omega^(l_1) + n_0 where A = 2^(n_0) * 3^(n_1) * 5^(n_2) * p(k)^(n_(k-1)). Every operation will monotonically decrease the ordinal.
Note that the exponential of omega in each term is l_k instead of k, and this is because the correspondence between prime factors and powers of omega is more complicated than "p(k+1) to omega^k".
When B+1=2, the increase of C is only 1, then every prime factor 2 corresponds ordinal 1, or omega^0. This agrees with a(p)=0 when p=2 in this sequence.
When B+1=3, any number of exponential of 2 can be increased, then every prime factor 3 corresponds ordinal omega.
When B+1=5, only the power of 2 can be increased as well, then prime factor 5 also corresponds omega.
When B+1=7, any number of exponentials of 2 and 3 can be both increased, then the corresponding ordinal is (1+omega)*omega=omega*omega=omega^2.
The rule is, the power of omega for a given prime number p equals the maximum among those for prime factors of (p-1), plus one.
This sequence is similar to but different from A083647, the difference begins at the 52nd term; i.e. for p=239. That is because 238=2*7*17 and a(7)=3>2=a(17) although 7<17.
From Jianing Song, Apr 28 2024: (Start)
a(n) is one less than the maximum length of a sequence d_0 = prime(n), d_1, ..., d_m = 2 such that d_i is a prime factor of d_{i-1} - 1. For example, for n = 52 (then prime(n) = 239), we have a(n) = 3 since that a sequence with maximum length is 239, 7, 3, 2. It is clear that a(n) >= A083647(n), as the latter takes d_i to be largest prime factor of d_{i-1} - 1.
Conjecture: the smallest prime p such that f(p) = m (namely a(primepi(p)) = m) is p = A082449(m). Verified for m <= 13. (End)

			For p=443, we have 442=2*13*17, and f(2)=0, f(13)=2, f(17)=1. The maximum among them is 2, so f(443)=3, or a(86)=3.

Jianing Song, Table of n, a(n) for n = 1..10000
Zhihu, Meitianli's answer to the question "Does my number exceed Graham's number?", Jul 17 2023

Cf. A364334, A082449. Different from A083647.

Nest[Function[list,
  Module[{p = Prime[Length[list] + 1]},
   Append[list,
    Max[(list[[PrimePi[First[#]]]]) & /@ FactorInteger[p - 1]] +
     1]]], {0}, 110]

a(n) = my(iteration = 0, v = [prime(n)], v_new); while(v!=[2], v_new = []; for(i=1, #v, v_new = concat(v_new, factor(v[i]-1)[,1]~)); v = Set(v_new); iteration++); iteration \\ Jianing Song, Apr 28 2024

A364332_first_N_terms(N) = my(v = vector(N), f); for(n=2, N, f = factor(prime(n)-1)[,1]~; v[n] = vecmax(vector(#f, i, v[primepi(f[i])]))+1); v \\ Jianing Song, Apr 28 2024

f(2) = 0 and f(p) = max{f(q):q is prime and q|(p-1)}+1 for p an odd prime. Then a(n) = f(prime(n)).

a(n) = 0 if and only if n = 1. a(n) = 1 if and only if prime(n) is a Fermat prime (A019434). a(n) = 2 if and only if prime(n) - 1 is a product of a power of 2 and a nonempty product of powers of Fermat primes. - Jianing Song, Apr 28 2024

A333870 The number of iterations of the absolute Möbius divisor function (A173557) required to reach from n to 1.

Original entry on oeis.org

0, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 2, 1, 2, 2, 3, 2, 3, 3, 4, 2, 2, 3, 2, 3, 4, 2, 3, 1, 3, 2, 3, 2, 3, 3, 3, 2, 3, 3, 4, 3, 2, 4, 5, 2, 3, 2, 2, 3, 4, 2, 3, 3, 3, 4, 5, 2, 3, 3, 3, 1, 3, 3, 4, 2, 4, 3, 4, 2, 3, 3, 2, 3, 3, 3, 4, 2, 2, 3, 4, 3, 2, 4, 4

Offset: 1

Amiram Eldar, Apr 08 2020

nonn

Apparently, the least number that reaches 1 after k iterations is A082449(k-1) (checked numerically for 1 <= k <= 17).

			a(3) = 2 since there are 2 iterations from 3 to 1: A173557(3) = 2 and A173557(2) = 1.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Daeyeoul Kim, Umit Sarp, and Sebahattin Ikikardes, Iterating the Sum of Möbius Divisor Function and Euler Totient Function, Mathematics, Vol. 7, No. 11 (2019), pp. 1083-1094.

Cf. A003434, A082449, A173557.

f[p_, e_] := p - 1; u[1] = 1; u[n_] := Times @@ (f @@@ FactorInteger[n]);a[n_] := Length @ FixedPointList[u, n] - 2; Array[a, 100]

cp's OEIS Frontend

A056637 a(n) is the least prime of class n-, according to the Erdős-Selfridge classification of primes.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

Extensions

A246497 Smallest k such that 9^^n is not congruent to 9^^(n-1) mod k, where 9^^n denotes the power tower 9^9^...^9 (in which 9 appears n times).

Views

Author

Keywords

Comments

Crossrefs

A019268 Let Dedekind's psi(m) = product of (p+1)p^(e-1) for primes p, where p^e is a factor of m. Iterating psi(m) eventually results in a number of form 2^a*3^b. a(n) is the smallest number that requires n steps to reach such a number.

Views

Author

Keywords

Comments

References

Crossrefs

Programs

Haskell

Mathematica

Extensions

A083647 For primes p: Number of steps to reach 2 when iterating f(p) = greatest prime divisor of p-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A364332 a(n) = f(prime(n)), where f(2) = 0 and for an odd prime p, f(p) = max{f(q)+1: q ranges over all prime factors of p-1}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A333870 The number of iterations of the absolute Möbius divisor function (A173557) required to reach from n to 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica