Zumkeller numbers: Difference between revisions
→{{header|jq}}
(→{{header|Pascal}}: improved sieve for prime decompostion runtime for 1e9 down from 474 s to 170 s tested til 1e11) |
|||
Line 2,307:
1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377
</pre>
=={{header|jq}}==
{{Works with|jq|1.5}}
From a practical point of view, jq is not well-suited to these tasks,
e.g. using the program shown here, the first task is completed in about 1 second.
The main point of interest here, therefore, is the partitioning
function, or rather how a generic partitioning function that
generates a stream of partitions is easily transformed into a
specialized function that prunes irrelevant partitions efficiently.
<lang jq># The factors, sorted
def factors:
. as $num
| reduce range(1; 1 + sqrt|floor) as $i
([];
if ($num % $i) == 0 then
($num / $i) as $r
| if $i == $r then . + [$i] else . + [$i, $r] end
else .
end
| sort) ;
def sum(s): reduce s as $x (0; . + $x);
# sum of a slice, without any allocation
def sum($i; $j): . as $in | reduce range($i; $j) as $ix (0; . + $in[$ix]);
# If the input is a sorted array of distinct non-negative integers,
# then the output will be a stream of [$x,$y] arrays,
# where $x and $y are non-empty arrays that partition the
# input, and where ($x|add) == $sum.
# If [$x,$y] is emitted, then [$y,$x] will not also be emitted.
# The items in $x appear in the same order as in the input, and similarly
# for $y.
#
def distinct_partitions($sum):
# input: [$array, $n, $lim] where $n>0
# output: a stream of arrays, $a, each with $n distinct items from $array,
# preserving the order in $array, and such that
# add == $lim
def p:
. as [$in, $n, $lim]
| if $n==1 # this condition is very common so it saves time to check early on
then ($in | bsearch($lim)) as $ix
| if $ix < 0 then empty
else [$lim]
end
else ($in|length) as $length
| if $length <= $n then empty
elif $length==$n then $in | select(add == $lim)
elif ($in[-$n:]|add) < $lim then empty
else ($in[:$n]|add) as $rsum
| if $rsum > $lim then empty
elif $rsum == $lim then "amazing" | debug | $in[:$n]
else range(0; 1 + $length - $n) as $i
| [$in[$i]] + ([$in[$i+1:], $n-1, $lim - $in[$i]]|p)
end
end
end;
range(1; (1+length)/2) as $i
| ([., $i, $sum]|p) as $pi
| [ $pi, (. - $pi)]
| select( if (.[0]|length) == (.[1]|length) then (.[0] < .[1]) else true end) #1
;
def zumkellerPartitions:
factors
| add as $sum
| if $sum % 2 == 1 then empty
else distinct_partitions($sum / 2)
end;
def is_zumkeller:
first(factors
| add as $sum
| if $sum % 2 == 1 then empty
else distinct_partitions($sum / 2)
| select( (.[0]|add) == (.[1]|add)) // ("internal error: \(.)" | debug | empty) #2
end
| true)
// false;</lang><lang jq>## The tasks:
"First 4:", limit(4; range(2; infinite) | select(is_zumkeller)),
"",
"First 220:", limit(220; range(2; infinite) | select(is_zumkeller))
</lang>
{{out}}
<pre>
First 220:
6
12
20
24
28
...
984
First 40 odd:
945
1575
2205
2835
3465
...
19305</pre>
=={{header|Julia}}==
| |||