Numbers with prime digits whose sum is 13: Difference between revisions
Numbers with prime digits whose sum is 13 (view source)
Revision as of 06:48, 24 January 2022
, 2 years ago→{{header|jq}}: add analytic solution
m (→{{header|jq}}: typo) |
(→{{header|jq}}: add analytic solution) |
||
Line 1,018:
'''Works with gojq, the Go implementation of jq'''
The first two solutions presented in this section focus on the specific task posed in the title of this page, and the third is a fast analytic solution for determining the count of distinct numbers with prime digits whose sum is any given number. This third solution requires gojq for accuracy if the target sum is relatively large.
All three solutions are based on the observation that the only decimal digits which are prime are [2, 3, 5, 7].
To save space,
def count(s): reduce s as $_ (0; .+1);
<lang jq># Output: a stream
def simple:
Line 1,035 ⟶ 1,036:
count(simple)</lang>
{{out}}
'''A Faster Solution'''▼
<pre>
43
</pre>
<lang jq>def faster:
def digits: [2, 3, 5, 7];
Line 1,053 ⟶ 1,058:
</lang>
{{out}}
<pre>
43
</pre>
====Fast Computation of the Count of Numbers====
As indicated above, this third solution is analytical (combinatoric),
and requires gojq for accuracy for relatively large target sums.
<lang jq># Input should be a sorted array of distinct positive integers
# Output is a stream of distinct arrays, each of which is sorted, and each sum of which is $sum
def sorted_combinations($sum):
if $sum <= 0 or length == 0 or $sum < .[0] then empty
else range(0; length ) as $i
| .[$i] as $x
| (($sum / $x) | floor) as $maxn
| range(1; 1 + $maxn) as $n
| ([range(0; $n) | $x]) as $prefix
| ($prefix | add // 0 ) as $psum
| if $psum == $sum then $prefix
else $prefix + (.[$i+1 :] | sorted_combinations($sum - $psum) )
end
end;
def factorial: reduce range(2;.+1) as $i (1; . * $i);
def product_of_factorials:
reduce .[] as $n (1; . * ($n|factorial));
# count the number of distinct permutations
def count_distinct_permutations:
def histogram:
reduce .[] as $i ([]; .[$i] += 1);
(length|factorial) / (histogram|product_of_factorials);
def number_of_interesting_numbers($total):
def digits: [2, 3, 5, 7];
reduce (digits | sorted_combinations($total)) as $pattern (0;
. + ($pattern|count_distinct_permutations));
number_of_interesting_numbers(13),
number_of_interesting_numbers(199)</lang>
{{out}}
<pre>
43
349321957098598244959032342621956
</pre>
| |||