Jordan-Pólya numbers: Difference between revisions
→{{header|jq}}
(Faster XPL0 example.) |
|||
Line 20:
* OEIS sequence [[oeis:A001013|A001013: Jordan-Pólya numbers]]
<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}}==
{{libheader|Wren-set}}
| |||