The   totient   function is also known as:

   Euler's totient function
   Euler's phi totient function
   phi totient function
    Φ    function   (uppercase Greek phi)
    φ     function   (lowercase Greek phi)


Definitions   (as per number theory)

The totient function:

   counts the integers up to a given positive integer   n   that are relatively prime to   n
   counts the integers   k   in the range   1 ≤ k ≤ n   for which the greatest common divisor   gcd(n,k)   is equal to   1
   counts numbers   ≤ n   and   prime to   n


If the totient number   (for N)   is one less than   N,   then   N   is prime.



Task

Create a   totient   function and:

   Find and display   (1 per line)   for the 1st   25   integers:
   the integer   (the index)
   the totient number for that integer
   indicate if that integer is prime
   Find and display the   count   of the primes up to          100
   Find and display the   count   of the primes up to       1,000
   Find and display the   count   of the primes up to     10,000
   Find and display the   count   of the primes up to   100,000     (optional)
Show all output here.



Related task

   Perfect totient numbers


Also see

   Wikipedia: Euler's totient function.
   MathWorld: totient function.
   OEIS: Euler totient function phi(n).


 
$lines
 
rem - return p mod q
function mod(p, q = integer) = integer
end = p - q * (p / q)
 
rem - return greatest common divisor of x and y
function gcd(x, y = integer) = integer
   var r, temp = integer
   if x < y then
      begin
         temp = x
         x = y
         y = temp
      end
   r = mod(x, y)
   while r <> 0 do
      begin
         x = y
         y = r
         r = mod(x, y)
      end
end = y
 
rem - return phi (also called totient) of n
function phi(n = integer) = integer
   var i, count = integer
   count = 1
   for i = 2 to n
      if gcd(n, i) = 1 then count = count + 1
   next i
end = count
 
rem - exercise the function
var n, totient, count = integer
print "  n    Phi(n)   Prime?"
for n = 1 to 25
   totient = phi(n)
   print using "####  ####     ";n, totient;
   if totient + 1 = n then
      print "yes"
   else
      print "no"
next n
 
rem - and further test it by counting primes
print
count = 0
for n = 1 to 1000
   if phi(n) = n - 1 then count = count + 1
   if n = 100 then
      print "Primes up to 100  = ";count
   else if n = 1000 then
      print "Primes up to 1000 = ";count
next n
 
end
 