Factorions: Difference between revisions
→{{header|jq}}
(→{{header|Vlang}}: Rename "Vlang" in "V (Vlang)") |
|||
Line 776:
Base 12:
1 2
</pre>
=={{header|jq}}==
{{works with|jq}}
'''Also works with gojq, the Go implementation of jq, and with fq.'''
The main difficulty in computing the factorions of an arbitrary base
is obtaining a tight limit on the maximum value a factorion can
have in that base. The present entry accordingly does at least provide a function,
`sufficient`, for computing an upper bound with respect to a particular base, and uses it to compute
the factorions of all bases from 2 through 9.
However, the algorithm used by `sufficient` is too simplistic to be of much practical use for bases 10 or higher.
For base 10, the task description provides a value with a link to a justification. For bases 11 and 12, we use limits that are known to be sufficient, as per (*) [https://web.archive.org/web/20151220095834/https://en.wikipedia.org/wiki/Factorion].
<syntaxhighlight lang=jq>
# A stream of factorials
# [N|factorials][n] is n!
def factorials:
select(. > 0)
| 1,
foreach range(1; .) as $n(1; . * $n);
# The base-$b factorions less than or equal to $max
def factorions($b; $max):
($max // 1500000) as $max
| [$b|factorials] as $fact
| range(1; $max) as $i
| {sum: 0, j: $i}
| until( .j == 0 or .sum > $i;
( .j % $b) as $d
| .sum += $fact[$d]
| .j = ((.j/$b)|floor) )
| select(.sum == $i)
| $i ;
# input: base
# output: an upper bound for the factorions in that base
def sufficient:
. as $base
| def stream:
recurse(if . > 0 then ./$base|floor else empty end) | . % $base ;
[12|factorials] as $fact
| $fact[$base-1] as $f
| { digits: 1, value: $base}
| until ( (.value > ($f * .digits) );
.digits += 1
| .value *= $base ) ;
# Show the factorions for all based from 2 through 12:
(range(2;10)
| . as $base
| sufficient.value as $max
| {$base, factorions: ([factorions($base; $max)] | join(" "))}),
{base: 10, factorions: ([factorions(10; 1500000)] | join(" "))}, # limit per the task description
{base: 11, factorions: ([factorions(11; 50000)] | join(" "))}, # a limit known to be sufficient per (*)
{base: 12, factorions: ([factorions(12; 50000)] | join(" "))} # a limit known to be sufficient per (*)
</syntaxhighlight>
{{output}}
<pre>
{"base":2,"factorions":"1 2"}
{"base":3,"factorions":"1 2"}
{"base":4,"factorions":"1 2 7"}
{"base":5,"factorions":"1 2 49"}
{"base":6,"factorions":"1 2 25 26"}
{"base":7,"factorions":"1 2"}
{"base":8,"factorions":"1 2"}
{"base":9,"factorions":"1 2 41282"}
{"base":10,"factorions":"1 2 145 40585"}
{"base":11,"factorions":"1 2 26 48 40472"}
{"base":12,"factorions":"1 2"}
</pre>
| |||