46 lines
2.1 KiB
Plaintext
46 lines
2.1 KiB
Plaintext
The '''totient''' function is also known as:
|
|
::* Euler's totient function
|
|
::* Euler's phi totient function
|
|
::* phi totient function
|
|
::* <big> Φ </big> function (uppercase Greek phi)
|
|
::* <big> φ </big> function (lowercase Greek phi)
|
|
|
|
|
|
|
|
;Definitions (as per number theory):
|
|
The totient function:
|
|
::* counts the integers up to a given positive integer <big>'''n'''</big> that are relatively prime to <big>'''n'''</big>
|
|
::* counts the integers <big>'''k'''</big> in the range <big>'''1 ≤ k ≤ n'''</big> for which the greatest common divisor <big>'''gcd(n,k)'''</big> is equal to <big>'''1'''</big>
|
|
::* counts numbers <big>'''≤ n'''</big> and prime to <big>'''n'''</big>
|
|
|
|
|
|
|
|
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<sup>st</sup> '''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.
|
|
|
|
|
|
;Related task:
|
|
::* [[Perfect totient numbers]]
|
|
|
|
|
|
;Also see:
|
|
::* [[wp:Euler's_totient_function|Wikipedia: Euler's totient function]].
|
|
::* [http://mathworld.wolfram.com/TotientFunction.html MathWorld: totient function].
|
|
::* [[oeis:/A000010|OEIS: Euler totient function phi(n)]].
|
|
<br/>
|
|
|