Perfect total number

The totient of a number is defined in number theory as , which is also called Euler's Phi function and indicates how many coprime natural numbers there are that are not greater than . ${\ displaystyle k}$ ${\ displaystyle \ varphi (k)}$ ${\ displaystyle k}$ ${\ displaystyle x}$ ${\ displaystyle k}$

A perfect totiente number (from the English perfect totient number ) is a natural number , which is obtained as follows: ${\ displaystyle n}$

Start with the number and form its totient . Now one forms the totient from this totient and so on until one reaches the value . If the totients obtained in this way are added and the total is exactly the initial number , then this is a perfectly totient number. ${\ displaystyle n}$ ${\ displaystyle \ varphi (n)}$ ${\ displaystyle \ varphi (n)}$ ${\ displaystyle \ varphi (\ varphi (n))}$ ${\ displaystyle 1}$ ${\ displaystyle n}$ ${\ displaystyle n}$

In mathematical terms, this means:

Be

{\ displaystyle \ varphi ^ {i} (n): = \ left \ {{\ begin {matrix} \ varphi (n) & {\ mbox {for}} i = 1 \\\ varphi (\ varphi ^ {i -1} (n)) & {\ mbox {otherwise}} \ end {matrix}} \ right.}

for the iterated totients.

Furthermore be a natural number with .

{\ displaystyle c}

{\ displaystyle \ varphi ^ {c} (n) = 2}

Then is a perfectly totient number if:

{\ displaystyle n}

{\ displaystyle n = \ sum _ {i = 1} ^ {c + 1} \ varphi ^ {i} (n)}

These numbers were first studied by mathematician Laureano Pérez-Cacho in 1939. After a long break, in 1975 the mathematician T. Venkataraman and in 1982 the two mathematicians AL Mohan and D. Suryanarayana dealt with these numbers.

Examples

Be . ${\ displaystyle n = 9}$

For number there are coprime numbers which are smaller than , namely and . So is .

{\ displaystyle n = 9}

{\ displaystyle 6}

{\ displaystyle n = 9}

{\ displaystyle 1,2,4,5,7}

{\ displaystyle 8}

{\ displaystyle \ varphi (9) = 6}

Now you determine the totient of . With number there are only prime numbers than what smaller , namely, and . So is .

{\ displaystyle 6}

{\ displaystyle 6}

{\ displaystyle 2}

{\ displaystyle 6}

{\ displaystyle 1}

{\ displaystyle 5}

{\ displaystyle \ varphi (6) = 2}

What remains is the determination of the totient of . With number there is only one prime number than what smaller , namely . So is .

{\ displaystyle 2}

{\ displaystyle 2}

{\ displaystyle 2}

{\ displaystyle 1}

{\ displaystyle \ varphi (2) = 1}

One receives .

{\ displaystyle \ varphi (\ varphi (\ varphi (9))) = \ varphi (\ varphi (6)) = \ varphi (2) = 1}

If you add the totients obtained in this way , you get the starting number. So is a perfectly total number.

{\ displaystyle 6 + 2 + 1 = 9 = n}

{\ displaystyle n = 9}

The following numbers are the smallest perfectly 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, ... ( continuation A082897 in OEIS )

There are 61 perfectly totient numbers that are less than a trillion (that is, less than ).

{\ displaystyle 10 ^ {12}}

properties

Every perfectly total number is odd .

Proof:

A feature of the Totienten is that for always an even number results (only gives an odd Totienten). When checking whether a number is a perfectly totient number or not, only even numbers have to be added up at the beginning, which ultimately results in an even number as the sum. At the very end , an odd number has to be added to this even number , so that the total is an odd number. However, this totient total is the value of the perfectly totient number, from which one can conclude that all perfectly totient numbers must be odd.

{\ displaystyle \ varphi (n)}

{\ displaystyle n \ geq 3}

{\ displaystyle \ varphi (1) = \ varphi (2) = 1}

{\ displaystyle \ varphi (2) = 1}

{\ displaystyle \ Box}

All numbers of the form with , are perfect totiente numbers. ${\ displaystyle n = 3 ^ {k}}$ ${\ displaystyle k \ in \ mathbb {N}}$ ${\ displaystyle k> 0}$

Proof of the claim:

Proof:

The following calculation rule of the Euler's Phi function is used:

{\ displaystyle \ quad \ varphi (p ^ {k}) = p ^ {k-1} (p-1)}

Thus:

{\ displaystyle \ varphi (3 ^ {k}) = 3 ^ {k-1} \ cdot (3-1) = 2 \ cdot 3 ^ {k-1}}

The following property of Euler's Phi function is also used for coprime numbers and :

{\ displaystyle m}

{\ displaystyle n}

{\ displaystyle \ quad \ varphi (m \ cdot n) = \ varphi (m) \ cdot \ varphi (n)}

Thus, taking into account the above two rules:

{\ displaystyle \ varphi ^ {2} (3 ^ {k}) = \ varphi (2 \ cdot 3 ^ {k-1}) = \ varphi (2) \ cdot \ varphi (3 ^ {k-1}) = 1 \ times 2 \ times 3 ^ {k-2} = 2 \ times 3 ^ {k-2}}

{\ displaystyle \ varphi ^ {3} (3 ^ {k}) = \ varphi (2 \ cdot 3 ^ {k-2}) = \ varphi (2) \ cdot \ varphi (3 ^ {k-2}) = 1 \ times 2 \ times 3 ^ {k-3} = 2 \ times 3 ^ {k-3}}

Etc.

The proof works by means of complete induction .

Induction start : The statement is true for :

{\ displaystyle k = 1}

In fact, a perfectly totient number is because , and is.

{\ displaystyle n = 3 ^ {k} = 3 ^ {1} = 3}

{\ displaystyle \ varphi (3) = 2}

{\ displaystyle \ varphi (2) = 1}

{\ displaystyle 2 + 1 = 3}

The induction hypothesis is that a perfectly totiente number, so that:

{\ displaystyle n = 3 ^ {k-1}}

{\ displaystyle \ sum _ {i = 1} ^ {c + 1} \ varphi ^ {i} (3 ^ {k-1}) = \ varphi (3 ^ {k-1}) + \ varphi ^ {2 } (3 ^ {k-1}) + \ ldots + \ varphi ^ {c + 1} (3 ^ {k-1}) = 2 \ cdot 3 ^ {k-2} +2 \ cdot 3 ^ {k -3} + \ ldots +2 \ cdot 3 ^ {2} +2 \ cdot 3 ^ {1} +2 \ cdot 3 ^ {0} +1 = {\ color {red} 1 + 2 + 2 \ cdot 3 +2 \ cdot 9 + 2 \ cdot 27+ \ ldots +2 \ cdot 3 ^ {k-2} \; {\ stackrel {!} {=}} \; 3 ^ {k-1}}}

Now comes the induction conclusion : It remains to show that there is also a perfectly totient number.

{\ displaystyle n = 3 ^ {k}}

Since according to the induction hypothesis there is a perfectly totient number, the following must apply:

{\ displaystyle 3 ^ {k-1}}

{\ displaystyle {\ begin {array} {rcl} \ displaystyle \ sum _ {i = 1} ^ {c + 1} \ varphi ^ {i} (3 ^ {k}) & = & \ varphi (3 ^ { k}) + \ varphi ^ {2} (3 ^ {k}) + \ varphi ^ {3} (3 ^ {k}) + \ ldots + \ varphi ^ {c} (3 ^ {k}) + \ varphi ^ {c + 1} (3 ^ {k}) \\ & = & \ varphi ^ {c + 1} (3 ^ {k}) + \ varphi ^ {c} (3 ^ {k}) + \ ldots + \ varphi ^ {3} (3 ^ {k}) + \ varphi ^ {2} (3 ^ {k}) + \ varphi (3 ^ {k}) \\ & = & 1 + 2 \ cdot 3 ^ {0} +2 \ cdot 3 ^ {1} +2 \ cdot 3 ^ {2} + \ ldots +2 \ cdot 3 ^ {k-3} +2 \ cdot 3 ^ {k-2} +2 \ cdot 3 ^ {k-1} \\ & = & {\ color {red} 1 + 2 + 2 \ times 3 + 2 \ times 9 + 2 \ times 27+ \ ldots +2 \ times 3 ^ {k-2} } +2 \ cdot 3 ^ {k-1} \\ & = & {\ color {red} 3 ^ {k-1}} + 2 \ cdot 3 ^ {k-1} \ qquad {\ text {(induction assumption )}} \\ & = & 3 \ cdot 3 ^ {k-1} \\ & = & 3 ^ {k} \ end {array}}}

This gives the sum of the respective totients exactly , so is a perfectly totient number. What had to be proven .

{\ displaystyle 3 ^ {k}}

{\ displaystyle 3 ^ {k}}

{\ displaystyle \ Box}

Most of the known perfectly totient numbers are multiples of powers of , that is, of the form . The smallest perfectly total number that is not divisible by is . ${\ displaystyle 3}$ ${\ displaystyle n = x \ cdot 3 ^ {k}}$ ${\ displaystyle 3}$ ${\ displaystyle n = 4375}$
Be the -th perfectly total number. For the first 64 known perfectly totient numbers: ${\ displaystyle n_ {i}}$ ${\ displaystyle i}$

{\ displaystyle n_ {i} \ approx 1.56 ^ {i}}

The product of the first Fermat prime numbers is a perfectly totient number. ${\ displaystyle n}$

Examples:

At the moment only the five Fermat prime numbers and are known. If you multiply them together, you get the numbers and , which are actually all perfectly total numbers.

{\ displaystyle 3,5,17,257}

{\ displaystyle 65537}

{\ displaystyle 3,15,255,65535}

{\ displaystyle 4294967295}

Be with prime , . Then: ${\ displaystyle n: = 3p}$ ${\ displaystyle p \ in \ mathbb {P}}$ ${\ displaystyle p> 3}$

{\ displaystyle n}

is a perfectly totient number if and only if and is itself a perfectly totient number.

{\ displaystyle p = 4k + 1}

{\ displaystyle k}

This theorem was already proven in 1939 by LP Cacho.

Example:

The number is a perfectly total number. It's a prime number. You get the number that is actually a perfectly total number.

{\ displaystyle k = 9}

{\ displaystyle p = 4k + 1 = 4 \ cdot 9 + 1 = 37}

{\ displaystyle n = 3p = 3 \ cdot 37 = 111}

Be a prime number with natural . Then: ${\ displaystyle p: = 4 \ cdot 3 ^ {k} +1}$ ${\ displaystyle k> 0}$

{\ displaystyle n = 3p}

is a perfectly total number.

This theorem was proved by the mathematician T. Venkataraman in 1975.

The following list indicates the smallest for which numbers of the form are prime:

{\ displaystyle k}

{\ displaystyle p = 4 \ cdot 3 ^ {k} +1}

0, 1, 2, 3, 6, 14, 15, 39, 201, 249, 885, 1005, 1254, 1635, 3306, 3522, 9602, 19785, 72698, 233583, 328689, 537918, 887535, 980925, 1154598, 1499606, ... (sequence A005537 in OEIS )

Be with prime , . Then: ${\ displaystyle n: = 3p}$ ${\ displaystyle p \ in \ mathbb {P}}$ ${\ displaystyle p \ equiv 3 {\ pmod {4}}}$

{\ displaystyle n}

is not a perfectly total number.

This theorem was proven by the two mathematicians AL Mohan and D. Suryanarayana in 1982.

literature

AL Mohan, D. Suryanarayana: Perfect totient numbers . In: Krishnaswami Alladi (Ed.): Number Theory (= Lecture Notes in Mathematics . Volume 938 ). Springer, Berlin / Heidelberg 1982, ISBN 978-3-540-11568-7 , pp. 101-105 , doi : 10.1007 / BFb0097177 (English).
Jozsef Sándor, Borislav Crstici: Handbook of Number Theory II . Kluwer Academic Publishers, Dordrecht / Boston / London 2004, ISBN 1-4020-2546-7 , section “Perfect totient numbers and related results”, p. 240–242 (English, online [accessed March 28, 2020]).

Web links

T. Venkataraman: Perfect totient number. The Mathematics Student 43 , 1975, p. 178 , accessed March 25, 2020 .
Douglas E. Iannucci, Deng Moujie, Graeme L. Cohen: On Perfect Totient Numbers. (PDF). Journal of Integer Sequences 6 , Article 03.4.5, 2003, pp. 1–7 , accessed on March 25, 2020 .
Florian Luca: On the Distribution of Perfect Totients. (PDF). Journal of Integer Sequences 9 , Article 06.4.4, 2006, pp. 1–17 , accessed on March 25, 2020 .
Igor E. Shparlinski: On the Sum of Iterations of the Euler Function. Journal of Integer Sequences 9 , Article 06.1.6, 2006, pp. 1–5 , accessed on March 25, 2020 .
Paul Loomis, Michael Plytage & John Polhill: Summing Up the Euler φ Function. The College Mathematics Journal 39 (1), January 2008, pp. 34-42 , accessed March 25, 2020 .
perfect totient number . In: PlanetMath . (English)
Perfect totient numbers. Program codes for perfectly total numbers. Rosettacode.org, March 14, 2020, accessed March 25, 2020 .

Individual evidence

↑ ^a ^b Laureano Pérez-Cacho (1939). "Sobre la suma de indicadores de ordenes sucesivos". Revista Matematica Hispano-Americana. 5 (3): pp. 45-50.
↑ ^a ^b T. Venkataraman: Perfect totient number. The Mathematics Student 43 , 1975, p. 178 , accessed March 25, 2020 .
↑ AL Mohan, D. Suryanarayana: Perfect Totient Numbers. Springer, Berlin, Heidelberg, 1982, pp. 101-105 , accessed on March 25, 2020 .
↑ List of the first 64 perfectly totient numbers on OEIS A082897
↑ Robert Munafo: Sequence A082897: Perfect Totient Numbers. 2020, accessed March 25, 2020 .
↑ ^a ^b Comments on OEIS A082897
↑ AL Mohan, D. Suryanarayana: Perfect Totient Numbers. Remark 1. Springer, Berlin, Heidelberg, 1982, p. 101 , accessed on March 25, 2020 .
^ Douglas E. Iannucci, Deng Moujie, Graeme L. Cohen: On Perfect Totient Numbers. (PDF), information in front of the board on p. 2. Journal of Integer Sequences 6 , Article 03.4.5, 2003, pp. 1–7 , accessed on March 25, 2020 .
↑ AL Mohan, D. Suryanarayana: Perfect Totient Numbers. Theorem 1. Springer, Berlin, Heidelberg, 1982, p. 101 , accessed on March 25, 2020 .

[Cacho-1] Laureano Pérez-Cacho (1939). "Sobre la suma de indicadores de ordenes sucesivos". Revista Matematica Hispano-Americana. 5 (3): pp. 45-50.

[Venkataraman-2] T. Venkataraman: Perfect totient number. The Mathematics Student 43 , 1975, p. 178 , accessed March 25, 2020 .

[Mohan-3] AL Mohan, D. Suryanarayana: Perfect Totient Numbers. Springer, Berlin, Heidelberg, 1982, pp. 101-105 , accessed on March 25, 2020 .

[Zahlenliste-4] List of the first 64 perfectly totient numbers on OEIS A082897

[Munafo-5] Robert Munafo: Sequence A082897: Perfect Totient Numbers. 2020, accessed March 25, 2020 .

[OEIS082897-6] Comments on OEIS A082897

[Mohan3-7] AL Mohan, D. Suryanarayana: Perfect Totient Numbers. Remark 1. Springer, Berlin, Heidelberg, 1982, p. 101 , accessed on March 25, 2020 .

[Iannucci-8] Douglas E. Iannucci, Deng Moujie, Graeme L. Cohen: On Perfect Totient Numbers. (PDF), information in front of the board on p. 2. Journal of Integer Sequences 6 , Article 03.4.5, 2003, pp. 1–7 , accessed on March 25, 2020 .

[Mohan2-9] AL Mohan, D. Suryanarayana: Perfect Totient Numbers. Theorem 1. Springer, Berlin, Heidelberg, 1982, p. 101 , accessed on March 25, 2020 .