A053478 -id:A053478 - cp's OEIS frontend

A082897 Perfect totient numbers.

3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375, 5571, 6561, 8751, 15723, 19683, 36759, 46791, 59049, 65535, 140103, 177147, 208191, 441027, 531441, 1594323, 4190263, 4782969, 9056583, 14348907, 43046721

Offset: 1

Douglas E. Iannucci, Jul 21 2003

nonn

It is trivial that perfect totient numbers must be odd. It is easy to show that powers of 3 are perfect totient numbers.
The product of the first n Fermat primes (A019434) is also a perfect totient number. There are 57 terms under 10^11. - Jud McCranie, Feb 24 2012
Terms 15, 255, 65535 and 4294967295 also belong to A051179 (see Theorem 4 in Loomis link). - Michel Marcus, Mar 19 2014
For the first 64 terms, a(n) is approximately 1.56^n. - Jud McCranie, Jun 17 2017
These numbers were first studied in 1939 by the Spanish mathematician Laureano Pérez-Cacho Villaverde (1900-1957). The term "perfect totient number" was coined by Venkataraman (1975). - Amiram Eldar, Mar 10 2021

			327 is a perfect totient number because 327 = 216 + 72 + 24 + 8 + 4 + 2 + 1. Note that 216 = phi(327), 72 = phi(216), 24 = phi(72) and so on.

Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section B41, pp. 147-150.
L. Pérez-Cacho, Sobre la suma de indicadores de órdenes sucesivos (in Spanish), Revista Matematica Hispano-Americana, Vol.5, No. 3 (1939), pp. 45-50.
József Sándor and Borislav Crstici, Handbook of Number theory II, Kluwer Academic Publishers, 2004, Chapter 3, pp. 240-242.
D. L. Silverman, Problem 1040, J. Recr. Math., Vol. 14 (1982); Solution by R. I. Hess, ibid., Vol. 15 (1983).

Jud McCranie, Table of n, a(n) for n = 1..64 (first 51 terms from Robert G. Wilson v)
Jovele G. Belmonte, On perfect totient numbers, Masteral Thesis, De La Salle University, 2006.
Li-Xia Dai and Yong-Gao Chen, A note on perfect totient numbers, Journal of Northeast Normal University, Vol. 39, No. 4 (2007), pp. 17-19.
Tuukka Hyvärinen, Täydelliset totienttiluvut (in Finnish), Master's thesis, Tampere University, 2015; alternative link.
Douglas E. Iannucci, Deng Moujie and Graeme L. Cohen, On Perfect Totient Numbers, Journal of Integer Sequences, Vol. 6 (2003), Article 03.4.5.
Paul Loomis, Michael Plytage and John Polhill, Summing up the Euler phi function, The College Mathematics Journal, Vol. 39, No. 1, Jan. 2008.
Florian Luca, On the Distribution of Perfect Totients, Journal of Integer Sequences, Vol. 9 (2006), Article 06.4.4.
A. L. Mohan and D. Suryanarayana, Perfect totient numbers, in: K. Alladi (ed.), Number Theory, Proceedings of the Third Matscience Conference Held at Mysore, India, June 3-6, 1981, Lecture Notes in Mathematics, Vol 938, Springer, Berlin, Heidelber, 1982, pp. 101-105.
Deng Moujie, A Note On Perfect Totient Numbers, Journal of Integer Sequences, Vol. 12 (2009), Article 09.6.2.
Igor E. Shparlinski, On the sum of iterations of the Euler function, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.6.
Hans Sieburg and Michael Kentgens, On Phi-perfect numbers, in: J. Akiyama et al. (eds.), Number Theory and Combinatorics, Japan 1984, World Scientific, 1985, pp. 245-254.
M. V. Subbarao, On a Function connected with phi(n), The Mathematics Student, Vol. 23 (1955), pp. 178-179; entire volume.
T. Venkataraman, Perfect totient number, The Mathematics Student, Vol. 43, No. 2 (1975), p. 178; entire issue.
Wikipedia, Perfect totient number.

Cf. A092693 (sum of iterated phi(n)). See also A091847.

Cf. A051179, A125734.

with(numtheory):
A082897_list := proc(N) local k,p,n,L;
L := NULL;
for n from 3 by 2 to N do
k := 0; p := phi(n);
while 1 < p do k := k + p; p := phi(p) od;
if k + 1 = n then L := L,n fi
od; L end: # Peter Luschny, Nov 01 2010

kMax = 57395631; a = Table[0, {kMax}]; PTNs = {}; Do[e = EulerPhi[k]; a[[k]] = e + a[[e]]; If[k == a[[k]], AppendTo[PTNs, k]], {k, 2, kMax}]; PTNs
perfTotQ[n_] := Plus @@ FixedPointList[ EulerPhi@ # &, n] == 2n + 1; Select[Range[1000], perfTotQ] (* Robert G. Wilson v, Nov 06 2010 *)

S(n)={n=eulerphi(n);if(n==1,1,n+S(n))}
for(n=2,1e3,if(S(n)==n,print1(n", "))) \\ Charles R Greathouse IV, Mar 29 2012; Corrected by Dana Jacobsen, Dec 16 2018

use ntheory "euler_phi"; sub S { my $n=euler_phi(shift); return 1 if $n == 1; $n+S($n); }   for (2..1e4) { say if $==S($); } # Dana Jacobsen, Dec 16 2018

from itertools import count, islice
from gmpy2 import digits
from sympy import totient
def A082897_gen(startvalue=3): # generator of terms >= startvalue
    for n in count((k:=max(startvalue,3))+1-(k&1),2):
        t = digits(n,3)
        if t.count('0') == len(t)-1:
            yield n
        else:
            m, s = n, 1
            while (m:=totient(m))>1:
                s += m
            if s == n:
                yield n
A082897_list = list(islice(A082897_gen(),20)) # Chai Wah Wu, Mar 24 2023

n is a perfect totient number if S(n) = n, where S(n) = phi(n) + phi^2(n) +  ... + 1, where phi is Euler's totient function and phi^2(n) = phi(phi(n)), ..., phi^k(n) = phi(phi^(k-1)(n)).
n such that n = A092693(n).
n such that 2n = A053478(n). - Vladeta Jovovic, Jul 02 2004
n log log log log n << a(n) <= 3^n. - Charles R Greathouse IV, Mar 22 2012

Corrected by T. D. Noe, Mar 11 2004

A092693 Sum of iterated phi(n).

Original entry on oeis.org

0, 1, 3, 3, 7, 3, 9, 7, 9, 7, 17, 7, 19, 9, 15, 15, 31, 9, 27, 15, 19, 17, 39, 15, 35, 19, 27, 19, 47, 15, 45, 31, 35, 31, 39, 19, 55, 27, 39, 31, 71, 19, 61, 35, 39, 39, 85, 31, 61, 35, 63, 39, 91, 27, 71, 39, 55, 47, 105, 31, 91, 45, 55, 63, 79, 35, 101, 63, 79, 39, 109, 39, 111

Offset: 1

T. D. Noe, Mar 04 2004

nonn

Iannucci, Moujie and Cohen examine perfect totient numbers: n such that a(n) = n.

			a(100) = 71 because the iterations of phi (40, 16, 8, 4, 2, 1) sum to 71.

T. D. Noe, Table of n, a(n) for n = 1..10000
C. Defant, On Arithmetic Functions Related to Iterates of the Schemmel Totient Functions, J. Int. Seq. 18 (2015) # 15.2.1
P. Erdos and M. V. Subbarao, On the iterates of some arithmetic functions, The theory of arithmetic functions (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich. 1971), Lecture Notes in Math., 251 , pp. 119-125, Springer, Berlin, 1972. [alternate link]
Douglas E. Iannucci, Deng Moujie and Graeme L. Cohen, On perfect totient numbers, J. Integer Sequences, 6 (2003), #03.4.5.

Cf. A003434 (iterations of phi(n) needed to reach 1), A092694 (iterated phi product).

Cf. A082897 and A091847 (perfect totient numbers).

a092693 1 = 0
a092693 n = (+ 1) $ sum $ takeWhile (/= 1) $ iterate a000010 $ a000010 n
-- Reinhard Zumkeller, Oct 27 2011

nMax=100; a=Table[0, {nMax}]; Do[e=EulerPhi[n]; a[[n]]=e+a[[e]], {n, 2, nMax}]; a (* T. D. Noe *)
Table[Plus @@ FixedPointList[EulerPhi, n] - (n + 1), {n, 72}] (* Alonso del Arte, Jan 29 2007 *)

a(n)=my(k);while(n>1,k+=n=eulerphi(n));k \\ Charles R Greathouse IV, Mar 22 2012

from sympy import totient
from math import prod
def f(n):
    m = n
    while m > 1:
        m = totient(m)
        yield m
def A092693(n): return sum(f(n)) # Chai Wah Wu, Nov 14 2021

a(1) = 0, a(n) = phi(n) + a(phi(n))
a(n) = A053478(n) - n. - Vladeta Jovovic, Jul 02 2004
Erdős & Subbarao prove that a(n) ~ phi(n) for almost all n. In particular, a(n) < n for almost all n. The proportion of numbers up to N for which a(n) > n is at most 1/log log log log N. - Charles R Greathouse IV, Mar 22 2012

A288452 Pseudoperfect totient numbers: numbers n such that equal the sum of a subset of their iterated phi(n).

Original entry on oeis.org

3, 5, 7, 9, 11, 13, 15, 17, 19, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 47, 49, 51, 53, 55, 59, 61, 65, 67, 69, 71, 73, 77, 79, 81, 83, 85, 87, 89, 97, 101, 103, 107, 109, 111, 113, 115, 119, 121, 123, 125, 127, 131, 137, 139, 141, 143, 149, 151, 153, 155

Offset: 1

Amiram Eldar, Jun 09 2017

nonn

Analogous to A005835 (pseudoperfect numbers) as A082897 (perfect totient numbers) is analogous to A000396 (perfect numbers).
All the odd primes are in this sequence.
Number of terms < 10^k: 4, 40, 350, 2956, 24842, etc. - Robert G. Wilson v, Jun 17 2017
All terms are odd. If n is even, phi(n) <= n/2, and except for n = 2, we will have phi(n) also even. So the sum of the phi sequence < n*(1/2 + 1/4 + ...) = n. - Franklin T. Adams-Watters, Jun 25 2017

			The iterated phi of 25 are 20, 8, 4, 2, 1 and 25 = 20 + 4 + 1.

Robert G. Wilson v, Table of n, a(n) for n = 1..10000

Supersequence of A082897. Subsequence of A286265.

Cf. A000010, A000396, A005835, A053478, A092693.

pseudoPerfectTotQ[n_]:= Module[{tots = Most[Rest[FixedPointList[EulerPhi@# &, n]]]}, MemberQ[Total /@ Subsets[tots, Length[tots]], n]]; Select[Range[155], pseudoPerfectTotQ]

subsetSum(v, target)=if(setsearch(v,target), return(1)); if(#v<2, return(target==0)); my(u=v[1..#v-1]); if(target>v[#v] && subsetSum(u, target-v[#v]), return(1)); subsetSum(u,target);
is(n)=if(isprime(n), return(n>2)); my(v=List(),k=n); while(k>1, listput(v,k=eulerphi(k))); subsetSum(Set(v),n) \\ Charles R Greathouse IV, Jun 25 2017

A375478 Irregular triangle read by rows in which row n lists the iterates of the phi(x) map from n to 1, where phi(x) is Euler's totient function (A000010).

Original entry on oeis.org

1, 2, 1, 3, 2, 1, 4, 2, 1, 5, 4, 2, 1, 6, 2, 1, 7, 6, 2, 1, 8, 4, 2, 1, 9, 6, 2, 1, 10, 4, 2, 1, 11, 10, 4, 2, 1, 12, 4, 2, 1, 13, 12, 4, 2, 1, 14, 6, 2, 1, 15, 8, 4, 2, 1, 16, 8, 4, 2, 1, 17, 16, 8, 4, 2, 1, 18, 6, 2, 1, 19, 18, 6, 2, 1, 20, 8, 4, 2, 1, 21, 12, 4, 2, 1

Offset: 1

Paolo Xausa, Aug 17 2024

First differs from A246700 at n = 22.

			Triangle begins:
   1;
   2, 1;
   3, 2, 1;
   4, 2, 1;
   5, 4, 2, 1;
   6, 2, 1;
   7, 6, 2, 1;
   8, 4, 2, 1;
   9, 6, 2, 1;
  10, 4, 2, 1;
  ...

Paolo Xausa, Table of n, a(n) for n = 1..10636 (rows 1..1200 of the triangle, flattened).
Index entries for sequences related to totient function phi(n).

Supersequence of A246700.

Cf. A000010, A049108 (row lengths), A053478 (row sums).

Array[Most[FixedPointList[EulerPhi, #]] &, 25]

T(n,1) = n; T(n,k) = A000010(T(n,k-1)), for k = 2..A049108(n).

A335121 Admirable totient numbers: numbers that are equal to the sum of their iterated phi, with one of them taken with a minus sign.

Original entry on oeis.org

5, 7, 33, 35, 55, 87, 95, 175, 201, 215, 219, 245, 531, 747, 927, 939, 1047, 1295, 1463, 1473, 1551, 1855, 2015, 2103, 2421, 2431, 2547, 2619, 2631, 2765, 3535, 4833, 5067, 5215, 7655, 7743, 7851, 10503, 11127, 11307, 13055, 13707, 16247, 16593, 17805, 18471

Offset: 1

Amiram Eldar, May 24 2020

nonn

Analogous to A111592 (admirable numbers) as A082897 (perfect totient numbers) is analogous to A000396 (perfect numbers).

			5 is a term since the values of the iterated phi of 5 are 4, 2 and 1 and 5 = 4 + 2 - 1.

Amiram Eldar, Table of n, a(n) for n = 1..171 (terms below 10^9)

Subsequence of A286265.

Cf. A000010, A053478, A082897, A111592, A288452.

admTotQ[n_] := Module[{s = Most @ Rest @ FixedPointList[EulerPhi, n]}, (ab = Plus @@ s - n) > 0 && EvenQ[ab] && ab/2 < n && MemberQ[s, ab/2]]; Select[Range[8000], admTotQ]

A340265 a(n) = n + 1 - a(phi(n)).

Original entry on oeis.org

1, 2, 2, 3, 3, 5, 3, 6, 5, 8, 4, 10, 4, 10, 10, 11, 7, 14, 6, 15, 12, 15, 9, 19, 11, 17, 14, 19, 11, 25, 7, 22, 19, 24, 17, 27, 11, 25, 21, 30, 12, 33, 11, 30, 27, 32, 16, 38, 17, 36, 30, 34, 20, 41, 26, 38, 31, 40, 20, 50, 12, 38, 37, 43, 28, 52, 16, 47, 40, 52, 20, 54, 20, 48

Offset: 1

Emanuel Landeholm, Jan 03 2021

Since phi(n) < n, a(n) only depends on earlier values a(k), k < n. This makes the sequences computable using dynamic programming. The motivation for the "+ 1" is that without it the sequence becomes half-integer as a(1) would equal 1/2.

1 <= a(n) <= n. Proof: Suppose 1 <= a(k) <= k for all k < n. Then a(k + 1) = k + 1 + 1 - a(phi(k + 1)). As 1 <= a(phi(k)) <= k we have 2 <= k + 1 + 1 - k <= k + 1 + 1 - a(phi(k + 1)) = a(k + 1) <= k + 1.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000010, A053478.

f:= proc(n) option remember; n+ 1 - procname(numtheory:-phi(n)); end proc:
f(1):= 1:
map(f, [$1..100]); # Robert Israel, Jan 06 2021

Function[, If[#1 == 1, 1, # + 1 - #0[EulerPhi@#]], Listable]@Range[70]

first(n) = {my(res = vector(n)); res[1] = 1; for(i = 2, n, res[i] = i + 1 - res[eulerphi(i)]); res} \\ David A. Corneth, Jan 03 2021

from sympy import totient as phi
N = 100
# a(n) = n + 1 - a(phi(n)), n > 0, a(0) = 0
a = [ 0 ] * N
# a(1) = 1 + 1 - a(phi(1)) = 2 - a(1) => 2 a(1) = 2 => a(1) = 1
# a(n), n > 1 computed using dynamic programming
a[1] = 1
for n in range(2, N):
  a[n] = n + 1 - a[phi(n)]
print(a[1:])

from sympy import totient as phi
def a(n): return 1 if n==1 else n + 1 - a(phi(n))
print([a(n) for n in range(1, 100)]) # Michael S. Branicky, Jan 03 2021

a(n) = n + Sum_{k=1..floor(log_2(n))} (-1)^k*(phi^k(n) - 1), where phi^k(n) is the k-th iterate of phi(n). - Ridouane Oudra, Oct 10 2023

A181627 Number of iterations of phi(n) if n is a perfect totient number.

Original entry on oeis.org

2, 3, 4, 4, 5, 5, 6, 7, 6, 8, 7, 8, 8, 7, 8, 10, 11, 11, 11, 11, 9, 10, 12, 10, 14, 13, 11, 16, 14, 12, 16, 17, 13, 14, 19, 15, 20, 16, 17, 18, 18, 19, 24, 19, 20, 21, 22, 29, 32, 28, 30, 22, 29, 23, 30, 32, 24, 25, 31, 35, 26, 34, 35, 27

Offset: 1

Peter Luschny, Nov 02 2010

Let phi^{i} denote the i-th iteration of phi. a(n) is the smallest integer k such that phi^{k}(n) = 1 and Sum_{1<=i<=a(n)} phi^{i}(n) = n.

Paul Loomis, Michael Plytage and John Polhill, Summing up the Euler phi function, The College Mathematics Journal, Vol. 39, No. 1, Jan. 2008, pp. 34-42.
Peter Luschny, Sequences related to Euler's totient function.

Cf. A000010, A082897, A053478, A049108.

lst = (* get list from A082897 *); f[n_] := Length@ FixedPointList[ EulerPhi@ # &, n] - 2; f@# & /@ lst (* Robert G. Wilson v, Nov 06 2010 *)

a(n) = A049108(A082897(n)) - 1. - Amiram Eldar, Apr 14 2023

More terms from Robert G. Wilson v, Nov 06 2010

More terms from Amiram Eldar, Apr 14 2023

cp's OEIS Frontend

A082897 Perfect totient numbers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Perl

Python

Formula

Extensions

A092693 Sum of iterated phi(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Formula

A288452 Pseudoperfect totient numbers: numbers n such that equal the sum of a subset of their iterated phi(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A375478 Irregular triangle read by rows in which row n lists the iterates of the phi(x) map from n to 1, where phi(x) is Euler's totient function (A000010).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A335121 Admirable totient numbers: numbers that are equal to the sum of their iterated phi, with one of them taken with a minus sign.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A340265 a(n) = n + 1 - a(phi(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Python

Formula

A181627 Number of iterations of phi(n) if n is a perfect totient number.

Views