Totient function: Difference between revisions
Content deleted Content added
Added Fōrmulæ solution |
|||
Line 1,457: | Line 1,457: | ||
The count of the primes up to 1,000,000 = 78498 |
The count of the primes up to 1,000,000 = 78498 |
||
The count of the primes up to 10,000,000 = 664579 |
The count of the primes up to 10,000,000 = 664579 |
||
</pre> |
|||
=={{header|jq}}== |
|||
{{works with|jq}} |
|||
<lang jq> |
|||
# jq optimizes the recursive call of _gcd in the following: |
|||
def gcd(a;b): |
|||
def _gcd: |
|||
if .[1] != 0 then [.[1], .[0] % .[1]] | _gcd else .[0] end; |
|||
[a,b] | _gcd ; |
|||
def count(s): reduce s as $x (0; .+1); |
|||
def totient: |
|||
. as $n |
|||
| count( range(0; .) | select( gcd($n; .) == 1) ); |
|||
# input: determines the maximum via range(0; .) |
|||
# and so may be `infinite` |
|||
def primes_via_totient: |
|||
range(0; .) | select(totient == . - 1); |
|||
</lang> |
|||
'''The tasks''' |
|||
<lang jq>def task: |
|||
def task1($n): |
|||
range(1;$n) |
|||
| totient as $totient |
|||
| {i: ., $totient, isprime: ($totient == ( . - 1 ))}; |
|||
task1(26); |
|||
def onepass: |
|||
reduce (10000 | primes_via_totient) as $p ({}; |
|||
if $p < 10000 |
|||
then .["10^4"] += 1 |
|||
| if $p < 1000 |
|||
then .["10^3"] += 1 |
|||
| if $p < 100 |
|||
then .["10^2"] += 1 |
|||
else . end else . end else . end) ; |
|||
task, "\nCounts of primes up to the given limits:", onepass</lang> |
|||
{{out}} |
|||
<pre> |
|||
{"i":1,"totient":1,"isprime":false} |
|||
{"i":2,"totient":1,"isprime":true} |
|||
{"i":3,"totient":2,"isprime":true} |
|||
{"i":4,"totient":2,"isprime":false} |
|||
{"i":5,"totient":4,"isprime":true} |
|||
{"i":6,"totient":2,"isprime":false} |
|||
{"i":7,"totient":6,"isprime":true} |
|||
{"i":8,"totient":4,"isprime":false} |
|||
{"i":9,"totient":6,"isprime":false} |
|||
{"i":10,"totient":4,"isprime":false} |
|||
{"i":11,"totient":10,"isprime":true} |
|||
{"i":12,"totient":4,"isprime":false} |
|||
{"i":13,"totient":12,"isprime":true} |
|||
{"i":14,"totient":6,"isprime":false} |
|||
{"i":15,"totient":8,"isprime":false} |
|||
{"i":16,"totient":8,"isprime":false} |
|||
{"i":17,"totient":16,"isprime":true} |
|||
{"i":18,"totient":6,"isprime":false} |
|||
{"i":19,"totient":18,"isprime":true} |
|||
{"i":20,"totient":8,"isprime":false} |
|||
{"i":21,"totient":12,"isprime":false} |
|||
{"i":22,"totient":10,"isprime":false} |
|||
{"i":23,"totient":22,"isprime":true} |
|||
{"i":24,"totient":8,"isprime":false} |
|||
{"i":25,"totient":20,"isprime":false} |
|||
Counts of primes up to the given limits: |
|||
{"10^4":1229,"10^3":168,"10^2":25} |
|||
</pre> |
</pre> |
||