|
%I #43 May 13 2020 18:58:46
%S 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 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 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 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 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 Reinhard Zumkeller, <a href="/A064415/b064415.txt">Table of n, a(n) for n = 1..10000</a>
%H 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 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 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 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 From _Antti Karttunen_, May 13 2020: (Start)
%F For n > 1, a(n) = A003434(n) - A000035(n).
%F 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 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 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 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 a(n) = A064097(n) - A329697(n).
%F a(2^k) = a(3^k) = k.
%F (End)
%o (Haskell)
%o a064415 1 = 0
%o a064415 n = a003434 n - n `mod` 2 -- _Reinhard Zumkeller_, Sep 18 2011
%o (PARI)
%o A003434(n)=for(k=0, n, n>1 || return(k); n=eulerphi(n));
%o a(n) = if( n<=2, n-1, A003434(n) - (n%2) );
%o vector(200, n, a(n)) \\ _Joerg Arndt_, Apr 08 2014
%o (PARI) A064415(n) = if(!bitand(n,n-1),valuation(n,2),A064415(n-(n/vecmax(factor(n)[, 1])))); \\ _Antti Karttunen_, May 13 2020
%o (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 Cf. A000010, A003434, A007814, A052126, A054725, A064097, A064416, A064674, A171462, A291783, A329697.
%Y The 2-adic valuation of A309243.
%Y Partial sums of A334195. Cf. A053044 for partial sums of this sequence.
%Y Cf. also A334097 (analogous sequence when using the map k -> k + k/p).
%K nonn
%O 1,4
%A Christian WEINSBERG (cweinsbe(AT)fr.packardbell.org), Sep 30 2001
%E More terms from _David Wasserman_, Jul 22 2002
%E Definition corrected by _Reinhard Zumkeller_, Sep 18 2011
|
