A064415 a(1) = 0, a(n) = iter(n) if n is even, a(n) = iter(n)-1 if n is odd, where iter(n) = A003434(n) = smallest number of iterations of Euler totient function phi needed to reach 1.

0, 1, 1, 2, 2, 2, 2, 3, 2, 3, 3, 3, 3, 3, 3, 4, 4, 3, 3, 4, 3, 4, 4, 4, 4, 4, 3, 4, 4, 4, 4, 5, 4, 5, 4, 4, 4, 4, 4, 5, 5, 4, 4, 5, 4, 5, 5, 5, 4, 5, 5, 5, 5, 4, 5, 5, 4, 5, 5, 5, 5, 5, 4, 6, 5, 5, 5, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 4, 6, 6, 5, 6, 5, 5, 6, 6, 5, 5, 6, 5, 6, 5, 6, 6, 5, 5, 6, 6, 6, 6, 6, 5

Offset: 1

Author

Christian WEINSBERG (cweinsbe(AT)fr.packardbell.org), Sep 30 2001

Keywords

• nonn

Comments

a(n) is the exponent of the eventual power of 2 reached when starting from k=n and then iterating the nondeterministic map k -> k-(k/p), where p can be any odd prime factor of k, for example, the largest. Note that each original odd prime factor p of n brings its own share of 2's to the final result after it has been completely processed (with all intermediate odd primes also eliminated, leaving only 2's). As no 2's are removed, also all 2's already present in the original n are included in the eventual power of 2 that is reached, implying that a(n) >= A007814(n). - Antti Karttunen, May 13 2020

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204.
• Paul Erdos, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204. [Annotated copy with A-numbers]

Crossrefs

Cf. A000010, A003434, A007814, A052126, A054725, A064097, A064416, A064674, A171462, A291783, A329697.

The 2-adic valuation of A309243.

Partial sums of A334195. Cf. A053044 for partial sums of this sequence.

Cf. also A334097 (analogous sequence when using the map k -> k + k/p).

Programs

Haskell

a064415 1 = 0
a064415 n = a003434 n - n `mod` 2 -- Reinhard Zumkeller, Sep 18 2011

PARI

A003434(n)=for(k=0, n, n>1 || return(k); n=eulerphi(n));
a(n) = if( n<=2, n-1, A003434(n) - (n%2) );
vector(200, n, a(n)) \\ Joerg Arndt, Apr 08 2014

PARI

A064415(n) = if(!bitand(n,n-1),valuation(n,2),A064415(n-(n/vecmax(factor(n)[, 1])))); \\ Antti Karttunen, May 13 2020

PARI

A064415(n) = if(1==n, 0, if(isprime(n), 1+A064415(n>>1), my(f=factor(n)); (apply(A064415, f[, 1])~ * f[, 2]))); \\ Antti Karttunen, May 13 2020

Formula

For all integers m >0 and n>0 a(m*n)=a(m)+a(n). The function a(n) is completely additive. The smallest integer q which satisfy the equation a(q)=n is 2^q, the greatest is 3^q. For all integers n>0, the counter image off n, a^-1(n) is finite.

a(1) = 0 and a(n) = A054725(n) for n>=2. - Joerg Arndt, Apr 08 2014, A-number corrected by Antti Karttunen, May 13 2020

From Antti Karttunen, May 13 2020: (Start)

For n > 1, a(n) = A003434(n) - A000035(n).

a(1) = 0, a(2) = 1 and for n > 2, a(n) = sum(p | n, a(p-1)), where sum is over all primes p that divide n, with multiplicity. (Cf. A054725).

a(1) = 0, a(2) = 1 and a(p) = 1 + a((p-1)/2) if p is an odd prime and a(n*m) = a(n) + a(m) if m,n > 1. [From above formula, 1+ compensates for the "lost" 2]

a(n) = A007814(A309243(n)). [From Rémy Sigrist's conjecture in the latter sequence. This reduces to a(n) = sum(p|n, a(p-1)) formula above, thus holds also]

If A209229(n) = 1 [when n is a power of 2], a(n) = A007814(n), otherwise a(n) = a(n-A052126(n)) = a(A171462(n)). [From the definition in the comments]

a(n) = A064097(n) - A329697(n).

a(2^k) = a(3^k) = k.

(End)

Extensions

More terms from David Wasserman, Jul 22 2002

Definition corrected by Reinhard Zumkeller, Sep 18 2011