cp's OEIS Frontend

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.

%I A064415 #43 May 13 2020 18:58:46
%S A064415 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,
%T A064415 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,
%U A064415 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
%N 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.
%C A064415 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
%H A064415 Reinhard Zumkeller, <a href="/A064415/b064415.txt">Table of n, a(n) for n = 1..10000</a>
%H A064415 Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, <a href="http://math.dartmouth.edu/~carlp/iterate.pdf">On the normal behavior of the iterates of some arithmetic functions</a>, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204.
%H A064415 Paul Erdos, Andrew Granville, Carl Pomerance and Claudia Spiro, <a href="/A000010/a000010_1.pdf">On the normal behavior of the iterates of some arithmetic functions</a>, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204. [Annotated copy with A-numbers]
%F A064415 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.
%F A064415 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
%F A064415 From _Antti Karttunen_, May 13 2020: (Start)
%F A064415 For n > 1, a(n) = A003434(n) - A000035(n).
%F A064415 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).
%F A064415 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]
%F A064415 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]
%F A064415 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]
%F A064415 a(n) = A064097(n) - A329697(n).
%F A064415 a(2^k) = a(3^k) = k.
%F A064415 (End)
%o A064415 (Haskell)
%o A064415 a064415 1 = 0
%o A064415 a064415 n = a003434 n - n `mod` 2 -- _Reinhard Zumkeller_, Sep 18 2011
%o A064415 (PARI)
%o A064415 A003434(n)=for(k=0, n, n>1 || return(k); n=eulerphi(n));
%o A064415 a(n) = if( n<=2, n-1, A003434(n) - (n%2) );
%o A064415 vector(200, n, a(n)) \\ _Joerg Arndt_, Apr 08 2014
%o A064415 (PARI) A064415(n) = if(!bitand(n,n-1),valuation(n,2),A064415(n-(n/vecmax(factor(n)[, 1])))); \\ _Antti Karttunen_, May 13 2020
%o A064415 (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
%Y A064415 Cf. A000010, A003434, A007814, A052126, A054725, A064097, A064416, A064674, A171462, A291783, A329697.
%Y A064415 The 2-adic valuation of A309243.
%Y A064415 Partial sums of A334195. Cf. A053044 for partial sums of this sequence.
%Y A064415 Cf. also A334097 (analogous sequence when using the map k -> k + k/p).
%K A064415 nonn
%O A064415 1,4
%A A064415 Christian WEINSBERG (cweinsbe(AT)fr.packardbell.org), Sep 30 2001
%E A064415 More terms from _David Wasserman_, Jul 22 2002
%E A064415 Definition corrected by _Reinhard Zumkeller_, Sep 18 2011