login
Perfect totient numbers.
27

%I #92 Mar 24 2023 12:43:21

%S 3,9,15,27,39,81,111,183,243,255,327,363,471,729,2187,2199,3063,4359,

%T 4375,5571,6561,8751,15723,19683,36759,46791,59049,65535,140103,

%U 177147,208191,441027,531441,1594323,4190263,4782969,9056583,14348907,43046721

%N Perfect totient numbers.

%C It is trivial that perfect totient numbers must be odd. It is easy to show that powers of 3 are perfect totient numbers.

%C 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

%C Terms 15, 255, 65535 and 4294967295 also belong to A051179 (see Theorem 4 in Loomis link). - _Michel Marcus_, Mar 19 2014

%C For the first 64 terms, a(n) is approximately 1.56^n. - _Jud McCranie_, Jun 17 2017

%C 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

%D Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section B41, pp. 147-150.

%D 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.

%D József Sándor and Borislav Crstici, Handbook of Number theory II, Kluwer Academic Publishers, 2004, Chapter 3, pp. 240-242.

%D D. L. Silverman, Problem 1040, J. Recr. Math., Vol. 14 (1982); Solution by R. I. Hess, ibid., Vol. 15 (1983).

%D M. V. Subbarao, On a Function connected with phi(n), The Mathematics Student, Vol. 23 (1955), pp. 178-179.

%D T. Venkataraman, Perfect totient number, The Mathematics Student, Vol. 43 (1975), p. 178.

%H Jud McCranie, <a href="/A082897/b082897.txt">Table of n, a(n) for n = 1..64</a> (first 51 terms from Robert G. Wilson v)

%H Jovele G. Belmonte, <a href="https://animorepository.dlsu.edu.ph/etd_masteral/3449/">On perfect totient numbers</a>, Masteral Thesis, De La Salle University, 2006.

%H Li-Xia Dai and Yong-Gao Chen, <a href="http://caod.oriprobe.com/articles/13427719/A_note_on_perfect_totient_numbers.htm">A note on perfect totient numbers</a>, Journal of Northeast Normal University, Vol. 39, No. 4 (2007), pp. 17-19.

%H Tuukka Hyvärinen, <a href="https://trepo.tuni.fi/handle/10024/97744">Täydelliset totienttiluvut</a> (in Finnish), Master's thesis, Tampere University, 2015; <a href="https://core.ac.uk/download/pdf/250138377.pdf">alternative link</a>.

%H Douglas E. Iannucci, Deng Moujie and Graeme L. Cohen, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Cohen2/cohen50.html">On Perfect Totient Numbers</a>, Journal of Integer Sequences, Vol. 6 (2003), Article 03.4.5.

%H Paul Loomis, Michael Plytage and John Polhill, <a href="http://www.jstor.org/stable/27646564">Summing up the Euler phi function</a>, The College Mathematics Journal, Vol. 39, No. 1, Jan. 2008.

%H Florian Luca, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Luca/luca66.html">On the Distribution of Perfect Totients</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.4.4.

%H A. L. Mohan and D. Suryanarayana, <a href="https://doi.org/10.1007/BFb0097177">Perfect totient numbers</a>, 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.

%H Deng Moujie, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Deng/deng1.html">A Note On Perfect Totient Numbers</a>, Journal of Integer Sequences, Vol. 12 (2009), Article 09.6.2.

%H Igor E. Shparlinski, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Shparlinski/shpar43.html">On the sum of iterations of the Euler function</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.6.

%H Hans Sieburg and Michael Kentgens, <a href="https://www.researchgate.net/publication/258424386_On_Phi-perfect_numbers">On Phi-perfect numbers</a>, in: J. Akiyama et al. (eds.), Number Theory and Combinatorics, Japan 1984, World Scientific, 1985, pp. 245-254.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Perfect_totient_number">Perfect totient number</a>.

%F 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)).

%F n such that n = A092693(n).

%F n such that 2n = A053478(n). - _Vladeta Jovovic_, Jul 02 2004

%F n log log log log n << a(n) <= 3^n. - _Charles R Greathouse IV_, Mar 22 2012

%e 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.

%p with(numtheory):

%p A082897_list := proc(N) local k,p,n,L;

%p L := NULL;

%p for n from 3 by 2 to N do

%p k := 0; p := phi(n);

%p while 1 < p do k := k + p; p := phi(p) od;

%p if k + 1 = n then L := L,n fi

%p od; L end: # _Peter Luschny_, Nov 01 2010

%t 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

%t perfTotQ[n_] := Plus @@ FixedPointList[ EulerPhi@ # &, n] == 2n + 1; Select[Range[1000], perfTotQ] (* _Robert G. Wilson v_, Nov 06 2010 *)

%o (PARI) S(n)={n=eulerphi(n);if(n==1,1,n+S(n))}

%o for(n=2,1e3,if(S(n)==n,print1(n", "))) \\ _Charles R Greathouse IV_, Mar 29 2012; Corrected by _Dana Jacobsen_, Dec 16 2018

%o (Perl) 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

%o (Python)

%o from itertools import count, islice

%o from gmpy2 import digits

%o from sympy import totient

%o def A082897_gen(startvalue=3): # generator of terms >= startvalue

%o for n in count((k:=max(startvalue,3))+1-(k&1),2):

%o t = digits(n,3)

%o if t.count('0') == len(t)-1:

%o yield n

%o else:

%o m, s = n, 1

%o while (m:=totient(m))>1:

%o s += m

%o if s == n:

%o yield n

%o A082897_list = list(islice(A082897_gen(),20)) # _Chai Wah Wu_, Mar 24 2023

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

%Y Cf. A051179, A125734.

%K nonn

%O 1,1

%A _Douglas E. Iannucci_, Jul 21 2003

%E Corrected by _T. D. Noe_, Mar 11 2004