Totient function: Difference between revisions
Thundergnat (talk | contribs) (→{{header|Perl 6}}: Add a Perl 6 example) |
(clarify what is wanted (indicate if an integer is prime).) |
||
Line 27: | Line 27: | ||
::::* the integer (the index) |
::::* the integer (the index) |
||
::::* the totient number for that integer |
::::* the totient number for that integer |
||
::::* if |
::::* indicate if an integer is prime |
||
::* Find and display the ''count'' of the primes up to 100 |
::* 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 1,000 |
Revision as of 15:46, 5 December 2018
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 an 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
This is an incredibly inefficient way of finding prime numbers.
<lang perl6>my \𝜑 = (1..*).hyper(:8degree).map: -> $t { +(^$t).grep: * gcd $t == 1 };
printf "𝜑(%2d) = %d\n", $_, 𝜑[$_ - 1] for 1 .. 25;
(100, 1000, 10000).map: -> $limit {
say "\nCount of primes <= $limit: ", +(1..$limit).grep: {$_ == 𝜑[$_ - 1] + 1}
}</lang>
- Output:
𝜑( 1) = 1 𝜑( 2) = 1 𝜑( 3) = 2 𝜑( 4) = 2 𝜑( 5) = 4 𝜑( 6) = 2 𝜑( 7) = 6 𝜑( 8) = 4 𝜑( 9) = 6 𝜑(10) = 4 𝜑(11) = 10 𝜑(12) = 4 𝜑(13) = 12 𝜑(14) = 6 𝜑(15) = 8 𝜑(16) = 8 𝜑(17) = 16 𝜑(18) = 6 𝜑(19) = 18 𝜑(20) = 8 𝜑(21) = 12 𝜑(22) = 10 𝜑(23) = 22 𝜑(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