Numbers with prime digits whose sum is 13: Difference between revisions

Content added Content deleted
(→‎{{header|jq}}: add analytic solution)
Line 1,018: Line 1,018:
'''Works with gojq, the Go implementation of jq'''
'''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.
Two solutions are presented. Both are based on the

observation that the only digits which are prime are [2, 3, 5, 7]
All three solutions are based on the observation that the only decimal digits which are prime are [2, 3, 5, 7].
so the numbers of interest cannot have more than 6 digits.

To save space, both only present the count of the number of solutions; this is done using the stream counter:
To save space, the first two solutions only present the count of the number of solutions; this is done using the stream counter:


def count(s): reduce s as $_ (0; .+1);
def count(s): reduce s as $_ (0; .+1);


'''Simple Generate-and-Test Solution'''
====Simple Generate-and-Test Solution====
<lang jq># Output: a stream
<lang jq># Output: a stream
def simple:
def simple:
Line 1,035: Line 1,036:


count(simple)</lang>
count(simple)</lang>
{{out}}
'''A Faster Solution'''
<pre>
43
</pre>
====A Faster Solution====
<lang jq>def faster:
<lang jq>def faster:
def digits: [2, 3, 5, 7];
def digits: [2, 3, 5, 7];
Line 1,053: Line 1,058:
</lang>
</lang>
{{out}}
{{out}}
In both cases:
<pre>
<pre>
43
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>
</pre>