A049115 -id:A049115 - cp's OEIS frontend

A227944 Number of iterations of "take odd part of phi" (A053575) to reach 1 from n.

0, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 2, 3, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 1, 2, 1, 2, 1, 2, 2, 3, 3, 2, 1, 2, 2, 3, 2, 2, 3, 4, 1, 3, 2, 1, 2, 3, 3, 2, 2, 3, 3, 4, 1, 2, 2, 3, 1, 2, 2, 3, 1, 3, 2, 3, 2, 3, 3, 2, 3, 2, 2, 3, 1, 4, 2, 3, 2, 1, 3, 3, 2, 3, 2, 3, 3, 2, 4, 3, 1, 2, 3, 2, 2

Offset: 1

Max Alekseyev, Oct 03 2013

a(n) >= A256757(n) - 1.

			a(18) = 2 because it takes two steps to reach 1 from 18: phi(18) = 6, the odd part of which is 3, and phi(3) = 2, the odd part of which is 1.
a(19) = 3 because it takes three steps to reach 1 from 19: phi(19) = 18, the odd part of which is 9, and phi(9) = 6, the odd part of which is 3, and phi(3) = 2, the odd part of which is 1.

T. D. Noe, Table of n, a(n) for n = 1..10000

A variant of A049115: a(n) = A049115(n) unless n is a power of 2.

Cf. A003434, A227946.

a227944 n = fst $
            until ((== 1) . snd) (\(i, x) -> (i + 1, a053575 x)) (0, n)
-- Reinhard Zumkeller, Oct 09 2013

oddPhi[n_] := Module[{phi = EulerPhi[n]}, phi/2^IntegerExponent[phi, 2]]; Table[Length[NestWhileList[oddPhi[#] &, n, # > 1 &]] - 1, {n, 100}] (* T. D. Noe, Oct 07 2013 *)

For n > 1, a(n) = a(A053575(n)) + 1.

A049107 a(n) = Euler phi function applied 5 times to n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 1, 2, 4, 1, 4, 1, 2, 2, 4, 1, 2, 2, 2, 2, 2, 2, 4, 1, 2, 2, 4, 2, 4, 2, 2

Offset: 1

Labos Elemer

nonn

			For n = 163, the successive iterates applying Euler totient function are as follows: 163, 162, 54, 18, 6, 2, 1. The 6th term is 2, when Phi was applied 5 times. So a(163)=2, already a power of 2.
For n = 487, the successive iterates are 486, 162, 54, 18, 6, 2, 1. On the fifth iteration we reach 6, thus a(487) = 6. This is also the first term of A049107 that is not a power of 2. - _Antti Karttunen_, Aug 22 2017

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

Cf. A000010, A010554, A049099, A049100, A049115.

a(n)=Nest[ EulerPhi, n, 5 ]
Nest[EulerPhi,Range[110],5] (* Harvey P. Dale, May 19 2019 *)

A049107(n) = eulerphi(eulerphi(eulerphi(eulerphi(eulerphi(n))))); \\ Antti Karttunen, Aug 22 2017

a(n) = A000010(A049100(n)) = A010554(A049099(n)) = phi(phi(phi(phi(phi(n))))), where phi = A000010. - Antti Karttunen, Aug 22 2017

A049099 a(n) = Euler phi function applied thrice to n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 2, 4, 1, 2, 2, 2, 2, 4, 2, 4, 2, 2, 2, 4, 2, 4, 4, 4, 4, 4, 2, 4, 2, 4, 4, 8, 2, 4, 4, 4, 4, 10, 4, 4, 4, 8, 4, 8, 2, 8, 4, 4, 4, 12, 4, 8, 4, 4, 8, 8, 4, 8, 8, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 8, 6, 8, 16, 4, 16, 4, 8, 8, 16, 4, 8, 8, 8, 10, 8, 8, 16, 4, 8, 8, 16

Offset: 1

Labos Elemer

nonn

			n=163: the successive iterates of Euler totient function are 163,162,54,18,6,2,1. The 4th term is 18, when Phi was applied 3 times. So a(163)=18.

Antti Karttunen, 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]
Boris Putievskiy, Transformations [Of] Integer Sequences And Pairing Functions, arXiv preprint arXiv:1212.2732 [math.CO], 2012.

Cf. A000010, A010554, A049100, A049107, A049115.

Mathematica
```
a(n)=Nest[ EulerPhi, n, 3 ]
```

A049099(n) = eulerphi(eulerphi(eulerphi(n))); \\ Antti Karttunen, Aug 22 2017

a(n) = A000010(A010554(n)) = A000010(A000010(A000010(n))). - Antti Karttunen, Aug 22 2017

A049100 a(n) = Euler phi function applied 4 times to n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 1, 2, 1, 2, 2, 4, 1, 2, 2, 2, 2, 4, 2, 2, 2, 4, 2, 4, 1, 4, 2, 2, 2, 4, 2, 4, 2, 2, 4, 4, 2, 4, 4, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 4, 2, 4, 8, 2, 8, 2, 4, 4, 8, 2, 4, 4, 4, 4, 4, 4, 8, 2, 4, 4, 8, 4, 8, 4, 4

Offset: 1

Labos Elemer

nonn

			n=163, the successive iterates applying Euler totient function are as follows: 163,162,54,18,6,2,1. The 5th term is 6, when Phi was applied 4 times. So a(163)=6.

Antti Karttunen, Table of n, a(n) for n = 1..10000
Boris Putievskiy, Transformations [Of] Integer Sequences And Pairing Functions, arXiv preprint arXiv:1212.2732 [math.CO], 2012.

Cf. A000010, A010554, A049099, A049107, A049115.

with(numtheory): seq(phi(phi(phi(phi(n)))),n=1..130); # Emeric Deutsch, May 14 2006

Mathematica
```
a(n)=Nest[ EulerPhi, n, 4 ]
```

A049100(n) = eulerphi(eulerphi(eulerphi(eulerphi(n)))); \\ Antti Karttunen, Aug 22 2017

a(n) = phi(phi(phi(phi(n)))) = A000010(A000010(A000010(A000010(n)))) = A010554(A010554(n)) = A000010(A049099(n)).

Edited by N. J. A. Sloane at the suggestion of Andrew S. Plewe, Jun 23 2007

A049113 Number of powers of 2 in sequence obtained when phi (A000010) is repeatedly applied to n.

Original entry on oeis.org

1, 2, 2, 3, 3, 2, 2, 4, 2, 3, 3, 3, 3, 2, 4, 5, 5, 2, 2, 4, 3, 3, 3, 4, 4, 3, 2, 3, 3, 4, 4, 6, 4, 5, 4, 3, 3, 2, 4, 5, 5, 3, 3, 4, 4, 3, 3, 5, 3, 4, 6, 4, 4, 2, 5, 4, 3, 3, 3, 5, 5, 4, 3, 7, 5, 4, 4, 6, 4, 4, 4, 4, 4, 3, 5, 3, 5, 4, 4, 6, 2, 5, 5, 4, 7, 3, 4, 5, 5, 4, 4, 4, 5, 3, 4, 6, 6, 3, 5, 5, 5, 6, 6, 5, 5

Offset: 1

Labos Elemer

nonn

			If n = 164, the "iterated phi-sequence" for n is {164,80,32,16,8,4,2,1}. It includes 6 powers of 2 at the end, so a(164) = 6.

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

Cf. A000010, A049115, A049108.

A049113 := proc(n)
    local a, e;
    e := n ;
    a :=0 ;
    while e > 1 do
        if isA000079(e) then
            a := a+1 ;
        end if;
        e := numtheory[phi](e) ;
    end do:
    1+a;
end proc:
seq(A049113(n),n=1..40) ; # R. J. Mathar, Jan 09 2017

pwrs2 = NestList[2#&, 1, 15];
Table[Length[Intersection[NestWhileList[EulerPhi[#]&, i, # > 1 &], pwrs2]], {i, 100}] (* Harvey P. Dale, Dec 12 2010 *)

a(n)=while(n!=1<Charles R Greathouse IV, Feb 21 2013

a(n) = A049108(n)-A049115(n). - R. J. Mathar, Sep 08 2021

A060610 Repeatedly apply Euler phi to the n-th prime; a(n) is the number of terms in the resulting iteration chain which are not powers of 2 (number of initial iterations until reaching the first power of 2).

Original entry on oeis.org

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

Offset: 1

Labos Elemer, Apr 13 2001

			n=100,p(100)=541, Phi-iteration chain is {541,540,144,48,16,8,4,2,1} with 9 terms. The first 4 terms (541,540,144,48) are not powers of 2, som a(100)=4.

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

Cf. A000040, A000010, A049108, A049113, A049116, A049115, A003434.

Table[Count[FixedPointList[EulerPhi[#]&,Prime[n]],?(!IntegerQ[ Log[ 2,#]]&)],{n,110}] (* _Harvey P. Dale, Sep 18 2016 *)

a(n) = A049115(A000040(n)).

Definition clarified by Harvey P. Dale, Sep 18 2016

cp's OEIS Frontend

A227944 Number of iterations of "take odd part of phi" (A053575) to reach 1 from n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A049107 a(n) = Euler phi function applied 5 times to n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A049099 a(n) = Euler phi function applied thrice to n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A049100 a(n) = Euler phi function applied 4 times to n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A049113 Number of powers of 2 in sequence obtained when phi (A000010) is repeatedly applied to n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A060610 Repeatedly apply Euler phi to the n-th prime; a(n) is the number of terms in the resulting iteration chain which are not powers of 2 (number of initial iterations until reaching the first power of 2).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions