OFFSET
1,4
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)
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
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
EXAMPLE
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.
MATHEMATICA
Nest[Function[list,
Module[{p = Prime[Length[list] + 1]},
Append[list,
Max[(list[[PrimePi[First[#]]]]) & /@ FactorInteger[p - 1]] +
1]]], {0}, 110]
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Steven Lu, Jul 18 2023
STATUS
approved