Totient function

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 1^st 25 integers:

the integer (the index)
the totient number for that integer
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.

Also see

the Wikipedia entry for Euler's totient function.
the MathWorld entry for totient function.
the OEIS entry for Euler totient function phi(n).

REXX

<lang rexx>/*REXX program calculates the totient numbers for a range of numbers, and count primes. */ parse arg N . /*obtain optional argument from the CL.*/ if N== | N=="," then N= 25 /*Not specified? Then use the default.*/ tell= N>0 /*N positive>? Then display them all. */ N= abs(N) /*use the absolute value of N for loop.*/ w= length(N) /*W: is used to aligning the output. */ primes= 0 /*the number of primes found (so far).*/

                                                /*if N was negative, only count primes.*/
   do j=1  for  N;     tn= phi(j)               /*obtain totient number for a number.  */
   prime= word('(prime)', 1 + (tn\==j-1 ) )     /*determine if  J  is a prime number.  */
   if prime\==  then primes= primes+1         /*if a prime, then bump the prime count*/
   if tell  then say 'totient number for '  right(j, w)  " ──► "  right(tn, w) ' ' prime
   end

say say right(primes, w) ' primes detected for numbers up to and including ' N exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ gcd: parse arg x,y; do until y==0; parse value x//y y with y x

                               end   /*until*/
    return x

/*──────────────────────────────────────────────────────────────────────────────────────*/ phi: procedure; parse arg z; #= z==1; do k=1 for z-1

                                                    #= # +  (gcd(k, z)==1)
                                                    end   /*k*/
    return #</lang>

output when using the default input of: 25 </tt

totient number for 1 ──► 1 totient number for 2 ──► 1 (prime) totient number for 3 ──► 2 (prime) totient number for 4 ──► 2 totient number for 5 ──► 4 (prime) totient number for 6 ──► 2 totient number for 7 ──► 6 (prime) totient number for 8 ──► 4 totient number for 9 ──► 6 totient number for 10 ──► 4 totient number for 11 ──► 10 (prime) totient number for 12 ──► 4 totient number for 13 ──► 12 (prime) totient number for 14 ──► 6 totient number for 15 ──► 8 totient number for 16 ──► 8 totient number for 17 ──► 16 (prime) totient number for 18 ──► 6 totient number for 19 ──► 18 (prime) totient number for 20 ──► 8 totient number for 21 ──► 12 totient number for 22 ──► 10 totient number for 23 ──► 22 (prime) totient number for 24 ──► 8 totient number for 25 ──► 20 9 primes detected for numbers up to and including 25output when using the input of: -100 </tt25 primes detected for numbers up to and including 100output when using the input of: -1000 </tt168 primes detected for numbers up to and including 1000output when using the input of: -10000 </tt1229 primes detected for numbers up to and including 10000