A003434 -id:A003434 - cp's OEIS frontend

A336469 a(n) = A329697(phi(n)), where A329697 is totally additive with a(2) = 0 and a(p) = 1 + a(p-1) for odd primes.

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

Offset: 1

Antti Karttunen, Jul 22 2020

nonn

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

Cf. A000010, A000265, A003434, A005087, A046660, A064097, A064415, A329697, A336396, A336477.

Cf. A003401 (positions of zeros).

Array[Length@ NestWhileList[# - #/FactorInteger[#][[-1, 1]] &, EulerPhi[#], # != 2^IntegerExponent[#, 2] &] - 1 &, 105] (* Michael De Vlieger, Jul 24 2020 *)

A329697(n) = if(!bitand(n,n-1),0,1+A329697(n-(n/vecmax(factor(n)[, 1]))));
A336469(n) = A329697(eulerphi(n));
\\ Or alternatively as:
A336469(n) = { my(f = factor(n)); sum(k=1, #f~, if(2==f[k,1],0,-1 + (f[k, 2]*A329697(f[k, 1])))); };

Additive with a(2^e) = 0, and for odd primes p, a(p^e) = A329697((p - 1)*p^(e-1)) = e*A329697(p) - 1.

a(n) = A329697(n) - A005087(n) = A336396(n) + A046660(A000265(n)).

A032358 Number of iterations of phi(n) needed to reach 2.

Original entry on oeis.org

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

Offset: 2

Ursula Gagelmann (gagelmann(AT)altavista.net)

This sequence is additive (but not completely additive). [Charles R Greathouse IV, Oct 28 2011]
Shapiro asks for a proof that for every n > 1 there is a prime p such that a(p) = n. [Charles R Greathouse IV, Oct 28 2011]
This is A003434(n)-1 for n>1. - N. J. A. Sloane, Sep 02 2017

Reinhard Zumkeller, Table of n, a(n) for n = 2..10000
P. A. Catlin, Concerning the iterated phi-function, Amer Math. Monthly 77 (1970), pp. 60-61.
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]
T. D. Noe, Primes in classes of the iterated totient function, JIS 11 (2008) 08.1.2, sequence C(x).
Harold Shapiro, An arithmetic function arising from the phi function, Amer. Math. Monthly, Vol. 50, No. 1 (1943), 18-30.

Cf. A000010, A003434.

a032358 = length . takeWhile (/= 2) . (iterate a000010)
-- Reinhard Zumkeller, Oct 27 2011

A032358 := proc(n)
    local a,phin ;
    if n <=2 then
        0;
    else
        phin := n ;
        a := 0 ;
        for a from 1 do
            phin := numtheory[phi](phin) ;
            if phin = 2 then
                return a;
            end if;
        end do:
    end if;
end proc:
seq(A032358(n),n=1..30) ; # R. J. Mathar, Aug 28 2015

Table[Length[NestWhileList[EulerPhi[#]&,n,#>2&]]-1,{n,3,80}] (* Harvey P. Dale, May 01 2011 *)

a(n)=my(t);while(n>2,n=eulerphi(n);t++);t \\ Charles R Greathouse IV, Oct 28 2011

a(n) = a(phi(n))+1, a(1) = -1. - Vladeta Jovovic, Apr 29 2003
a(n) = A003434(n) - 1 = A049108(n) - 2.
From Charles R Greathouse IV, Oct 28 2011:  (Start)
Shapiro proves that log_3(n/2) <= a(n) < log_2(n) and also
a(mn) = a(m) + a(n) if either m or n is odd and a(mn) = a(m) + a(n) + 1 if m and n are even.
(End)

a(2) = 0 added and offset adjusted, suggested by David W. Wilson

A058812 Irregular triangle of rows of numbers in increasing order. Row 1 = {1}. Row m + 1 contains all numbers k such that phi(k) is in row m.

Original entry on oeis.org

1, 2, 3, 4, 6, 5, 7, 8, 9, 10, 12, 14, 18, 11, 13, 15, 16, 19, 20, 21, 22, 24, 26, 27, 28, 30, 36, 38, 42, 54, 17, 23, 25, 29, 31, 32, 33, 34, 35, 37, 39, 40, 43, 44, 45, 46, 48, 49, 50, 52, 56, 57, 58, 60, 62, 63, 66, 70, 72, 74, 76, 78, 81, 84, 86, 90, 98, 108, 114, 126

Offset: 0

Labos Elemer, Jan 03 2001

Nontotient values (A007617) are also present as inverses of some previous value.

Old name was: Irregular triangle of inverse totient values of integers generated recursively. Initial value is 1. The inverse-phi sets in increasing order are as follows: {1} -> {2} -> {3, 4, 6} -> {5, 7, 8, 9, 10, 12, 14, 18} -> ... The terms of each row are arranged by magnitude. The next row starts when the increase of terms is violated. 2^n is included in the n-th row. - David A. Corneth, Mar 26 2019

			Triangle begins:
  1;
  2;
  3, 4, 6;
  5, 7, 8, 9, 10, 12, 14, 18;
  ...
Row 3 is {3, 4, 6} as for each number k in this row, phi(k) is in row 2. - _David A. Corneth_, Mar 26 2019

T. D. Noe, Rows n=0..9 of triangle, flattened
Hartosh Singh Bal, Gaurav Bhatnagar, Prime number conjectures from the Shapiro class structure, arXiv:1903.09619 [math.NT], 2019.
T. D. Noe, Primes in classes of the iterated totient function, JIS 11 (2008) 08.1.2.
Index entries for sequences that are permutations of the natural numbers

Cf. A000010, A007617, A005277.
A058811 gives the number of terms in each row.
Cf. A003434, A007755, A060611, A092878, A098196, A135832.
Cf. also A334111.

inversePhi[m_?OddQ] = {}; inversePhi[1] = {1, 2}; inversePhi[m_] := Module[{p, nmax, n, nn}, p = Select[Divisors[m] + 1, PrimeQ]; nmax = m*Times @@ (p/(p-1)); n = m; nn = {}; While[n <= nmax, If[EulerPhi[n] == m, AppendTo[nn, n]]; n++]; nn]; row[n_] := row[n] = inversePhi /@ row[n-1] // Flatten // Union; row[0] = {1}; row[1] = {2}; Table[row[n], {n, 0, 5}] // Flatten (* Jean-François Alcover, Dec 06 2012 *)

Definition revised by T. D. Noe, Nov 30 2007

New name from David A. Corneth, Mar 26 2019

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

Original entry on oeis.org

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

A053044 a(n) is the number of iterations of the Euler totient function to reach 1, starting at n!.

Original entry on oeis.org

0, 1, 2, 4, 6, 8, 10, 13, 15, 18, 21, 24, 27, 30, 33, 37, 41, 44, 47, 51, 54, 58, 62, 66, 70, 74, 77, 81, 85, 89, 93, 98, 102, 107, 111, 115, 119, 123, 127, 132, 137, 141, 145, 150, 154, 159, 164, 169, 173, 178, 183, 188, 193, 197, 202, 207, 211, 216, 221, 226, 231

Offset: 1

Labos Elemer, Feb 25 2000

nonn

Powers of 2 arise at the end of iteration chains without interruption. Analogous to A053025 and A053034. The order of speed of convergence is as follows: A000005 > A000010 > A051953: e.g., for 20! the lengths of the corresponding iteration chains are 6, 51, and 101, respectively.

Partial sums of A064415.

			For n=1, no iteration is needed, so a(1)=0;
for n=2, the initial value is 2! = 2, so phi() must be applied once, thus a(2)=1;
for n=8, the iteration chain is {40320, 9216, 3072, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1}; its length = 14 = a(8) + 1, so the number of iterations applied to reach 1 is a(8)=13.

Amiram Eldar, 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, A000142, A003434, A053025, A053034.

Cf. also A064415.

Table[Length@ NestWhileList[EulerPhi, n!, # > 1 &] - 1, {n, 61}] (* or *)
Table[Length@ FixedPointList[EulerPhi, n!] - 2, {n, 61}] (* Michael De Vlieger, Jan 01 2017 *)

a(n) = {my(nb = 0, ns = n!); while (ns != 1, ns = eulerphi(ns); nb++); nb;} \\ Michel Marcus, Jan 01 2017

a(n) = A003434(A000142(n)). - Michel Marcus, Jan 01 2017

A060937 Number of iterations of d(n) (A000005) needed to reach 2 starting at n (n is counted).

Original entry on oeis.org

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

Offset: 2

Ahmed Fares (ahmedfares(AT)my-deja.com), May 06 2001

nonn

By the definition of a(n) we have for n >= 3 the recursion a(n) = a(d(n)) + 1. a(n) = 2 iff n is an odd prime.

			If n=12 the trajectory is {12,6,4,3,2}. Its length is 5, thus a(12)=5.

József Sándor, Dragoslav S. Mitrinovic, Borislav Crstici, Handbook of Number Theory I, Springer Science & Business Media, 2005, chapter 2, page 66.

Charles R Greathouse IV, Table of n, a(n) for n = 2..10000
Paul Erdős and Imre Kátai, On the growth of d_k(n), Fibonacci Quarterly, Vol. 7, No. 3 (1969), pp. 267-274.

Equals A036459 + 1.

Cf. A000005, A049108, A003434.

with(numtheory): interface(quiet=true): for n from 2 to 200 do if (1=1) then temp := n: count := 1: end if; while (temp > 2) do temp := tau(temp): count := count + 1: od; printf("%d,", count); od;

a[n_] := -1 + Length @ FixedPointList[DivisorSigma[0, #] &, n]; Array[a, 100, 2] (* Amiram Eldar, Jul 10 2021 *)

a(n)=my(t=1);while(n>2,n=numdiv(n);t++);t \\ Charles R Greathouse IV, Apr 07 2012

0 < lim sup_{n->oo} (a(n)-1)/log(log(log(n))) < oo (Erdős and Kátai, 1969). - Amiram Eldar, Jul 10 2021

More terms from Winston C. Yang (winston(AT)cs.wisc.edu), May 21 2001

A185816 Number of iterations of lambda(n) needed to reach 1.

Original entry on oeis.org

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

Offset: 1

Michel Lagneau, Feb 05 2011

nonn

lambda(n) is the Carmichael lambda function, A002322.

a(n) = (length of row n in table A246700) - 1. - Reinhard Zumkeller, Sep 02 2014

			If n = 23 the trajectory is 23, 22, 10, 4, 2, 1. Its length is 6, thus a(23) = 5.

T. D. Noe, 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 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. [Annotated copy with A-numbers]
Paul Erdős, A. Granville, C. Pomerance, and C. Spiro, On the Normal Behavior of the Iterates of some Arithmetic Functions, in Analytic number theory (Allerton Park, IL, 1989), Progr. Math., 85 Birkhäuser Boston, Boston, MA, (1990), 165-204.
Nick Harland, The iterated Carmichael lambda function, arXiv:1111.3667v1 [math.NT], Nov 15, 2011.
Nick Harland, The number of iterates of the Carmichael lambda function required to reach 1, arXiv:1203.4791 [math.NT], Mar 21, 2012.

Cf. A002322, A036459, A003434.

Cf. A027763, A173927, A246700.

a185816 n = if n == 1 then 0 else a185816 (a002322 n) + 1
-- Reinhard Zumkeller, Sep 02 2014

a:= n-> `if`(n=1, 0, 1+a(numtheory[lambda](n))):
seq(a(n), n=1..100);  # Alois P. Heinz, Apr 27 2019

f[n_] := Length[ NestWhileList[ CarmichaelLambda, n, Unequal, 2]] - 2; Table[f[n], {n, 1, 120}]

For n > 1: a(n) = a(A002322(n)) + 1. - Reinhard Zumkeller, Sep 02 2014

A256757 Number of iterations of A007733 required to reach 1.

Original entry on oeis.org

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

Offset: 1

Ivan Neretin, Apr 09 2015

In other words, the minimal height (not counting k) of the power tower 2^(2^(...^(2^k)...)) required to make it eventually constant modulo n (=A245970(n)) for sufficiently large k.

a(n) <= A227944(n) + 1. - Max Alekseyev, Oct 11 2016

Ivan Neretin, Table of n, a(n) for n = 1..10000

Cf. A007733, A256607 (second iteration), A256758 (positions of records), A003434, A227944 (similarly built upon the totient function).

a256757 n = fst $ until ((== 1) . snd)
            (\(i, x) -> (i + 1, fromIntegral $ a007733 x)) (0, n)
-- Reinhard Zumkeller, Apr 13 2015

A007733 = Function[n, MultiplicativeOrder[2, n/(2^IntegerExponent[n, 2])]];
a = Function[n, k = 0; m = n; While[m > 1, m = A007733[m]; k++]; k];
Table[a[n], {n, 100}] (* Ivan Neretin, Apr 13 2015 *)

a(n) = {if (n==1, return(0)); nb = 1; while((n = znorder(Mod(2, n/2^valuation(n, 2)))) != 1, nb++); nb;} \\ Michel Marcus, Apr 11 2015

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

A333609 The number of iterations of the infinitary totient function iphi (A091732) required to reach from n to 1.

Original entry on oeis.org

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

Offset: 1

Amiram Eldar, Mar 28 2020

nonn

			a(6) = 2 since there are 2 iterations from 6 to 1: iphi(6) = 2 and iphi(2) = 1.

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

Cf. A003434, A049865, A091732.

f[p_, e_] := p^(2^(-1 + Position[Reverse @ IntegerDigits[e, 2], 1])); iphi[1] = 1; iphi[n_] := Times @@ (Flatten@(f @@@ FactorInteger[n]) - 1); a[n_] := Length @ NestWhileList[iphi, n, # != 1 &] - 1; Array[a, 100]

A334195 a(1) = 0, then after the first differences of A064415.

Original entry on oeis.org

0, 1, 0, 1, 0, 0, 0, 1, -1, 1, 0, 0, 0, 0, 0, 1, 0, -1, 0, 1, -1, 1, 0, 0, 0, 0, -1, 1, 0, 0, 0, 1, -1, 1, -1, 0, 0, 0, 0, 1, 0, -1, 0, 1, -1, 1, 0, 0, -1, 1, 0, 0, 0, -1, 1, 0, -1, 1, 0, 0, 0, 0, -1, 2, -1, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -2, 2, 0, -1, 1, -1, 0, 1, 0, -1, 0, 1, -1, 1, -1, 1, 0, -1, 0, 1, 0, 0, 0, 0, -1

Offset: 1

Antti Karttunen, Apr 18 2020

sign

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

Cf. A003434, A064415, A334090, A334091, A334196.

Also, from a(3) onward the first differences of A054725.

A003434(n) = for(k=0, n, n>1 || return(k); n=eulerphi(n));
A064415(n) = if(1==n,0, A003434(n)-(n%2));
A334195(n) = if(1==n,0,A064415(n)-A064415(n-1));

a(1) = 0; and for n > 1, a(n) = A064415(n) - A064415(n-1).

a(n) = A334090(n) - A334091(n).

cp's OEIS Frontend

A336469 a(n) = A329697(phi(n)), where A329697 is totally additive with a(2) = 0 and a(p) = 1 + a(p-1) for odd primes.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A032358 Number of iterations of phi(n) needed to reach 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A058812 Irregular triangle of rows of numbers in increasing order. Row 1 = {1}. Row m + 1 contains all numbers k such that phi(k) is in row m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

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

A053044 a(n) is the number of iterations of the Euler totient function to reach 1, starting at n!.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A060937 Number of iterations of d(n) (A000005) needed to reach 2 starting at n (n is counted).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A185816 Number of iterations of lambda(n) needed to reach 1.

Views

Author

Keywords