Jordan-Pólya numbers: Difference between revisions
Content added Content deleted
(Faster XPL0 example.) |
|||
Line 20: | Line 20: | ||
* OEIS sequence [[oeis:A001013|A001013: Jordan-Pólya numbers]] |
* OEIS sequence [[oeis:A001013|A001013: Jordan-Pólya numbers]] |
||
<br> |
<br> |
||
=={{header|jq}}== |
|||
{{works with|jq}} |
|||
'''Also works with gojq, the Go implementation of jq''' |
|||
'''Adapted from [[#Wren|Wren]]''' |
|||
<syntaxhighlight lang="jq"> |
|||
### Generic functions |
|||
# For gojq |
|||
def _nwise($n): |
|||
def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end; |
|||
n; |
|||
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" ); |
|||
# Input: an array |
|||
# Output: a stream of pairs [$x, $frequency] |
|||
# A two-level dictionary is used: .[type][tostring] |
|||
def frequencies: |
|||
if length == 0 then empty |
|||
else . as $in |
|||
| reduce range(0; length) as $i ({}; |
|||
$in[$i] as $x |
|||
| .[$x|type][$x|tostring] as $pair |
|||
| if $pair |
|||
then .[$x|type][$x|tostring] |= (.[1] += 1) |
|||
else .[$x|type][$x|tostring] = [$x, 1] |
|||
end ) |
|||
| .[][] |
|||
end ; |
|||
# Output: the items in the stream up to but excluding the first for which cond is truthy |
|||
def emit_until(cond; stream): label $out | stream | if cond then break $out else . end; |
|||
### Jordan-Pólya numbers |
|||
# input: {factorial} |
|||
# output: an array |
|||
def JordanPolya($lim; $mx): |
|||
if $lim < 2 then [1] |
|||
else . + {v: [1], t: 1, k: 2} |
|||
| .mx = ($mx // $lim) |
|||
| until(.k > .mx or .t > $lim; |
|||
.t *= .k |
|||
| if .t <= $lim |
|||
then reduce JordanPolya(($lim/.t)|floor; .t)[] as $rest (.; |
|||
.v += [.t * $rest] ) |
|||
| .k += 1 |
|||
else . |
|||
end) |
|||
| .v |
|||
| unique |
|||
end; |
|||
# Cache m! for m <= $n |
|||
def cacheFactorials($n): |
|||
{fact: 1, factorial: [1]} |
|||
| reduce range(1; $n + 1) as $i (.; |
|||
.fact *= $i |
|||
| .factorial[$i] = .fact ); |
|||
# input: {factorial} |
|||
def Decompose($n; $start): |
|||
if $start and $start < 2 then [] |
|||
else |
|||
{ factorial, |
|||
start: ($start // 18), |
|||
m: $n, |
|||
f: [] } |
|||
| label $out |
|||
| foreach range(.start; 1; -1) as $i (.; |
|||
.i = $i |
|||
| .emit = null |
|||
| until (.emit or (.m % .factorial[$i] != 0); |
|||
.f += [$i] |
|||
| .m = (.m / .factorial[$i]) |
|||
| if .m == 1 then .emit = .f else . end) |
|||
| if .emit then ., break $out else . end) |
|||
| if .emit then .emit |
|||
elif .i == 2 then Decompose($n; .start-1) |
|||
else empty |
|||
end |
|||
end; |
|||
# Input: {factorial} |
|||
# $v should be an array of J-P numbers |
|||
def synopsis($v): |
|||
(100, 800, 1800, 2800, 3800) as $i |
|||
| if $v[$i-1] == null |
|||
then "\nThe \($i)th Jordan-Pólya number was not found." | error |
|||
else "\nThe \($i)th Jordan-Pólya number is \($v[$i-1] )", |
|||
([Decompose($v[$i-1]; null) | frequencies] |
|||
| map( if (.[1] == 1) then "\(.[0])!" else "(\(.[0])!)^\(.[1])" end) |
|||
| " i.e. " + join(" * ") ) |
|||
end ; |
|||
def task: |
|||
cacheFactorials(18) |
|||
| JordanPolya(pow(2;53)-1; null) as $v |
|||
| "\($v|length) Jordan–Pólya numbers have been found. The first 50 are:", |
|||
( $v[:50] | tprint(10; 4)), |
|||
"\nThe largest Jordan–Pólya number before 100 million: " + |
|||
"\(if $v[-1] > 1e8 then last(emit_until(. >= 1e8; $v[])) else "not found" end)", |
|||
synopsis($v) ; |
|||
task |
|||
</syntaxhighlight> |
|||
{{output}} |
|||
gojq and jq produce the same results except that gojq produces the factorizations in a different order. |
|||
The output shown here corresponds to the invocation: jq -nr -f jordan-polya-numbers.jq |
|||
<pre> |
|||
3887 Jordan–Pólya numbers have been found. The first 50 are: |
|||
1 2 4 6 8 12 16 24 32 36 |
|||
48 64 72 96 120 128 144 192 216 240 |
|||
256 288 384 432 480 512 576 720 768 864 |
|||
960 1024 1152 1296 1440 1536 1728 1920 2048 2304 |
|||
2592 2880 3072 3456 3840 4096 4320 4608 5040 5184 |
|||
The largest Jordan–Pólya number before 100 million: 99532800 |
|||
The 100th Jordan-Pólya number is 92160 |
|||
i.e. 6! * (2!)^7 |
|||
The 800th Jordan-Pólya number is 18345885696 |
|||
i.e. (4!)^7 * (2!)^2 |
|||
The 1800th Jordan-Pólya number is 9784472371200 |
|||
i.e. (6!)^2 * (4!)^2 * (2!)^15 |
|||
The 2800th Jordan-Pólya number is 439378587648000 |
|||
i.e. 14! * 7! |
|||
The 3800th Jordan-Pólya number is 7213895789838336 |
|||
i.e. (4!)^8 * (2!)^16 |
|||
</pre> |
|||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{libheader|Wren-set}} |
{{libheader|Wren-set}} |