Blum integer: Difference between revisions
Content added Content deleted
(→{{header|J}}: stretch) |
|||
Line 352: | Line 352: | ||
9 24.9847 |
9 24.9847 |
||
</syntaxhighlight> |
</syntaxhighlight> |
||
=={{header|jq}}== |
|||
'''Adapted from [[#Wren|Wren]]''' |
|||
{{Works with|jq}} |
|||
<syntaxhighlight lang=jq> |
|||
### Generic utilities |
|||
def lpad($len): tostring | ($len - length) as $l | (" " * $l) + .; |
|||
# tabular print |
|||
def tprint(columns; wide): |
|||
reduce _nwise(columns) as $row (""; |
|||
. + ($row|map(lpad(wide)) | join(" ")) + "\n" ); |
|||
### Primes |
|||
def is_prime: |
|||
. as $n |
|||
| if ($n < 2) then false |
|||
elif ($n % 2 == 0) then $n == 2 |
|||
elif ($n % 3 == 0) then $n == 3 |
|||
elif ($n % 5 == 0) then $n == 5 |
|||
elif ($n % 7 == 0) then $n == 7 |
|||
elif ($n % 11 == 0) then $n == 11 |
|||
elif ($n % 13 == 0) then $n == 13 |
|||
elif ($n % 17 == 0) then $n == 17 |
|||
elif ($n % 19 == 0) then $n == 19 |
|||
else sqrt as $s |
|||
| 23 |
|||
| until( . > $s or ($n % . == 0); . + 2) |
|||
| . > $s |
|||
end; |
|||
def primes: 2, (range(3;infinite;2) | select(is_prime)); |
|||
# input: the number to be tested |
|||
def isprime($smalls): |
|||
if . < 2 then false |
|||
else sqrt as $s |
|||
| (first( $smalls[] as $p |
|||
| if . == $p then 1 |
|||
elif . % $p == 0 then 0 |
|||
elif $p > $s then 1 |
|||
else empty |
|||
end) // null) as $result |
|||
| if $result then $result == 1 |
|||
else ($smalls[-1] + 2) |
|||
| until( . > $s or ($n % . == 0); . + 2) |
|||
| . > $s |
|||
end |
|||
end; |
|||
# Assumes n is odd. |
|||
def firstPrimeFactor: |
|||
if (. == 1) then 1 |
|||
elif (. % 3 == 0) then 3 |
|||
elif (. % 5 == 0) then 5 |
|||
else . as $n |
|||
| [4, 2, 4, 2, 4, 6, 2, 6] as $inc |
|||
| { k: 7, |
|||
i: 0 } |
|||
| ($n | sqrt) as $s |
|||
| until (.k > $s or .done; |
|||
if $n % .k == 0 |
|||
then .done = true |
|||
else .k += $inc[.i] |
|||
| .i = (.i + 1) % 8 |
|||
end ) |
|||
| if .done then .k else $n end |
|||
end ; |
|||
### Blum integers |
|||
# Number of small primes to pre-compute |
|||
def task($numberOfSmallPrimes): |
|||
[limit($numberOfSmallPrimes; primes)] as $smalls |
|||
| { blum: [], |
|||
bc:0, |
|||
counts: { "1": 0, "3": 0, "7": 0, "9": 0 }, |
|||
i: 1 } |
|||
| label $out |
|||
| foreach range(0; infinite) as $_ (.; |
|||
(.i|firstPrimeFactor) as $p |
|||
| .j = null |
|||
| if ($p % 4 == 3) |
|||
then (.i / $p) as $q |
|||
| if $q != $p and ($q % 4 == 3) and ($q | isprime($smalls)) |
|||
then if (.bc < 50) then .blum[.bc] = .i else . end |
|||
| .counts[(.i % 10) | tostring] += 1 |
|||
| .bc += 1 |
|||
| .j = .i |
|||
else . |
|||
end |
|||
else . |
|||
end |
|||
| .i |= if (. % 5 == 3) then . + 4 else . + 2 end; |
|||
select(.j) |
|||
| if (.bc == 50) |
|||
then "First 50 Blum integers:", |
|||
(.blum | tprint(10; 3) ) |
|||
elif .bc == 26828 or .bc % 1e5 == 0 |
|||
then "The \(.bc) Blum integer is: \(.j)", |
|||
if .bc == 400000 |
|||
then "\n% distribution of the first 400,000 Blum integers:", |
|||
((.counts|keys_unsorted[]) as $k |
|||
| " \( .counts[$k] / 4000 )% end in \($k)"), |
|||
break $out |
|||
else empty |
|||
end |
|||
else empty |
|||
end); |
|||
task(10000) |
|||
</syntaxhighlight> |
|||
{{output}} |
|||
<pre> |
|||
First 50 Blum integers: |
|||
21 33 57 69 77 93 129 133 141 161 |
|||
177 201 209 213 217 237 249 253 301 309 |
|||
321 329 341 381 393 413 417 437 453 469 |
|||
473 489 497 501 517 537 553 573 581 589 |
|||
597 633 649 669 681 713 717 721 737 749 |
|||
The 26828 Blum integer is: 524273 |
|||
The 100000 Blum integer is: 2075217 |
|||
The 200000 Blum integer is: 4275533 |
|||
The 300000 Blum integer is: 6521629 |
|||
The 400000 Blum integer is: 8802377 |
|||
% distribution of the first 400,000 Blum integers: |
|||
25.00125% end in 1 |
|||
25.01675% end in 3 |
|||
24.99725% end in 7 |
|||
24.98475% end in 9 |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |