A364332 - OEIS

%I #42 Apr 30 2024 08:30:02

%S 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,

%T 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,

%U 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

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

%C This sequence is related to a problem about googology (see Zhihu).

%C There are three numbers named A, B and C, and initially A>1, and B=C=0.

%C Now take the following steps:

%C   Step 1. Let B=B+1, C=C+1.

%C   Step 2. Check if A is divisible by (B+1). If yes, go to Step 3; if no, go back to Step 1.

%C   Step 3. Let A=A/(B+1)*B^C.

%C   Step 4. Let B=0.

%C   Step 5. If A=1, then stop, otherwise go back to Step 1.

%C This program will always stop. When the program stops, C will be a very large number.

%C 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.

%C 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.

%C 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".

%C 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.

%C When B+1=3, any number of exponential of 2 can be increased, then every prime factor 3 corresponds ordinal omega.

%C When B+1=5, only the power of 2 can be increased as well, then prime factor 5 also corresponds omega.

%C 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.

%C 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.

%C 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.

%C From _Jianing Song_, Apr 28 2024: (Start)

%C 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.

%C Conjecture: the smallest prime p such that f(p) = m (namely a(primepi(p)) = m)) is p = A082449(m). Verified for m <= 13. (End)

%H Jianing Song, <a href="/A364332/b364332.txt">Table of n, a(n) for n = 1..10000</a>

%H Zhihu, <a href="https://www.zhihu.com/answer/3122621353">Meitianli's answer to the question "Does my number exceed Graham's number?"</a>, Jul 17 2023

%F 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)).

%F 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

%e 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.

%t Nest[Function[list,

%t   Module[{p = Prime[Length[list] + 1]},

%t    Append[list,

%t     Max[(list[[PrimePi[First[#]]]]) & /@ FactorInteger[p - 1]] +

%t      1]]], {0}, 110]

%o (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

%o (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

%Y Cf. A364334, A082449. Different from A083647.

%K nonn

%O 1,4

%A _Steven Lu_, Jul 18 2023