A032358 -id:A032358 - cp's OEIS frontend

A290149 Totient sublime numbers: numbers k such that the number of terms in the iterations of phi(k) from k to 1, A032358(k)+2, and their sum, A092693(k) are both perfect totient numbers (A082897).

6, 2916, 4374, 109100, 113708, 3188646

Offset: 1

Amiram Eldar, Jul 21 2017

Analogous to A081357 (sublime numbers), as A082897 (perfect totient numbers) is analogous to A000396 (perfect numbers).

No other terms below 10^8.

			There are 9 terms in the iterations of phi(k) for 2916: 2916, 972, 324, 108, 36, 12, 4, 2, 1. Their sum is 4375. Both 9 and 4375 are perfect totient numbers (A082897).

Cf. A032358, A081357, A082897, A092693.

iterList [n_] := FixedPointList[EulerPhi@# &, n]; sumIter [n_] := Plus @@ iterList[n] - 1; numIter[n_] := Length[iterList[n]] - 1; perfTotQ[n_] := sumIter[n] == 2 n; totSublimeQ[n_] := perfTotQ[numIter[n]] && perfTotQ[sumIter[n]]; Select[Range [10^8], totSublimeQ]

A053478 Sum of iterates when phi, A000010, is iterated until fixed point 1.

Original entry on oeis.org

1, 3, 6, 7, 12, 9, 16, 15, 18, 17, 28, 19, 32, 23, 30, 31, 48, 27, 46, 35, 40, 39, 62, 39, 60, 45, 54, 47, 76, 45, 76, 63, 68, 65, 74, 55, 92, 65, 78, 71, 112, 61, 104, 79, 84, 85, 132, 79, 110, 85, 114, 91, 144, 81, 126, 95, 112, 105, 164, 91, 152, 107, 118, 127, 144, 101

Offset: 1

Labos Elemer, Jan 14 2000

nonn

For n = 2^w, the sum is 2^(w+1) - 1.

			If phi is applied repeatedly to n = 91, the iterates {91, 72, 24, 8, 4, 2, 1} are obtained. Their sum is a(91) = 91 + 72 + 24 + 8 + 4 + 2 + 1 = 202.

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

Cf. A000010, A010554, A049099, A049100, A049107, A049108, A032358.

Row sums of A375478.

a053478 = (+ 1) . sum . takeWhile (/= 1) . iterate a000010
-- Reinhard Zumkeller, Oct 27 2011

f[n_] := Plus @@ Drop[ FixedPointList[ EulerPhi, n], -1]; Table[ f[n], {n, 66}] (* Robert G. Wilson v, Dec 16 2004 *)
f[1] := 1; f[n_] := n + f[EulerPhi[n]]; Table[f[n], {n, 66}] (* Carlos Eduardo Olivieri, May 26 2015 *)

a(n)=my(s=n);while(n>1,s+=n=eulerphi(n)); s \\ Charles R Greathouse IV, Feb 21 2013

a(n) = n + a(phi(n)).

a(n) = A092693(n) + n. - Vladeta Jovovic, Jul 02 2004

A071575 Number of iterations of cototient(n) needed to reach 1 (cototient(n) = n-phi(n)).

Original entry on oeis.org

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

Offset: 1

Benoit Cloitre, May 31 2002

			cototient(6) = 4, cototient(4) = 2, cototient(2) = 1, hence a(6) = 3.

T. D. Noe, Table of n, a(n) for n=1..10000
Paul Ellis, Jason Shi, Thotsaporn Aek Thanatipanonda, and Andrew Tu, Two Games on Arithmetic Functions: SALIQUANT and NONTOTIENT, arXiv:2309.01231 [math.NT], 2023. See p. 7.

Cf. A032358, A051953, A076640.

cot[n_] := n - EulerPhi[n]; a[n_] := -1 + Length @ NestWhileList[cot, n, # > 1 &]; Array[a, 100] (* Amiram Eldar, May 19 2022 *)

for(n=1,150,s=n; t=0; while(s!=1,t++; s=s-eulerphi(s); if(s==1,print1(t,","); ); ))

a(n) = a(n-phi(n))+1, a(1) = 0.

a(n) = A076640(n)-1.

Prepended a(1)=0 and changed offset. - T. D. Noe, Dec 03 2008

A334196 a(1) = 0, then after the first differences of A003434.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Apr 18 2020

sign

Also, from a(2) onward the first differences of A049108, and from a(3) onward the first differences of A032358.

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

Cf. A000010, A003434, A032358, A049108, A334195.

Differences[Array[Length[FixedPointList[EulerPhi, #]] &, 100, 0]] (* Paolo Xausa, Aug 18 2024 *)

A003434(n) = for(k=0, n, n>1 || return(k); n=eulerphi(n));
A334196(n) = if(1==n,0,A003434(n)-A003434(n-1));

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

A340762 Numbers k such that iterations of phi(k), phi(phi(k)), ... end in ... 4, 2, 1.

Original entry on oeis.org

4, 5, 8, 10, 11, 12, 13, 15, 16, 17, 20, 21, 22, 23, 24, 25, 26, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72

Offset: 1

Franz Vrabec, Jan 20 2021

nonn

Infinite set (see reference).

			11 is in the list because phi(phi(11)) = phi(10) = 4.

Robert Israel, Table of n, a(n) for n = 1..10000
Eliot T. Jacobson and Alan E. Parks, Infinite branches of the phi-tree, Amer. Math. Monthly, Vol. 93, No. 7 (August-September 1986), pp. 552-554.
Keith Matthews, Solving phi(x)=n, where phi(x) is Euler's totient function.

Cf. A000010, A340765 (complement relative to {n>=4}).

Cf. A003434, A032358, A049108.

filter:= proc(n) option remember;
  if n < 4 then false
  elif n = 4 then true
  else procname(numtheory:-phi(n))
  fi
end proc:
select(filter, [$4..100]); # Robert Israel, Dec 23 2021

Select[Range[4, 72], FixedPointList[EulerPhi, #][[-4]] == 4 &] (* Amiram Eldar, Jan 27 2021 *)

isok(k) = if (k>=4, while((k!=6) && (k!=4), k=eulerphi(k))); k == 4; \\ Michel Marcus, Feb 01 2021

A340765 Numbers k such that iterations of phi(k), phi(phi(k)), ... end in ... 6, 2, 1.

Original entry on oeis.org

6, 7, 9, 14, 18, 19, 27, 38, 54, 81, 162, 163, 243, 326, 486, 487, 729, 974, 1458, 1459, 2187, 2918, 4374, 6561, 13122, 19683, 39366, 39367, 59049, 78734, 118098, 177147, 354294, 531441, 1062882, 1594323, 3188646, 4782969, 9565938, 14348907, 28697814, 43046721, 86093442, 86093443, 129140163, 172186886

Offset: 1

Franz Vrabec, Jan 20 2021

nonn

Infinite set (see reference).

Contains 3^k for k >= 2 and 2*3^k for k >= 1, and all members of A111974 except 3. - Robert Israel, Dec 23 2021

			19 is in the list because phi(phi(19)) = phi(18) = 6.

Robert Israel, Table of n, a(n) for n = 1..1000
Eliot T. Jacobson and Alan E. Parks, Infinite branches of the phi-tree, Amer. Math. Monthly, Vol. 93, No. 7 (August-September 1986), pp. 552-554.
Keith Matthews, Solving phi(x)=n, where phi(x) is Euler's totient function.

Cf. A000010, A340762 (complement relative to {n>=4}).

Cf. A003434, A032358, A049108, A111974.

R:= {6}: Agenda:= {6}: count:= 1:
while count - nops(Agenda) < 99 do
  v:= min(Agenda);
  W:= convert(numtheory:-invphi(v),set);
  count:= count + nops(W);
  Agenda:= Agenda minus {v} union W;
  R:= R union W;
od:
sort(select(`<=`, convert(R,list),min(Agenda))); # Robert Israel, Dec 23 2021

Select[Range[4, 10000], FixedPointList[EulerPhi, #][[-4]] == 6 &] (* Amiram Eldar, Jan 27 2021 *)

isok(k) = if (k>=6, while((k!=6) && (k!=4), k=eulerphi(k))); k == 6; \\ Michel Marcus, Feb 01 2021

A145443 In class n of the phi iteration, the number of primes less than the smallest composite number.

Original entry on oeis.org

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

Offset: 1

T. D. Noe, Oct 10 2008

nonn

A number is in class n if n iterations of Euler's phi function produces 2 (see A032358). a(n)>0 for the n in A136040.

			According to A005239, class 5 begins with 41, 47, 51, 53, 55, 59, 61. There are two primes less than the composite 51. Hence a(5)=2.

T. D. Noe, Table of n, a(n) for n=1..1000
T. D. Noe, Computing Numbers in Section I of the Totient Iteration

A098196

Modified comment. - T. D. Noe, Nov 18 2008

Extension T. D. Noe, Nov 18 2008

cp's OEIS Frontend

A290149 Totient sublime numbers: numbers k such that the number of terms in the iterations of phi(k) from k to 1, A032358(k)+2, and their sum, A092693(k) are both perfect totient numbers (A082897).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A053478 Sum of iterates when phi, A000010, is iterated until fixed point 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A071575 Number of iterations of cototient(n) needed to reach 1 (cototient(n) = n-phi(n)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A334196 a(1) = 0, then after the first differences of A003434.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A340762 Numbers k such that iterations of phi(k), phi(phi(k)), ... end in ... 4, 2, 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A340765 Numbers k such that iterations of phi(k), phi(phi(k)), ... end in ... 6, 2, 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A145443 In class n of the phi iteration, the number of primes less than the smallest composite number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions