cp's OEIS Frontend

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)