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

This permutation maps between the partitions as ordered in A112798 and A241918 (the original motivation for this sequence).

For all n > 2, A007814(a(n)) = A055396(n)-1, which implies that this self-inverse permutation maps between primes (A000040) and the powers of two larger than one (A000079(n>=1)), and apart from a(1) & a(2), this also maps each even number to some odd number, and vice versa, which means there are no fixed points after 2.

A122111 commutes with this one, that is, a(n) = A122111(a(A122111(n))).

Conjugates between A243051 and A242424 and other rows of A243060 and A243070.

Let f(n) = A000265(n) be the odd part of n. Let p be the largest prime factor of k, and say k = p * m. Suppose that k is not a power of 2, i.e., p > 2, then f(k) = p * f(m). The iteration is k -> k + k/p = p*m + m = (p+1) * m. So, p * f(m) -> f(p+1) * f(m). Since for p > 2, f(p+1) < p, the odd part in each iteration decreases, until it becomes 1, i.e., until we reach a power of 2. - Amiram Eldar, Feb 19 2020

Any odd prime factor of k can be used at any step of the iteration, and the result will be same. Thus, like A329697, this is also fully additive sequence. - Antti Karttunen, Apr 29 2020

If and only if a(n) is equal to A005087(n), then sigma(2n) - sigma(n) is a power of 2. (See A336923, A046528). - 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

It seems that a(n) <= A297113(n) for all n. Of the first 10000 positive natural numbers, 6454 are such that a(n) = A297113(n). - Antti Karttunen, Dec 31 2017

Also one plus the maximum number of unit steps East or South in the Young diagram of the integer partition with Heinz number n > 1, starting from the upper-left square and ending in a boundary square in the lower-right quadrant. The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). - Gus Wiseman, Apr 06 2019

From Gus Wiseman, Apr 06 2019: (Start)

Also the number of squares in the Young diagram of the integer partition with Heinz number n that are graph-distance 1 from the lower-right boundary, where the Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). For example, the partition (6,5,5,3) with Heinz number 7865 has diagram

o o o o o o

o o o o o

o o o o o

o o o

with inner rim

o

o

o o

o o o

of size 7, so a(7867) = 7.

(End)

For n greater than 1, the n-th entry is given by n*(1-1/p) where p is largest prime dividing n.

A prime index of n is a number m such that prime(m) divides n.

Also one plus the size of the largest hook contained in the Young diagram of the integer partition with Heinz number n. The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

Numbers of the form 2^k * ((2^p)-1), where p is one of the primes in A000043, and k >= 0.

Numbers k such that A000265(k) is in A000668.

Numbers k for which A331410(k) = 1.

Numbers k that themselves are not powers of two, but for which A335876(k) = k+A052126(k) is [a power of 2].

Conjecture: This sequence gives all fixed points of map n -> A332214(n) and its inverse n -> A332215(n). See also notes in A029747 and in A163511.