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

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

Author

Steven Lu, Jul 18 2023

Keywords

• nonn

Comments

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)

Examples

			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.
		

Links

• 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

Crossrefs

Cf. A364334, A082449. Different from A083647.

Programs

Mathematica

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

PARI

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

PARI

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

Formula

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