A053044 -id:A053044 - 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.

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

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

nonn

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

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]

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).

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

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

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

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

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)

More terms from David Wasserman, Jul 22 2002

Definition corrected by Reinhard Zumkeller, Sep 18 2011

A335429 Partial sums of A329697.

Original entry on oeis.org

0, 0, 1, 1, 2, 3, 5, 5, 7, 8, 10, 11, 13, 15, 17, 17, 18, 20, 23, 24, 27, 29, 32, 33, 35, 37, 40, 42, 45, 47, 50, 50, 53, 54, 57, 59, 62, 65, 68, 69, 71, 74, 78, 80, 83, 86, 90, 91, 95, 97, 99, 101, 104, 107, 110, 112, 116, 119, 123, 125, 128, 131, 135, 135, 138, 141, 145, 146, 150, 153, 157, 159, 162, 165, 168, 171

Offset: 1

Antti Karttunen, Jun 28 2020

nonn

Antti Karttunen, Table of n, a(n) for n = 1..14042

Cf. A000142, A053044, A329697, A335860.

A329697(n) = if(!bitand(n,n-1),0,1+A329697(n-(n/vecmax(factor(n)[, 1]))));
A335429(n) = if(1==n,0,A329697(n)+A335429(n-1));

a(1) = 0; for n > 1, a(n) = A329697(n) + a(n-1).
a(n) = A329697(A000142(n)) = A329697(n!).
a(n) = A335860(n) - A053044(n).

A053096 When the Euler phi function is iterated with initial value A002110(n) = primorial, a(n) = number of iterations required to reach the fixed number = 1.

Original entry on oeis.org

1, 2, 4, 6, 9, 12, 16, 19, 23, 27, 31, 35, 40, 44, 49, 54, 59, 64, 69, 74, 79, 84, 90, 96, 102, 108, 114, 120, 125, 131, 136, 142, 149, 155, 161, 167, 173, 178, 185, 191, 198, 204, 210, 217, 223, 229, 235, 241, 248, 254, 261, 268, 275, 282, 290, 297, 304, 310

Offset: 1

Labos Elemer, Feb 28 2000

nonn

Analogous to A053025, A053034, A053044. For comparison: iteration of, e.g., A000005 to primorial i.v. is trivially computable: q(n)=A002110(n), d(q(n)) = 2^n, d(d(q(n))) = n+1 and so A036450(A002110(n)) = A000005(n+1).

			n=7, A002110(7)=510510; the corresponding iteration chain is {510510, 92160, 24576, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1}. Its length is 17, so the required number of iterations is a(7)=16.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A000010, A002110, A003434.

Array[-2 + Length@ FixedPointList[EulerPhi, Product[Prime@ i, {i, #}]] &, 58] (* Michael De Vlieger, Nov 20 2017 *)

a(n)=my(t=prod(i=1,n,prime(i)-1),s=1); while(t>1, t=eulerphi(t); s++); s \\ Charles R Greathouse IV, Jan 06 2016

A003434(n)=my(s);while(n>1,n=eulerphi(n);s++);s
first(n)=my(s=1); vector(n,k,s+=A003434(prime(k))-1) \\ Charles R Greathouse IV, Jan 06 2016

a(n) is the smallest number such that Nest[EulerPhi, A002110, a(n)]=1

A291783 Partial sums of A064415(k)^2.

Original entry on oeis.org

0, 1, 2, 6, 10, 14, 18, 27, 31, 40, 49, 58, 67, 76, 85, 101, 117, 126, 135, 151, 160, 176, 192, 208, 224, 240, 249, 265, 281, 297, 313, 338, 354, 379, 395, 411, 427, 443, 459, 484, 509, 525, 541, 566, 582, 607, 632, 657, 673, 698, 723, 748, 773, 789, 814, 839

Offset: 1

N. J. A. Sloane, Sep 02 2017

nonn

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]

Cf. A064415, A053044.

A335860 Partial sums of A064097.

Original entry on oeis.org

0, 1, 3, 5, 8, 11, 15, 18, 22, 26, 31, 35, 40, 45, 50, 54, 59, 64, 70, 75, 81, 87, 94, 99, 105, 111, 117, 123, 130, 136, 143, 148, 155, 161, 168, 174, 181, 188, 195, 201, 208, 215, 223, 230, 237, 245, 254, 260, 268, 275, 282, 289, 297, 304, 312, 319, 327, 335

Offset: 1

Michael De Vlieger, Antti Karttunen, Robert G. Wilson v, Jun 27 2020

nonn

Cf. A053044, A064097, A081401, A335429.

Accumulate@ Nest[Append[#1, #1[[#2 - #2/FactorInteger[#2][[1, 1]]]] + 1] & @@ {#, Length@ # + 1} &, {0}, 57]

a(n) = A064097(A000142(n)) = A064097(n!).

a(n) = A053044(n) + A335429(n).

A053046 a(n) is the number of terms that are not powers of 2 among the iterates of the Euler phi function when it is iterated with initial value n!.

Original entry on oeis.org

0, 0, 1, 1, 1, 2, 3, 3, 5, 5, 5, 6, 7, 8, 9, 9, 9, 11, 13, 13, 15, 15, 15, 16, 16, 17, 20, 21, 22, 23, 24, 24, 25, 25, 26, 28, 30, 32, 34, 34, 34, 36, 38, 38, 40, 40, 40, 41, 43, 43, 44, 45, 46, 49, 49, 50, 53, 54, 55, 56, 57, 58, 61, 61, 62, 63, 64, 64, 65, 66, 67, 69, 71, 73, 74

Offset: 1

Labos Elemer, Feb 25 2000

nonn

Non-powers of 2 arise at the beginning of iteration chains without interruption. Analogous to A053036.

			For n = 10, the initial value is 10! = 3628800 and the iteration chain is {3628800, 829440, 221184, 73728, 24576, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1}. Its length is 19 and there are 5 values that are not powers of 2: 10!, ..., 24576. Thus a(10) = 5.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000010, A000142, A048855, A053036, A053044, A053045.

a(n) = 1 + A053044(n) - A053045(n). - R. J. Mathar, Jan 09 2017

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

PARI

PARI

PARI

Formula

Extensions

A335429 Partial sums of A329697.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A053096 When the Euler phi function is iterated with initial value A002110(n) = primorial, a(n) = number of iterations required to reach the fixed number = 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A291783 Partial sums of A064415(k)^2.

Views

Author

Keywords

Links

Crossrefs

A335860 Partial sums of A064097.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A053046 a(n) is the number of terms that are not powers of 2 among the iterates of the Euler phi function when it is iterated with initial value n!.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula