Totient function: Difference between revisions
(added a new (draft) task for the totient function; also added the REXX computer programming language entry.) |
(→{{header|REXX}}: fixed and ending TT HTML tag.) |
||
Line 68: | Line 68: | ||
end /*k*/ |
end /*k*/ |
||
return #</lang> |
return #</lang> |
||
{{out|output|text= when using the default input of: <tt> 25 </tt}} |
{{out|output|text= when using the default input of: <tt> 25 </tt>}} |
||
<pre> |
<pre> |
||
totient number for 1 ──► 1 |
totient number for 1 ──► 1 |
||
Line 98: | Line 98: | ||
9 primes detected for numbers up to and including 25 |
9 primes detected for numbers up to and including 25 |
||
</pre> |
</pre> |
||
{{out|output|text= when using the input of: <tt> -100 </tt}} |
{{out|output|text= when using the input of: <tt> -100 </tt>}} |
||
<pre> |
<pre> |
||
25 primes detected for numbers up to and including 100 |
25 primes detected for numbers up to and including 100 |
||
</pre> |
</pre> |
||
{{out|output|text= when using the input of: <tt> -1000 </tt}} |
{{out|output|text= when using the input of: <tt> -1000 </tt>}} |
||
<pre> |
<pre> |
||
168 primes detected for numbers up to and including 1000 |
168 primes detected for numbers up to and including 1000 |
||
</pre> |
</pre> |
||
{{out|output|text= when using the input of: <tt> -10000 </tt}} |
{{out|output|text= when using the input of: <tt> -10000 </tt>}} |
||
<pre> |
<pre> |
||
1229 primes detected for numbers up to and including 10000 |
1229 primes detected for numbers up to and including 10000 |
Revision as of 04:26, 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
- 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
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