cp's OEIS Frontend

From Antti Karttunen, Apr 07 2020: (Start)

Also the least number of iterations of nondeterministic map k -> k-(k/p) needed to reach a power of 2, when any prime factor p of k can be used. The minimal length path to the nearest power of 2 (= 2^A064415(n)) is realized whenever one uses any of the A005087(k) distinct odd prime factors of the current k, at any step of the process. For example, this could be done by iterating with the map k -> k-(k/A078701(k)), i.e., by using the least odd prime factor of k (instead of the largest prime).

Proof: Viewing the prime factorization of changing k as a multiset ("bag") of primes, we see that liquefying any odd prime p with step p -> (p-1) brings at least one more 2 to the bag, while applying p -> (p-1) to any 2 just removes it from the bag, but gives nothing back. Thus the largest (and thus also the nearest) power of 2 is reached by eliminating - step by step - all odd primes from the bag, but none of 2's, and it doesn't matter in which order this is done.

The above implies also that the sequence is totally additive, which also follows because both A064097 and A064415 are. That A064097(n) = A329697(n) + A054725(n) for all n > 1 can be also seen by comparing the initial conditions and the recursion formulas of these three sequences.

For any n, A333787(n) is either the nearest power of 2 reached (= 2^A064415(n)), or occurs on some of the paths from n to there.

(End)

A003401 gives the numbers k where a(k) = A005087(k). See also A336477. - Antti Karttunen, Mar 16 2021

Note that this is the logarithm of a completely multiplicative function. - Michael Somos

Number of iterations of r -> r - (largest divisor d < r) needed to reach 1 starting at r = n. a(n) = a(n - A032742(n)) + 1 for n >= 2. - Jaroslav Krizek, Jan 28 2010

From Antti Karttunen, Apr 04 2020: (Start)

Krizek's comment above stems from the fact that n - n/p = (p-1)*(n/p), where p is the least prime dividing n [= A020639(n), thus n/p = A032742(n)] and because this is fully additive sequence we can write a(n) = a(p) + a(n/p) = (1+a(p-1)) + a(n/p) = 1 + a((p-1)*(n/p)) = 1 + a(n - n/p), for any composite n.

Note that in above formula p can be any prime factor of n, not only the smallest, which proves Robert G. Wilson v's comment in A333123 that all such iteration paths from n to 1 are of the same length, regardless of the route taken.

(End)

From Antti Karttunen, May 11 2020: (Start)

Moreover, those paths form the chains of a graded poset, which is also a lattice. See the Mathematics Stack Exchange link.

Keeping the formula otherwise same, but changing it for primes either as a(p) = 1 + a(A064989(p)), a(p) = 1 + a(floor(p/2)) or a(p) = 1 + a(A048673(p)) gives sequences A056239, A064415 and A334200 respectively.

(End)

a(n) is the number of iterations r->A060681(r) to reach 1 starting at r=n. - R. J. Mathar, Nov 06 2023

1, 2 and 4 are the only numbers such that for every divisor d, d+1 is a prime.

These and only these primes appear as prime divisors of any term of InvPhi(n) set if n is not empty, i.e., if n is from A002202. - Labos Elemer, Jun 24 2002

a(n) is the number of integers k such that n = k - k/p where p is one of the prime divisors of k. (See, e.g., A064097 and A333123, which are related to the mapping k -> k - k/p.) - Robert G. Wilson v, Jun 12 2022

The count includes also n itself, and the final 1 when it is distinct from n.

a(n) >= A000005(n) because all divisors of n can be found in the union of those paths. - Antti Karttunen, Apr 19 2020

Applying map k -> (p-1)*(k/p) to any term k on any row n > 1, where p is any prime factor of k, gives one of the terms on preceding row n-1.

Any prime that appears on row n is 1 + {some term on row n-1}.

The e-th powers of the terms on row n form a subset of terms on row (e*n). More generally, a product of terms that occur on rows i_1, i_2, ..., i_k can be found at row (i_1 + i_2 + ... + i_k), because A064097 is completely additive.

A001221(k) gives the number of terms on the row above that are immediate descendants of k.

A067513(k) gives the number of terms on the row below that lead to k.

Row lengths are given by A073933(n). Row sums are given by A332809(n). The maximum value in each row is given by A334144(n).

The n-th row consists of all 1's if and only if n is a power of two (A000079) or a Fermat prime (A019434).

Conjecture: rows are unimodal (increasing and then decreasing).

Not all rows are unimodal. Indices of rows that have terms that increase and decrease more than once are A334238. - Michael De Vlieger, Apr 18 2020