Totient function

Totient function is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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
•   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.

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

Perl 6

Works with: Rakudo version 2018.11

This is an incredibly inefficient way of finding prime numbers.

<lang perl6>my \𝜑 = 0, |(1..*).hyper(:8degree).map: -> $t { +(^$t).grep: * gcd $t == 1 };

printf "𝜑(%2d) = %3d %s\n", $_, 𝜑[$_], $_ - 𝜑[$_] - 1 ??  !! 'Prime' for 1 .. 25;

(100, 1000, 10000).map: -> $limit {

   say "\nCount of primes <= $limit: " ~ +(^$limit).grep: {$_ == 𝜑[$_] + 1}

}</lang>

Output:

𝜑( 1) =   1
𝜑( 2) =   1 Prime
𝜑( 3) =   2 Prime
𝜑( 4) =   2
𝜑( 5) =   4 Prime
𝜑( 6) =   2
𝜑( 7) =   6 Prime
𝜑( 8) =   4
𝜑( 9) =   6
𝜑(10) =   4
𝜑(11) =  10 Prime
𝜑(12) =   4
𝜑(13) =  12 Prime
𝜑(14) =   6
𝜑(15) =   8
𝜑(16) =   8
𝜑(17) =  16 Prime
𝜑(18) =   6
𝜑(19) =  18 Prime
𝜑(20) =   8
𝜑(21) =  12
𝜑(22) =  10
𝜑(23) =  22 Prime
𝜑(24) =   8
𝜑(25) =  20

Count of primes <= 100: 25

Count of primes <= 1000: 168

Count of primes <= 10000: 1229

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

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  25

output   when using the input of:     -100

 25  primes detected for numbers up to and including  100

output   when using the input of:     -1000

 168  primes detected for numbers up to and including  1000

output   when using the input of:     -10000

 1229  primes detected for numbers up to and including  10000