Skip to main content.

Solution to puzzle 152: Totient valence

Skip restatement of puzzle.Euler's totient function phi(n) is defined as the number of positive integers not exceeding n that are relatively prime to n, where 1 is counted as being relatively prime to all numbers.  So, for example, phi(20) = 8 because the eight integers 1, 3, 7, 9, 11, 13, 17, and 19 are relatively prime to 20.

Euler's totient valence function v(n) is defined as the number of positive integers k such that phi(k) = n.  For instance, v(8) = 5 because only the five integers k = 15, 16, 20, 24, and 30 are such that phi(k) = 8.  The table below shows values of v(n) for n less than or equal to 16.  (For n not in the table, v(n) = 0.)

nv(n)k such that phi(k) = n
121, 2
233, 4, 6
445, 8, 10, 12
647, 9, 14, 18
8515, 16, 20, 24, 30
10211, 22
12613, 21, 26, 28, 36, 42
16617, 32, 34, 40, 48, 60

Evaluate v(21000).


A solution will be posted as soon as possible.

Source: Original

Back to top