Legendre prime counting function: Difference between revisions
Content added Content deleted
Line 355: | Line 355: | ||
10^8 5761455 |
10^8 5761455 |
||
10^9 50847534 |
10^9 50847534 |
||
</pre> |
|||
=={{header|jq}}== |
|||
'''Adapted from [[#Wren|Wren]]''' |
|||
{{works with|jq}} |
|||
'''Works with gojq, the Go implementation of jq''' (*) |
|||
The following implementation freely uses the following conveniences of jq syntax: |
|||
* the jq expression {$x} is an abbreviation for {"x" : $x} |
|||
* the jq expression {x} is an abbreviation for {"x" : .x} |
|||
The key-value pairs can be similarly specified in JSON objects with multiple keys. |
|||
(*) gojq struggles to get beyond [5,9592] without using huge amounts of memory; |
|||
jq becomes excessively slow after [7,664579]. |
|||
'''Preliminaries''' |
|||
<lang jq># For the sake of the accuracy of integer arithmetic when using gojq: |
|||
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in); |
|||
# Input: $n, which is assumed to be positive integer, |
|||
# Output: an array of primes less than or equal to $n (e.g. 10|eratosthenes #=> [2,3,5,7] |
|||
def eratosthenes: |
|||
# erase(i) sets .[i*j] to false for integral j > 1 |
|||
def erase(i): |
|||
if .[i] then |
|||
reduce range(2; (1 + length) / i) as $j (.; .[i * $j] = false) |
|||
else . |
|||
end; |
|||
(. + 1) as $n |
|||
| (($n|sqrt) / 2) as $s |
|||
| [null, null, range(2; $n)] |
|||
| reduce (2, 1 + (2 * range(1; $s))) as $i (.; erase($i)) |
|||
| map(select(.)) ; |
|||
</lang> |
|||
'''Phi and the Legendre Counting Function''' |
|||
<lang jq>def legendre: |
|||
(sqrt | floor + 1 | eratosthenes) as $primes |
|||
# Input: {x, a} |
|||
# Output: {phi: phi(x,a), memo} where .memo might have been updated |
|||
| def phi: |
|||
. as {x: $x, a: $a, memo: $memo} |
|||
| if $a == 0 then {phi: $x, $memo} |
|||
else "\($x),\($a)" as $ix |
|||
| $memo[ $ix ] as $m |
|||
| if $m then {phi: $m, $memo} |
|||
else .a += -1 |
|||
| phi as {phi: $phi1, memo: $memo} |
|||
| (($x / $primes[$a - 1])|floor) as $x |
|||
| ({$x, a, $memo} | phi) as {phi: $phi2, memo: $memo} |
|||
| ($phi1 - $phi2) as $phi |
|||
| {$phi, $memo} |
|||
| .memo[$ix] = $phi |
|||
end |
|||
end; |
|||
def l: |
|||
. as $n |
|||
| if . < 2 then 0 |
|||
else ($n|sqrt|floor|l) as $a |
|||
| ({x: $n, $a, memo: {}} | phi).phi + $a - 1 |
|||
end; |
|||
l; |
|||
def task: |
|||
range(0;10) |
|||
| . as $i |
|||
| [., (10|power($i)|legendre)] |
|||
; |
|||
task</lang> |
|||
{{out}} |
|||
<pre> |
|||
[0,0] |
|||
[1,4] |
|||
[2,25] |
|||
[3,168] |
|||
[4,1229] |
|||
[5,9592] |
|||
[6,78498] |
|||
[7,664579] |
|||
<terminated> |
|||
</pre> |
</pre> |
||