A049113 -id:A049113 - cp's OEIS frontend

A049115 a(n) is the number of iterations of the Euler phi function needed to reach a power of 2, when starting from n.

0, 0, 1, 0, 1, 1, 2, 0, 2, 1, 2, 1, 2, 2, 1, 0, 1, 2, 3, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 1, 2, 0, 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, 0, 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, 3, 1, 2, 2, 2

Offset: 1

Labos Elemer

nonn

a(n) = A227944(n) if n is not a power of 2. - Eric M. Schmidt, Oct 13 2013

			If n is a power of 2, then a(n)=0 by definition. If n = 59049, then by iterating with phi, we get 59049 -> 39366 -> 13122 -> 4374 -> 1458 -> 486 -> 162 -> 54 -> 18 -> 6 -> 2 -> 1. It took ten steps to reach the first power of 2 (2 in this case), so a(59049) = 10.

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

Cf. A000010, A003434, A049113, A057716, A209229, A227944.

Cf. also A064097, A064415, A329697.

Table[If[IntegerQ@ Log2@ n, 0, -1 + Length@ NestWhileList[EulerPhi, n, ! IntegerQ@ Log2@ # &]], {n, 105}] (* Michael De Vlieger, Aug 01 2017 *)

A049115(n) = if(!bitand(n,n-1),0,1+A049115(eulerphi(n))); \\ Antti Karttunen, Aug 28 2021

The smallest x so that Nest[ EulerPhi, n, x ] = 2^w is just achieved.
From Antti Karttunen, Aug 28 2021: (Start)
If A209229(n) = 1, then a(n) = 0, otherwise a(n) = 1 + a(A000010(n)).
a(n) <= A003434(n) and a(n) <= A329697(n) for all n.
(End)

Definition corrected and simplified, example corrected by Antti Karttunen, Aug 28 2021

A347387 The exponent of the first power of 2 reached when starting iterating A347385 from n, where A347385 is Dedekind psi function applied to the odd part of n.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Aug 31 2021

nonn

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

Cf. A000265, A001615, A007814, A209229, A347385, A347386.

Cf. also A049113, A347388.

f[p_, e_] := If[p == 2, 1, (p + 1)*p^(e - 1)]; psiOdd[1] = 1; psiOdd[n_] := Times @@ f @@@ FactorInteger[n]; a[n_] := IntegerExponent[NestWhile[psiOdd, n, # != 2^IntegerExponent[#, 2] &], 2]; Array[a, 100] (* Amiram Eldar, Aug 31 2021 *)

A347385(n) = if(1==n,n, my(f=factor(n>>valuation(n, 2))); prod(i=1, #f~, f[i, 1]^f[i, 2] + f[i, 1]^(f[i, 2]-1)));
A347387(n) = if(!bitand(n, n-1), valuation(n, 2), A347387(A347385(n)));

a(2^k) = k, and for numbers with A209229(n) = 0, a(n) = a(A001615(A000265(n))).

A053045 a(n) is the number of powers of 2 among the iterates of the Euler phi function when it is iterated with initial value n!.

Original entry on oeis.org

1, 2, 2, 4, 6, 7, 8, 11, 11, 14, 17, 19, 21, 23, 25, 29, 33, 34, 35, 39, 40, 44, 48, 51, 55, 58, 58, 61, 64, 67, 70, 75, 78, 83, 86, 88, 90, 92, 94, 99, 104, 106, 108, 113, 115, 120, 125, 129, 131, 136, 140, 144, 148, 149, 154, 158, 159, 163, 167, 171, 175, 179, 180

Offset: 1

Labos Elemer, Feb 25 2000

nonn

Powers of 2 arise at the end of iterations without interruption. Analogous to A053035.

			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 14 values are powers of 2: 8192, ..., 1. Thus a(10) = 14.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Michael De Vlieger)

Cf. A000010, A000142, A049113, A053035.

A053045 := 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(A053045(n),n=1..18) ; # R. J. Mathar, Jan 09 2017

Table[Count[NestWhileList[EulerPhi, n!, # > 1 &], ?(IntegerQ@ Log2@ # &)], {n, 63}] (* _Michael De Vlieger, Aug 15 2017 *)

a(n) = A049113(n!). - R. J. Mathar, Jan 09 2017

A060609 Repeatedly apply Euler phi to n-th prime; a(n) = highest power of 2 that is seen.

Original entry on oeis.org

2, 2, 4, 2, 4, 4, 16, 2, 4, 4, 8, 4, 16, 4, 4, 8, 4, 16, 8, 8, 8, 8, 16, 16, 32, 16, 32, 8, 4, 16, 4, 16, 64, 8, 8, 16, 16, 2, 16, 8, 16, 16, 8, 64, 8, 16, 16, 8, 16, 8, 16, 32, 64, 16, 256, 16, 16, 8, 16, 32, 8, 16, 32, 32, 32, 16, 32, 32, 8, 16, 64, 16, 32, 32, 4, 8, 64, 32, 64, 128

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 largest power of 2 is the 5th term=16=a(100).

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

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

Table[Max[Select[NestWhileList[EulerPhi[#]&,Prime[n],#>1&],IntegerQ[Log2[#]]&]],{n,80}] (* Harvey P. Dale, Aug 23 2025 *)

a(n) = A049116(A000040(n)).

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

A049115 a(n) is the number of iterations of the Euler phi function needed to reach a power of 2, when starting from n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A347387 The exponent of the first power of 2 reached when starting iterating A347385 from n, where A347385 is Dedekind psi function applied to the odd part of n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A053045 a(n) is the number of 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

Programs

Maple

Mathematica

Formula

A060609 Repeatedly apply Euler phi to n-th prime; a(n) = highest power of 2 that is seen.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

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