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 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.
- 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).
Go
Results for the larger values of n are very slow to emerge. <lang go>package main
import "fmt"
func gcd(n, k int) int {
if n < k || k < 1 {
panic("Need n >= k and k >= 1")
}
s := 1
for n&1 == 0 && k&1 == 0 {
n >>= 1
k >>= 1
s <<= 1
}
t := n
if n&1 != 0 {
t = -k
}
for t != 0 {
for t&1 == 0 {
t >>= 1
}
if t > 0 {
n = t
} else {
k = -t
}
t = n - k
}
return n * s
}
func totient(n int) int {
tot := 0
for k := 1; k <= n; k++ {
if gcd(n, k) == 1 {
tot++
}
}
return tot
}
func main() {
fmt.Println(" n phi prime")
fmt.Println("---------------")
count := 0
for n := 1; n <= 25; n++ {
tot := totient(n)
isPrime := n-1 == tot
if isPrime {
count++
}
fmt.Printf("%2d %2d %t\n", n, tot, isPrime)
}
fmt.Println("\nNumber of primes up to 25 =", count)
for n := 26; n <= 100000; n++ {
tot := totient(n)
if tot == n-1 {
count++
}
if n == 100 || n == 1000 || n%10000 == 0 {
fmt.Printf("\nNumber of primes up to %-6d = %d\n", n, count)
}
}
}</lang>
- Output:
n phi prime --------------- 1 1 false 2 1 true 3 2 true 4 2 false 5 4 true 6 2 false 7 6 true 8 4 false 9 6 false 10 4 false 11 10 true 12 4 false 13 12 true 14 6 false 15 8 false 16 8 false 17 16 true 18 6 false 19 18 true 20 8 false 21 12 false 22 10 false 23 22 true 24 8 false 25 20 false Number of primes up to 25 = 9 Number of primes up to 100 = 25 Number of primes up to 1000 = 168 Number of primes up to 10000 = 1229 Number of primes up to 20000 = 2262 Number of primes up to 30000 = 3245 Number of primes up to 40000 = 4203 Number of primes up to 50000 = 5133 Number of primes up to 60000 = 6057 Number of primes up to 70000 = 6935 Number of primes up to 80000 = 7837 Number of primes up to 90000 = 8713 Number of primes up to 100000 = 9592
Perl 6
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
Python
<lang python>from math import gcd
def φ(n):
return sum(1 for k in range(1, n + 1) if gcd(n, k) == 1)
if __name__ == '__main__':
def is_prime(n):
return φ(n) == n - 1
for n in range(1, 26):
print(f" φ({n}) == {φ(n)}{', is prime' if is_prime(n) else }")
count = 0
for n in range(1, 10_000 + 1):
count += is_prime(n)
if n in {100, 1000, 10_000}:
print(f"Primes up to {n}: {count}")</lang>
- Output:
φ(1) == 1 φ(2) == 1, is prime φ(3) == 2, is prime φ(4) == 2 φ(5) == 4, is prime φ(6) == 2 φ(7) == 6, is prime φ(8) == 4 φ(9) == 6 φ(10) == 4 φ(11) == 10, is prime φ(12) == 4 φ(13) == 12, is prime φ(14) == 6 φ(15) == 8 φ(16) == 8 φ(17) == 16, is prime φ(18) == 6 φ(19) == 18, is prime φ(20) == 8 φ(21) == 12 φ(22) == 10 φ(23) == 22, is prime φ(24) == 8 φ(25) == 20 Primes up to 100: 25 Primes up to 1000: 168 Primes up to 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
zkl
<lang zkl>fcn totient(n){ [1..n].reduce('wrap(p,k){ p + (n.gcd(k)==1) }) } fcn isPrime(n){ totient(n)==(n - 1) }</lang> <lang zkl>foreach n in ([1..25]){
println("\u03c6(%2d) ==%3d %s"
.fmt(n,totient(n),isPrime(n) and "is prime" or ""));
}</lang>
- Output:
φ( 1) == 1 φ( 2) == 1 is prime φ( 3) == 2 is prime φ( 4) == 2 φ( 5) == 4 is prime φ( 6) == 2 φ( 7) == 6 is prime φ( 8) == 4 φ( 9) == 6 φ(10) == 4 φ(11) == 10 is prime φ(12) == 4 φ(13) == 12 is prime φ(14) == 6 φ(15) == 8 φ(16) == 8 φ(17) == 16 is prime φ(18) == 6 φ(19) == 18 is prime φ(20) == 8 φ(21) == 12 φ(22) == 10 φ(23) == 22 is prime φ(24) == 8 φ(25) == 20
<lang zkl>count:=0; foreach n in ([1..10_000]){ // yes, this is sloooow
count+=isPrime(n);
if(n==100 or n==1000 or n==10_000)
println("Primes <= %,6d : %,5d".fmt(n,count));
}</lang>
- Output:
Primes <= 100 : 25 Primes <= 1,000 : 168 Primes <= 10,000 : 1,229