Numbers with prime digits whose sum is 13: Difference between revisions
(Added Easylang) |
|||
(40 intermediate revisions by 18 users not shown) | |||
Line 1: | Line 1: | ||
{{draft task}} |
{{draft task|Prime Numbers}} |
||
Find all the |
Find all the positive integers whose decimal digits are all primes and sum to '''13'''. |
||
<br><br> |
|||
=={{header|11l}}== |
|||
{{trans|C}} |
|||
<syntaxhighlight lang="11l">F primeDigitsSum13(=n) |
|||
V sum = 0 |
|||
L n > 0 |
|||
V r = n % 10 |
|||
I r !C (2, 3, 5, 7) |
|||
R 0B |
|||
n I/= 10 |
|||
sum += r |
|||
R sum == 13 |
|||
V c = 0 |
|||
L(i) 1..999999 |
|||
I primeDigitsSum13(i) |
|||
print(‘#6’.format(i), end' ‘ ’) |
|||
I ++c == 11 |
|||
c = 0 |
|||
print() |
|||
print()</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
337 355 373 535 553 733 2227 2272 2335 2353 2533 |
|||
2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 |
|||
22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 |
|||
33223 33232 33322 52222 222223 222232 222322 223222 232222 322222 |
|||
</pre> |
|||
=={{header|Action!}}== |
|||
<syntaxhighlight lang="action!">DEFINE PRIMECOUNT="4" |
|||
BYTE ARRAY primedigits(PRIMECOUNT)=[2 3 5 7] |
|||
PROC PrintNum(BYTE ARRAY code BYTE count) |
|||
BYTE i,c |
|||
FOR i=0 TO count-1 |
|||
DO |
|||
c=code(i) |
|||
Put(primedigits(c)+'0) |
|||
OD |
|||
RETURN |
|||
BYTE FUNC Sum(BYTE ARRAY code BYTE count) |
|||
BYTE i,res,c |
|||
res=0 |
|||
FOR i=0 TO count-1 |
|||
DO |
|||
c=code(i) |
|||
res==+primedigits(c) |
|||
OD |
|||
RETURN (res) |
|||
PROC Init(BYTE ARRAY code BYTE count) |
|||
Zero(code,count) |
|||
RETURN |
|||
BYTE FUNC Next(BYTE ARRAY code BYTE count) |
|||
INT pos,c |
|||
pos=count-1 |
|||
DO |
|||
c=code(pos)+1 |
|||
IF c<PRIMECOUNT THEN |
|||
code(pos)=c |
|||
RETURN (1) |
|||
FI |
|||
code(pos)=0 |
|||
pos==-1 |
|||
IF pos<0 THEN |
|||
RETURN (0) |
|||
FI |
|||
OD |
|||
RETURN (0) |
|||
PROC Main() |
|||
DEFINE MAXDIG="6" |
|||
BYTE ARRAY digits(MAXDIG) |
|||
BYTE count,pos |
|||
count=1 pos=0 |
|||
Init(count) |
|||
DO |
|||
IF Sum(digits,count)=13 THEN |
|||
IF pos+count>=38 THEN |
|||
pos=0 PutE() |
|||
FI |
|||
PrintNum(digits,count) Put(32) |
|||
pos==+count+1 |
|||
FI |
|||
IF Next(digits,count)=0 THEN |
|||
count==+1 |
|||
IF count>MAXDIG THEN |
|||
EXIT |
|||
FI |
|||
Init(count) |
|||
FI |
|||
OD |
|||
RETURN</syntaxhighlight> |
|||
{{out}} |
|||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Numbers_with_prime_digits_whose_sum_is_13.png Screenshot from Atari 8-bit computer] |
|||
<pre> |
|||
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 |
|||
22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 |
|||
222322 223222 232222 322222 |
|||
</pre> |
|||
=={{header|ALGOL 68}}== |
|||
Based on the Algol W sample. |
|||
<syntaxhighlight lang="algol68">BEGIN |
|||
# find numbers whose digits are prime and whose digit sum is 13 # |
|||
# as noted by the Wren sample, the digits can only be 2, 3, 5, 7 # |
|||
# and there can only be 3, 4, 5 or 6 digits # |
|||
[]INT possible digits = []INT( 0, 2, 3, 5, 7 )[ AT 0 ]; |
|||
INT number count := 0; |
|||
INT zero = ABS "0"; # integer value of the character "0" # |
|||
print( ( newline ) ); |
|||
FOR d1 index FROM 0 TO UPB possible digits DO |
|||
INT d1 = possible digits[ d1 index ]; |
|||
CHAR c1 = IF d1 /= 0 THEN REPR ( d1 + zero ) ELSE " " FI; |
|||
FOR d2 index FROM 0 TO UPB possible digits DO |
|||
INT d2 = possible digits[ d2 index ]; |
|||
IF d2 /= 0 OR d1 = 0 THEN |
|||
CHAR c2 = IF ( d1 + d2 ) /= 0 THEN REPR ( d2 + zero ) ELSE " " FI; |
|||
FOR d3 index FROM 0 TO UPB possible digits DO |
|||
INT d3 = possible digits[ d3 index ]; |
|||
IF d3 /= 0 OR ( d1 + d2 ) = 0 THEN |
|||
CHAR c3 = IF ( d1 + d2 + d3 ) /= 0 THEN REPR ( d3 + zero ) ELSE " " FI; |
|||
FOR d4 index FROM 1 TO UPB possible digits DO |
|||
INT d4 = possible digits[ d4 index ]; |
|||
CHAR c4 = REPR ( d4 + zero ); |
|||
FOR d5 index FROM 1 TO UPB possible digits DO |
|||
INT d5 = possible digits[ d5 index ]; |
|||
CHAR c5 = REPR ( d5 + zero ); |
|||
FOR d6 index FROM 1 TO UPB possible digits DO |
|||
INT d6 = possible digits[ d6 index ]; |
|||
IF ( d1 + d2 + d3 + d4 + d5 + d6 ) = 13 THEN |
|||
# found a number whose prime digits sum to 13 # |
|||
CHAR c6 = REPR ( d6 + zero ); |
|||
print( ( " ", c1, c2, c3, c4, c5, c6 ) ); |
|||
number count := number count + 1; |
|||
IF ( number count +:= 1 ) MOD 12 = 0 THEN print( ( newline ) ) FI |
|||
FI |
|||
OD # d6 # |
|||
OD # d5 # |
|||
OD # d4 # |
|||
FI |
|||
OD # d3 # |
|||
FI |
|||
OD # d2 # |
|||
OD # d1 # |
|||
END</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 |
|||
3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 |
|||
22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 |
|||
52222 222223 222232 222322 223222 232222 322222 |
|||
</pre> |
|||
<br> |
|||
=={{header|ALGOL W}}== |
=={{header|ALGOL W}}== |
||
Uses the observations about the digits and numbers in the Wren solution to generate the sequence. |
Uses the observations about the digits and numbers in the Wren solution to generate the sequence. |
||
< |
<syntaxhighlight lang="algolw">begin |
||
% find numbers whose digits are prime and whose digit sum is 13 % |
% find numbers whose digits are prime and whose digit sum is 13 % |
||
% as noted by the Wren sample, the digits can only be 2, 3, 5, 7 % |
% as noted by the Wren sample, the digits can only be 2, 3, 5, 7 % |
||
Line 39: | Line 200: | ||
end for_d2 |
end for_d2 |
||
end for_d1 |
end for_d1 |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 47: | Line 208: | ||
52222 222223 222232 222322 223222 232222 322222 |
52222 222223 222232 222322 223222 232222 322222 |
||
</pre> |
</pre> |
||
=={{header|Arturo}}== |
|||
<syntaxhighlight lang="rebol">pDigits: [2 3 5 7] |
|||
lst: map pDigits 'd -> @[d] |
|||
result: new [] |
|||
while [0 <> size lst][ |
|||
nextList: new [] |
|||
loop lst 'digitSeq [ |
|||
currSum: sum digitSeq |
|||
loop pDigits 'n [ |
|||
newSum: currSum + n |
|||
newDigitSeq: digitSeq ++ n |
|||
case [newSum] |
|||
when? [<13] -> 'nextList ++ @[newDigitSeq] |
|||
when? [=13] -> 'result ++ @[to :integer join to [:string] newDigitSeq] |
|||
else -> break |
|||
] |
|||
] |
|||
lst: new nextList |
|||
] |
|||
loop split.every: 10 result 'a -> |
|||
print map a => [pad to :string & 6]</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 337 355 373 535 553 733 2227 2272 2335 2353 |
|||
2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 |
|||
5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 |
|||
32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 |
|||
223222 232222 322222</pre> |
|||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
===Counting and testing=== |
|||
<lang AWK> |
|||
<syntaxhighlight lang="awk"> |
|||
# syntax: GAWK -f NUMBERS_WITH_PRIME_DIGITS_WHOSE_SUM_IS_13.AWK |
# syntax: GAWK -f NUMBERS_WITH_PRIME_DIGITS_WHOSE_SUM_IS_13.AWK |
||
BEGIN { |
BEGIN { |
||
Line 79: | Line 275: | ||
return(sum == 13) |
return(sum == 13) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 87: | Line 283: | ||
32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 |
32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 |
||
223222 232222 322222 |
223222 232222 322222 |
||
</pre> |
|||
===Generate digit combinations directly=== |
|||
<syntaxhighlight lang="awk">BEGIN { |
|||
o = 1 |
|||
src[o++] = 13 |
|||
do { |
|||
r = src[++i] |
|||
n = src[++i] |
|||
for (p = 2; p != 9; p += p % 2 + 1) { |
|||
if (p >= r) { |
|||
if (p == r) res = res " " n p |
|||
break |
|||
} |
|||
src[++o] = r - p |
|||
src[++o] = n p |
|||
} |
|||
} while (i != o) |
|||
print substr(res, 2) |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222</pre> |
|||
=={{header|bc}}== |
|||
<syntaxhighlight lang="bc">q[0] = 13 |
|||
o = 2 |
|||
while (i != o) { |
|||
r = q[i++] |
|||
n = q[i++] |
|||
for (p = 2; p != 9; p += p % 2 + 1) { |
|||
if (p >= r) { |
|||
if (p == r) n + p |
|||
break |
|||
} |
|||
q[o++] = r - p |
|||
q[o++] = (n + p) * 10 |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre style="max-height:12em"> |
|||
337 |
|||
355 |
|||
373 |
|||
535 |
|||
553 |
|||
733 |
|||
2227 |
|||
2272 |
|||
2335 |
|||
2353 |
|||
2533 |
|||
2722 |
|||
3235 |
|||
3253 |
|||
3325 |
|||
3352 |
|||
3523 |
|||
3532 |
|||
5233 |
|||
5323 |
|||
5332 |
|||
7222 |
|||
22225 |
|||
22252 |
|||
22333 |
|||
22522 |
|||
23233 |
|||
23323 |
|||
23332 |
|||
25222 |
|||
32233 |
|||
32323 |
|||
32332 |
|||
33223 |
|||
33232 |
|||
33322 |
|||
52222 |
|||
222223 |
|||
222232 |
|||
222322 |
|||
223222 |
|||
232222 |
|||
322222 |
|||
</pre> |
</pre> |
||
=={{header|C}}== |
=={{header|C}}== |
||
Brute force |
Brute force |
||
< |
<syntaxhighlight lang="c">#include <stdbool.h> |
||
#include <stdio.h> |
#include <stdio.h> |
||
Line 130: | Line 408: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 337 355 373 535 553 733 2227 2272 2335 2353 2533 |
<pre> 337 355 373 535 553 733 2227 2272 2335 2353 2533 |
||
Line 140: | Line 418: | ||
{{Trans|Phix}} |
{{Trans|Phix}} |
||
Same recursive method. |
Same recursive method. |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
using static System.Console; |
using static System.Console; |
||
using LI = System.Collections.Generic.SortedSet<int>; |
using LI = System.Collections.Generic.SortedSet<int>; |
||
Line 154: | Line 432: | ||
static void Main(string[] args) { WriteLine(string.Join(" ", |
static void Main(string[] args) { WriteLine(string.Join(" ", |
||
unl(new LI {}, new LI { 2, 3, 5, 7 }, 13))); } |
unl(new LI {}, new LI { 2, 3, 5, 7 }, 13))); } |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre style="white-space:pre-wrap;">337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222 |
<pre style="white-space:pre-wrap;">337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222 |
||
Line 160: | Line 438: | ||
=== Alternate === |
=== Alternate === |
||
Based in '''Nigel Galloway's''' suggestion from the discussion page. |
Based in '''Nigel Galloway's''' suggestion from the discussion page. |
||
< |
<syntaxhighlight lang="csharp">class Program { |
||
static void Main(string[] args) { int[] lst; int sum; |
static void Main(string[] args) { int[] lst; int sum; |
||
Line 170: | Line 448: | ||
else if (sum < 12) |
else if (sum < 12) |
||
w.Add((i.digs * 10 + j, sum)); } } |
w.Add((i.digs * 10 + j, sum)); } } |
||
}</ |
}</syntaxhighlight> |
||
Same output. |
Same output. |
||
=={{header|C++}}== |
=={{header|C++}}== |
||
{{trans|C#}}(the alternate version) |
{{trans|C#}}(the alternate version) |
||
< |
<syntaxhighlight lang="cpp">#include <cstdio> |
||
#include <vector> |
#include <vector> |
||
#include <bits/stdc++.h> |
#include <bits/stdc++.h> |
||
Line 188: | Line 466: | ||
printf("%d%d ", get<0>(i), x); |
printf("%d%d ", get<0>(i), x); |
||
else if (sum < 12) w.push_back({get<0>(i) * 10 + x, sum}); } |
else if (sum < 12) w.push_back({get<0>(i) * 10 + x, sum}); } |
||
return 0; }</ |
return 0; }</syntaxhighlight> |
||
Same output as C#. |
Same output as C#. |
||
=={{header|D}}== |
=={{header|D}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="d">import std.stdio; |
||
bool primeDigitsSum13(int n) { |
bool primeDigitsSum13(int n) { |
||
Line 224: | Line 502: | ||
} |
} |
||
writeln; |
writeln; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 337 355 373 535 553 733 2227 2272 2335 2353 2533 |
<pre> 337 355 373 535 553 733 2227 2272 2335 2353 2533 |
||
Line 230: | Line 508: | ||
22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 |
22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 |
||
33223 33232 33322 52222 222223 222232 222322 223222 232222 322222</pre> |
33223 33232 33322 52222 222223 222232 222322 223222 232222 322222</pre> |
||
=={{header|EasyLang}}== |
|||
<syntaxhighlight> |
|||
func digprimsum13 n . |
|||
while n > 0 |
|||
d = n mod 10 |
|||
if d < 2 or d = 4 or d = 6 or d >= 8 |
|||
return 0 |
|||
. |
|||
sum += d |
|||
n = n div 10 |
|||
. |
|||
return if sum = 13 |
|||
. |
|||
p = 2 |
|||
while p <= 322222 |
|||
if digprimsum13 p = 1 |
|||
write p & " " |
|||
. |
|||
p += 1 |
|||
. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222 |
|||
</pre> |
|||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// prime digits whose sum is 13. Nigel Galloway: October 21st., 2020 |
// prime digits whose sum is 13. Nigel Galloway: October 21st., 2020 |
||
let rec fN g=let g=[for n in [2;3;5;7] do for g in g->n::g]|>List.groupBy(fun n->match List.sum n with 13->'n' |n when n<12->'g' |_->'x')|>Map.ofSeq |
let rec fN g=let g=[for n in [2;3;5;7] do for g in g->n::g]|>List.groupBy(fun n->match List.sum n with 13->'n' |n when n<12->'g' |_->'x')|>Map.ofSeq |
||
[yield! (if g.ContainsKey 'n' then g.['n'] else []); yield! (if g.ContainsKey 'g' then fN g.['g'] else [])] |
[yield! (if g.ContainsKey 'n' then g.['n'] else []); yield! (if g.ContainsKey 'g' then fN g.['g'] else [])] |
||
fN [[]] |> Seq.iter(fun n->n|>List.iter(printf "%d");printf " ");printfn "" |
fN [[]] |> Seq.iter(fun n->n|>List.iter(printf "%d");printf " ");printfn "" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 246: | Line 550: | ||
===Filtering selections=== |
===Filtering selections=== |
||
Generate all selections of the prime digits in the only possible lengths whose sum can be 13, then filter for sums that equal 13. |
Generate all selections of the prime digits in the only possible lengths whose sum can be 13, then filter for sums that equal 13. |
||
< |
<syntaxhighlight lang="factor">USING: formatting io kernel math math.combinatorics |
||
math.functions math.ranges sequences sequences.extras ; |
math.functions math.ranges sequences sequences.extras ; |
||
Line 253: | Line 557: | ||
"Numbers whose digits are prime and sum to 13:" print |
"Numbers whose digits are prime and sum to 13:" print |
||
{ 2 3 5 7 } 3 6 [a,b] [ selections [ sum 13 = ] filter ] with |
{ 2 3 5 7 } 3 6 [a,b] [ selections [ sum 13 = ] filter ] with |
||
map-concat [ digits>number ] map "%[%d, %]\n" printf</ |
map-concat [ digits>number ] map "%[%d, %]\n" printf</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 259: | Line 563: | ||
{ 337, 355, 373, 535, 553, 733, 2227, 2272, 2335, 2353, 2533, 2722, 3235, 3253, 3325, 3352, 3523, 3532, 5233, 5323, 5332, 7222, 22225, 22252, 22333, 22522, 23233, 23323, 23332, 25222, 32233, 32323, 32332, 33223, 33232, 33322, 52222, 222223, 222232, 222322, 223222, 232222, 322222 } |
{ 337, 355, 373, 535, 553, 733, 2227, 2272, 2335, 2353, 2533, 2722, 3235, 3253, 3325, 3352, 3523, 3532, 5233, 5323, 5332, 7222, 22225, 22252, 22333, 22522, 23233, 23323, 23332, 25222, 32233, 32323, 32332, 33223, 33232, 33322, 52222, 222223, 222232, 222322, 223222, 232222, 322222 } |
||
</pre> |
</pre> |
||
=={{header|Delphi}}== |
|||
{{works with|Delphi|6.0}} |
|||
{{libheader|SysUtils,StdCtrls}} |
|||
<syntaxhighlight lang="Delphi"> |
|||
function IsPrime(N: int64): boolean; |
|||
{Fast, optimised prime test} |
|||
var I,Stop: int64; |
|||
begin |
|||
if (N = 2) or (N=3) then Result:=true |
|||
else if (n <= 1) or ((n mod 2) = 0) or ((n mod 3) = 0) then Result:= false |
|||
else |
|||
begin |
|||
I:=5; |
|||
Stop:=Trunc(sqrt(N+0.0)); |
|||
Result:=False; |
|||
while I<=Stop do |
|||
begin |
|||
if ((N mod I) = 0) or ((N mod (I + 2)) = 0) then exit; |
|||
Inc(I,6); |
|||
end; |
|||
Result:=True; |
|||
end; |
|||
end; |
|||
procedure GetDigits(N: integer; var IA: TIntegerDynArray); |
|||
{Get an array of the integers in a number} |
|||
var T: integer; |
|||
begin |
|||
SetLength(IA,0); |
|||
repeat |
|||
begin |
|||
T:=N mod 10; |
|||
N:=N div 10; |
|||
SetLength(IA,Length(IA)+1); |
|||
IA[High(IA)]:=T; |
|||
end |
|||
until N<1; |
|||
end; |
|||
function IsPrimeDigitSum13(N: integer): boolean; |
|||
{Return true N's digits are prime and total 13} |
|||
var IA: TIntegerDynArray; |
|||
var I,Sum: integer; |
|||
begin |
|||
Result:=False; |
|||
GetDigits(N,IA); |
|||
for I:=0 to High(IA) do |
|||
if not IsPrime(IA[I]) then exit; |
|||
Sum:=0; |
|||
for I:=0 to High(IA) do Sum:=Sum+IA[I]; |
|||
Result:=Sum=13; |
|||
end; |
|||
procedure ShowPrimeDigitSum13(Memo: TMemo); |
|||
{Show numbers whose digits are prime and total 13} |
|||
var I,Cnt: integer; |
|||
var S: string; |
|||
begin |
|||
Cnt:=0; |
|||
for I:=1 to 999999 do |
|||
if IsPrimeDigitSum13(I) then |
|||
begin |
|||
Inc(Cnt); |
|||
S:=S+Format('%8D',[I]); |
|||
If (Cnt mod 5)=0 then S:=S+#$0D#$0A; |
|||
end; |
|||
Memo.Lines.Add(S); |
|||
end; |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
337 355 373 535 553 |
|||
733 2227 2272 2335 2353 |
|||
2533 2722 3235 3253 3325 |
|||
3352 3523 3532 5233 5323 |
|||
5332 7222 22225 22252 22333 |
|||
22522 23233 23323 23332 25222 |
|||
32233 32323 32332 33223 33232 |
|||
33322 52222 222223 222232 222322 |
|||
223222 232222 322222 |
|||
Elapsed Time: 627.207 ms. |
|||
</pre> |
|||
===F# translation=== |
===F# translation=== |
||
The following is based on Nigel Galloway's algorithm as described [http://rosettacode.org/wiki/Talk:Numbers_with_prime_digits_whose_sum_is_13#Nice_recursive_solution here] on the talk page. It's about 10x faster than the previous method. |
The following is based on Nigel Galloway's algorithm as described [http://rosettacode.org/wiki/Talk:Numbers_with_prime_digits_whose_sum_is_13#Nice_recursive_solution here] on the talk page. It's about 10x faster than the previous method. |
||
< |
<syntaxhighlight lang="factor">USING: io kernel math prettyprint sequences sequences.extras ; |
||
{ } { { 2 } { 3 } { 5 } { 7 } } [ |
{ } { { 2 } { 3 } { 5 } { 7 } } [ |
||
{ 2 3 5 7 } [ suffix ] cartesian-map concat |
{ 2 3 5 7 } [ suffix ] cartesian-map concat |
||
[ sum 13 = ] partition [ append ] dip [ sum 11 > ] reject |
[ sum 13 = ] partition [ append ] dip [ sum 11 > ] reject |
||
] until-empty [ bl ] [ [ pprint ] each ] interleave nl</ |
] until-empty [ bl ] [ [ pprint ] each ] interleave nl</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 275: | Line 673: | ||
Ho hum. Another prime digits task. |
Ho hum. Another prime digits task. |
||
< |
<syntaxhighlight lang="freebasic"> |
||
function digit_is_prime( n as integer ) as boolean |
function digit_is_prime( n as integer ) as boolean |
||
select case n |
select case n |
||
Line 305: | Line 703: | ||
for i as uinteger = 1 to 322222 |
for i as uinteger = 1 to 322222 |
||
if all_digits_prime(i) andalso digit_sum_13(i) then print i, |
if all_digits_prime(i) andalso digit_sum_13(i) then print i, |
||
next i</ |
next i</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 320: | Line 718: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
Reuses code from some other tasks. |
Reuses code from some other tasks. |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 393: | Line 791: | ||
fmt.Println("Those numbers whose digits are all prime and sum to 13 are:") |
fmt.Println("Those numbers whose digits are all prime and sum to 13 are:") |
||
fmt.Println(res2) |
fmt.Println(res2) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 402: | Line 800: | ||
===only counting=== |
===only counting=== |
||
See Julia [http://rosettacode.org/wiki/Numbers_with_prime_digits_whose_sum_is_13#Julia] |
See Julia [http://rosettacode.org/wiki/Numbers_with_prime_digits_whose_sum_is_13#Julia] |
||
<syntaxhighlight lang="go"> |
|||
<lang go> |
|||
package main |
package main |
||
Line 491: | Line 889: | ||
fmt.Println("The count of numbers whose digits are all prime and sum to",mySum,"is",gblCount) |
fmt.Println("The count of numbers whose digits are all prime and sum to",mySum,"is",gblCount) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 528: | Line 926: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
As an unfold, in the recursive pattern described by Nigel Galloway on the Talk page. |
As an unfold, in the recursive pattern described by Nigel Galloway on the Talk page. |
||
< |
<syntaxhighlight lang="haskell">import Data.List.Split (chunksOf) |
||
import Data.List (intercalate, transpose, unfoldr) |
import Data.List (intercalate, transpose, unfoldr) |
||
import Text.Printf |
import Text.Printf |
||
Line 577: | Line 975: | ||
unDigits :: [Int] -> Int |
unDigits :: [Int] -> Int |
||
unDigits = foldl ((+) . (10 *)) 0</ |
unDigits = foldl ((+) . (10 *)) 0</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>43 numbers with prime digits summing to 13: |
<pre>43 numbers with prime digits summing to 13: |
||
Line 586: | Line 984: | ||
32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 |
32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 |
||
223222 232222 322222</pre> |
223222 232222 322222</pre> |
||
=={{header|J}}== |
|||
Galloway's algorithm, from the talk page: |
|||
<syntaxhighlight lang=J>ps13=: {{ |
|||
seq=. 0#,D=. ,Q=. ":,.p:i.4 |
|||
while. #Q do. |
|||
N=. ,/D,"0 1/Q |
|||
i=. +/"1"."0 N |
|||
Q=. (12>i)#N |
|||
seq=. seq,,".(13=i)#N |
|||
end. |
|||
}}0</syntaxhighlight> |
|||
Here, upper case names are character arrays representing digits, lower case names are numeric arrays. |
|||
<code>Q</code> (number suffixes) and <code>N</code> (candidate numbers) represent sequences of sequences of characters. (The top level sequence -- rows -- distinguishes different potential numbers and the secondary sequence -- columns -- distinguishes digits within potential numbers). |
|||
Meanwhile, <code>D</code> (prime digits), <code>i</code> (digit sums) and <code>seq</code> (numbers whose digit sum is 13) are simple sequences. |
|||
<syntaxhighlight lang=J> ps13 |
|||
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222</syntaxhighlight> |
|||
=={{header|Java}}== |
|||
{{trans|Kotlin}} |
|||
<syntaxhighlight lang="java">public class PrimeDigits { |
|||
private static boolean primeDigitsSum13(int n) { |
|||
int sum = 0; |
|||
while (n > 0) { |
|||
int r = n % 10; |
|||
if (r != 2 && r != 3 && r != 5 && r != 7) { |
|||
return false; |
|||
} |
|||
n /= 10; |
|||
sum += r; |
|||
} |
|||
return sum == 13; |
|||
} |
|||
public static void main(String[] args) { |
|||
// using 2 for all digits, 6 digits is the max prior to over-shooting 13 |
|||
int c = 0; |
|||
for (int i = 1; i < 1_000_000; i++) { |
|||
if (primeDigitsSum13(i)) { |
|||
System.out.printf("%6d ", i); |
|||
if (c++ == 10) { |
|||
c = 0; |
|||
System.out.println(); |
|||
} |
|||
} |
|||
} |
|||
System.out.println(); |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 337 355 373 535 553 733 2227 2272 2335 2353 2533 |
|||
2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 |
|||
22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 |
|||
33223 33232 33322 52222 222223 222232 222322 223222 232222 322222 </pre> |
|||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
As an unfold, in the recursive pattern described by Nigel Galloway on the Talk page. |
As an unfold, in the recursive pattern described by Nigel Galloway on the Talk page. |
||
< |
<syntaxhighlight lang="javascript">(() => { |
||
'use strict'; |
'use strict'; |
||
Line 769: | Line 1,227: | ||
return main(); |
return main(); |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>337,355,373,535,553,733 |
<pre>337,355,373,535,553,733 |
||
Line 779: | Line 1,237: | ||
52222,222223,222232,222322,223222,232222 |
52222,222223,222232,222322,223222,232222 |
||
322222</pre> |
322222</pre> |
||
=={{header|jq}}== |
|||
{{works with|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. |
|||
All three solutions are based on the observation that the only decimal digits which are prime are [2, 3, 5, 7]. |
|||
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); |
|||
====Simple Generate-and-Test Solution==== |
|||
<syntaxhighlight lang="jq"># Output: a stream |
|||
def simple: |
|||
range(2; 7) as $n |
|||
| [2, 3, 5, 7] |
|||
| combinations($n) |
|||
| select(add == 13) |
|||
| join("") | tonumber; |
|||
count(simple)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
43 |
|||
</pre> |
|||
====A Faster Solution==== |
|||
<syntaxhighlight lang="jq">def faster: |
|||
def digits: [2, 3, 5, 7]; |
|||
def wide($max): |
|||
def d: digits[] | select(. <= $max); |
|||
if . == 1 then d | [.] |
|||
else d as $first |
|||
| (. - 1 | wide($max - $first)) as $next |
|||
| [$first] + $next |
|||
end; |
|||
range(2; 7) |
|||
| wide(13) |
|||
| select(add == 13) |
|||
| join("") | tonumber; |
|||
count(faster) |
|||
</syntaxhighlight> |
|||
{{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. |
|||
<syntaxhighlight 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)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
43 |
|||
349321957098598244959032342621956 |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">using Combinatorics, Primes |
||
function primedigitsums(targetsum) |
function primedigitsums(targetsum) |
||
Line 828: | Line 1,375: | ||
foreach(countprimedigitsums, nextprimes(17, 40)) |
foreach(countprimedigitsums, nextprimes(17, 40)) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
There are 3 prime-digit-only numbers summing to 5 : [5, 32, 23] |
There are 3 prime-digit-only numbers summing to 5 : [5, 32, 23] |
||
Line 878: | Line 1,425: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|D}} |
{{trans|D}} |
||
< |
<syntaxhighlight lang="scala">fun primeDigitsSum13(n: Int): Boolean { |
||
var nn = n |
var nn = n |
||
var sum = 0 |
var sum = 0 |
||
Line 905: | Line 1,452: | ||
} |
} |
||
println() |
println() |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 337 355 373 535 553 733 2227 2272 2335 2353 2533 |
<pre> 337 355 373 535 553 733 2227 2272 2335 2353 2533 |
||
Line 911: | Line 1,458: | ||
22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 |
22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 |
||
33223 33232 33322 52222 222223 222232 222322 223222 232222 322222 </pre> |
33223 33232 33322 52222 222223 222232 222322 223222 232222 322222 </pre> |
||
=={{header|Lua}}== |
|||
{{trans|C}} |
|||
<syntaxhighlight lang="lua">function prime_digits_sum_13(n) |
|||
local sum = 0 |
|||
while n > 0 do |
|||
local r = n % 10 |
|||
if r ~= 2 and r ~= 3 and r ~= 5 and r ~= 7 then |
|||
return false |
|||
end |
|||
n = math.floor(n / 10) |
|||
sum = sum + r |
|||
end |
|||
return sum == 13 |
|||
end |
|||
local c = 0 |
|||
for i=1,999999 do |
|||
if prime_digits_sum_13(i) then |
|||
io.write(string.format("%6d ", i)) |
|||
if c == 10 then |
|||
c = 0 |
|||
print() |
|||
else |
|||
c = c + 1 |
|||
end |
|||
end |
|||
end |
|||
print()</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 337 355 373 535 553 733 2227 2272 2335 2353 2533 |
|||
2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 |
|||
22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 |
|||
33223 33232 33322 52222 222223 222232 222322 223222 232222 322222 </pre> |
|||
=={{header|Nim}}== |
|||
<syntaxhighlight lang="nim">import math, sequtils, strutils |
|||
type Digit = 0..9 |
|||
proc toInt(s: seq[Digit]): int = |
|||
## Convert a sequence of digits to an integer. |
|||
for n in s: |
|||
result = 10 * result + n |
|||
const PrimeDigits = @[Digit 2, 3, 5, 7] |
|||
var list = PrimeDigits.mapIt(@[it]) # List of sequences of digits. |
|||
var result: seq[int] |
|||
while list.len != 0: |
|||
var nextList: seq[seq[Digit]] # List with one more digit. |
|||
for digitSeq in list: |
|||
let currSum = sum(digitSeq) |
|||
for n in PrimeDigits: |
|||
let newSum = currSum + n |
|||
let newDigitSeq = digitSeq & n |
|||
if newSum < 13: nextList.add newDigitSeq |
|||
elif newSum == 13: result.add newDigitSeq.toInt |
|||
else: break |
|||
list = move(nextList) |
|||
for i, n in result: |
|||
stdout.write ($n).align(6), if (i + 1) mod 9 == 0: '\n' else: ' ' |
|||
echo()</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 337 355 373 535 553 733 2227 2272 2335 |
|||
2353 2533 2722 3235 3253 3325 3352 3523 3532 |
|||
5233 5323 5332 7222 22225 22252 22333 22522 23233 |
|||
23323 23332 25222 32233 32323 32332 33223 33232 33322 |
|||
52222 222223 222232 222322 223222 232222 322222 </pre> |
|||
=={{header|OCaml}}== |
|||
<syntaxhighlight lang="ocaml">let prime_digits_13 = |
|||
let digits = [2; 3; 5; 7] in |
|||
let rec next ds ns = function |
|||
| [] -> if ns = [] then [] else next digits [] (List.rev ns) |
|||
| (n, r) :: cs' as cs -> |
|||
match ds with |
|||
| d :: ds' when d < r -> next ds' (((n + d) * 10, r - d) :: ns) cs |
|||
| d :: ds' when d = r -> n + d :: next digits ns cs' |
|||
| _ -> next digits ns cs' |
|||
in next digits [] [0, 13] |
|||
let () = |
|||
List.map string_of_int prime_digits_13 |> String.concat " " |> print_endline</syntaxhighlight> |
|||
{{out}} |
|||
<pre>337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222</pre> |
|||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
{{Works with|Free Pascal}} Only counting.<BR>Extreme fast in finding the sum of primesdigits = value.<BR>Limited by Uint64 |
{{Works with|Free Pascal}} Only counting.<BR>Extreme fast in finding the sum of primesdigits = value.<BR>Limited by Uint64 |
||
< |
<syntaxhighlight lang="pascal">program PrimSumUpTo13; |
||
{$IFDEF FPC} |
{$IFDEF FPC} |
||
{$MODE DELPHI} |
{$MODE DELPHI} |
||
Line 1,057: | Line 1,692: | ||
writeln(num:6,gblCount:25,' '); |
writeln(num:6,gblCount:25,' '); |
||
until num > MAXNUM; |
until num > MAXNUM; |
||
END.</ |
END.</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre> Sum Count of arrangements |
<pre> Sum Count of arrangements |
||
Line 1,093: | Line 1,728: | ||
</pre> |
</pre> |
||
===using gmp=== |
===using gmp=== |
||
< |
<syntaxhighlight lang="pascal">program PrimSumUpTo13_GMP; |
||
{$IFDEF FPC} |
{$IFDEF FPC} |
||
{$OPTIMIZATION ON,ALL} |
{$OPTIMIZATION ON,ALL} |
||
Line 1,308: | Line 1,943: | ||
z_clear(gblSum); |
z_clear(gblSum); |
||
z_clear(gbldelta); |
z_clear(gbldelta); |
||
END.</ |
END.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,362: | Line 1,997: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">#!/usr/bin/perl |
||
use strict; |
use strict; |
||
Line 1,381: | Line 2,016: | ||
} |
} |
||
} |
} |
||
print $numbers =~ s/.{1,80}\K /\n/gr;</ |
print $numbers =~ s/.{1,80}\K /\n/gr;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,390: | Line 2,025: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--(phixonline)--> |
|||
<lang Phix>function unlucky(sequence set, integer needed, string v="", sequence res={}) |
|||
<syntaxhighlight lang="phix"> |
|||
with javascript_semantics |
|||
function unlucky(sequence set, integer needed, string v="", sequence res={}) |
|||
if needed=0 then |
if needed=0 then |
||
res = append(res,sprintf("%6s",v)) |
res = append(res,sprintf("%6s",v)) |
||
Line 1,400: | Line 2,038: | ||
return res |
return res |
||
end function |
end function |
||
sequence r = sort(unlucky({2,3,5,7},13)) |
sequence r = sort(unlucky({2,3,5,7},13)) |
||
puts(1,join_by(r,1,11," ")) |
puts(1,join_by(r,1,11," ")) |
||
</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,412: | Line 2,050: | ||
===iterative=== |
===iterative=== |
||
Queue-based version of Nigel's recursive algorithm, same output. |
Queue-based version of Nigel's recursive algorithm, same output. |
||
<!--(phixonline)--> |
|||
<lang Phix>requires("0.8.2") -- uses latest apply() mods, rest is fine |
|||
<syntaxhighlight lang="phix"> |
|||
with javascript_semantics |
|||
requires("0.8.2") -- uses latest apply() mods, rest is fine |
|||
constant dgts = {2,3,5,7} |
constant dgts = {2,3,5,7} |
||
function unlucky() |
function unlucky() |
||
Line 1,428: | Line 2,069: | ||
return res |
return res |
||
end function |
end function |
||
sequence r = unlucky() |
sequence r = unlucky() |
||
r = apply(true,sprintf,{{"%6d"},r}) |
r = apply(true,sprintf,{{"%6d"},r}) |
||
puts(1,join_by(r,1,11," ")) |
puts(1,join_by(r,1,11," ")) |
||
</syntaxhighlight> |
|||
I've archived a slightly more OTT version: [[Numbers_with_prime_digits_whose_sum_is_13/Phix]]. |
I've archived a slightly more OTT version: [[Numbers_with_prime_digits_whose_sum_is_13/Phix]]. |
||
=={{header|Prolog}}== |
|||
<syntaxhighlight lang="prolog"> |
|||
digit_sum(N, M) :- digit_sum(N, 0, M). |
|||
digit_sum(0, A, B) :- !, A = B. |
|||
digit_sum(N, A0, M) :- |
|||
divmod(N, 10, Q, R), |
|||
plus(A0, R, A1), |
|||
digit_sum(Q, A1, M). |
|||
prime_digits(0). |
|||
prime_digits(N) :- |
|||
prime_digits(M), |
|||
member(D, [2, 3, 5, 7]), |
|||
N is 10 * M + D. |
|||
prime13(N) :- |
|||
prime_digits(N), |
|||
(N > 333_333 -> !, false ; true), |
|||
digit_sum(N, 13). |
|||
main :- |
|||
findall(N, prime13(N), S), |
|||
format("Those numbers whose digits are all prime and sum to 13 are: ~n~w~n", [S]), |
|||
halt. |
|||
?- main. |
|||
</syntaxhighlight> |
|||
{{Out}} |
|||
<pre> |
|||
Those numbers whose digits are all prime and sum to 13 are: |
|||
[337,355,373,535,553,733,2227,2272,2335,2353,2533,2722,3235,3253,3325,3352,3523,3532,5233,5323,5332,7222,22225,22252,22333,22522,23233,23323,23332,25222,32233,32323,32332,33223,33232,33322,52222,222223,222232,222322,223222,232222,322222] |
|||
</pre> |
|||
=={{header|Python}}== |
|||
With improvements to the ideas from the discussion page: |
|||
<syntaxhighlight lang="python">from collections import deque |
|||
def prime_digits_sum(r): |
|||
q = deque([(r, 0)]) |
|||
while q: |
|||
r, n = q.popleft() |
|||
for d in 2, 3, 5, 7: |
|||
if d >= r: |
|||
if d == r: yield n + d |
|||
break |
|||
q.append((r - d, (n + d) * 10)) |
|||
print(*prime_digits_sum(13))</syntaxhighlight> |
|||
{{out}} |
|||
<pre>337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222</pre> |
|||
=={{header|Quackery}}== |
|||
<syntaxhighlight lang="Quackery"> [] ' [ [ ] ] |
|||
[ behead |
|||
' [ 2 3 5 7 ] witheach |
|||
[ dip dup join |
|||
0 over witheach + |
|||
dup 13 = iff |
|||
[ drop nested |
|||
dip rot join |
|||
unrot conclude ] |
|||
done |
|||
11 > iff drop done |
|||
nested swap dip join ] |
|||
drop dup [] = until ] |
|||
swap witheach |
|||
[ 0 swap witheach |
|||
[ swap 10 * + ] |
|||
number$ nested join ] |
|||
60 wrap$</syntaxhighlight> |
|||
{{out}} |
|||
<pre>337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 |
|||
3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 |
|||
22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 |
|||
33232 33322 52222 222223 222232 222322 223222 232222 322222 |
|||
</pre> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
<lang |
<syntaxhighlight lang="raku" line>put join ', ', sort +*, unique flat |
||
< 2 2 2 2 2 3 3 3 5 5 7 >.combinations |
< 2 2 2 2 2 3 3 3 5 5 7 >.combinations |
||
.grep( *.sum == 13 ) |
.grep( *.sum == 13 ) |
||
.map( { .join => $_ } ) |
.map( { .join => $_ } ) |
||
.map: { .value.permutations».join }</ |
.map: { .value.permutations».join }</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>337, 355, 373, 535, 553, 733, 2227, 2272, 2335, 2353, 2533, 2722, 3235, 3253, 3325, 3352, 3523, 3532, 5233, 5323, 5332, 7222, 22225, 22252, 22333, 22522, 23233, 23323, 23332, 25222, 32233, 32323, 32332, 33223, 33232, 33322, 52222, 222223, 222232, 222322, 223222, 232222, 322222</pre> |
<pre>337, 355, 373, 535, 553, 733, 2227, 2272, 2335, 2353, 2533, 2722, 3235, 3253, 3325, 3352, 3523, 3532, 5233, 5323, 5332, 7222, 22225, 22252, 22333, 22522, 23233, 23323, 23332, 25222, 32233, 32323, 32332, 33223, 33232, 33322, 52222, 222223, 222232, 222322, 223222, 232222, 322222</pre> |
||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
< |
<syntaxhighlight lang="rexx">/*REXX pgm finds and displays all decimal numbers whose digits are prime and sum to 13. */ |
||
LO |
parse arg LO HI COLS . /*obtain optional arguments from the CL*/ |
||
if LO=='' | LO=="," then LO= 337 /*Not specified? Then use the default.*/ |
|||
if HI=='' | HI=="," then HI= 322222 /* " " " " " " */ |
|||
if cols=='' | cols=="," then cols= 10 /* " " " " " " */ |
|||
w= 10 /*width of a number in any column. */ |
|||
title= ' decimal numbers found whose digits are prime and sum to 13 ' |
|||
say ' index │'center(title, 1 + cols*(w+1) ) |
|||
say '───────┼'center("" , 1 + cols*(w+1), '─') |
|||
w= 10 /*max width of a integer in any column.*/ |
|||
found= 0; idx= 1 /*the number of numbers found (so far).*/ |
|||
$= /*variable to hold the list of #s found*/ |
$= /*variable to hold the list of #s found*/ |
||
do j=LO for HI-LO+1 /*search for numbers in this range. */ |
do j=LO for HI-LO+1 /*search for numbers in this range. */ |
||
Line 1,455: | Line 2,185: | ||
sum= sum + substr(j, k, 1) /*sum some middle decimal digits of J.*/ |
sum= sum + substr(j, k, 1) /*sum some middle decimal digits of J.*/ |
||
end /*k*/ |
end /*k*/ |
||
if sum\==13 |
if sum\==13 then iterate /*Sum not equal to 13? Then skip this #*/ |
||
found= found + 1 /*bump the number of numbers found. */ |
|||
c= commas(j) /*maybe add commas to the number. */ |
|||
$= $ right( commas(j), w) /*add the found number ───► the $ list.*/ |
|||
if found//cols\==0 then iterate /*have we populated a line of output? */ |
|||
say center(idx, 7)'│' substr($, 2); $= /*display what we have so far (cols). */ |
|||
idx= idx + cols /*bump the index count for the output*/ |
|||
end /*j*/ |
end /*j*/ |
||
if $\=='' then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/ |
|||
say '───────┴'center("" , 1 + cols*(w+1), '─') |
|||
say # ' decimal numbers found whose digits are prime and the decimal digits sum to 13'</lang> |
|||
say |
|||
say 'Found ' commas(found) title |
|||
exit 0 /*stick a fork in it, we're all done. */ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
commas: parse arg _; do jc=length(_)-3 to 1 by -3; _=insert(',', _, jc); end; return _</syntaxhighlight> |
|||
{{out|output|text= when using the internal default inputs:}} |
{{out|output|text= when using the internal default inputs:}} |
||
<pre> |
<pre> |
||
index │ decimal numbers found whose digits are prime and sum to 13 |
|||
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222 |
|||
───────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────── |
|||
1 │ 337 355 373 535 553 733 2,227 2,272 2,335 2,353 |
|||
11 │ 2,533 2,722 3,235 3,253 3,325 3,352 3,523 3,532 5,233 5,323 |
|||
21 │ 5,332 7,222 22,225 22,252 22,333 22,522 23,233 23,323 23,332 25,222 |
|||
31 │ 32,233 32,323 32,332 33,223 33,232 33,322 52,222 222,223 222,232 222,322 |
|||
41 │ 223,222 232,222 322,222 |
|||
───────┴─────────────────────────────────────────────────────────────────────────────────────────────────────────────── |
|||
43 decimal numbers found whose digits are prime and |
Found 43 decimal numbers found whose digits are prime and sum to 13 |
||
</pre> |
</pre> |
||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
load "stdlib.ring" |
load "stdlib.ring" |
||
Line 1,503: | Line 2,250: | ||
next |
next |
||
? "[" + left(svect, len(svect) - 1) + "]" |
? "[" + left(svect, len(svect) - 1) + "]" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,509: | Line 2,256: | ||
[337,355,373,535,553,733,2227,2272,2335,2353,2533,2722,3235,3253,3325,3352,3523,3532,5233,5323,5332,7222,22225,22252,22333,22522,23233,23323,23332,25222,32233,32323,32332,33223,33232,33322,52222,222223,222232,222322,223222,232222,322222] |
[337,355,373,535,553,733,2227,2272,2335,2353,2533,2722,3235,3253,3325,3352,3523,3532,5233,5323,5332,7222,22225,22252,22333,22522,23233,23323,23332,25222,32233,32323,32332,33223,33232,33322,52222,222223,222232,222322,223222,232222,322222] |
||
</pre> |
</pre> |
||
=={{header|RPL}}== |
|||
Nice recursive solution from the discussion page: |
|||
{{works with|HP|49}} |
|||
« { } { "" } |
|||
'''DO''' { } |
|||
1 PICK3 SIZE '''FOR''' j |
|||
2 7 '''FOR''' d |
|||
OVER j GET d + |
|||
0 |
|||
1 PICK3 SIZE '''FOR''' k |
|||
OVER k DUP SUB STR→ + |
|||
'''NEXT''' |
|||
'''CASE''' |
|||
DUP 13 == '''THEN''' DROP 4 ROLL SWAP + UNROT '''END''' |
|||
11 > '''THEN''' DROP '''END''' |
|||
+ |
|||
'''END''' |
|||
d 2 ≠ 1 + '''STEP''' <span style="color:grey">@ generates 2 3 5 7 index sequence</span> |
|||
'''NEXT''' NIP |
|||
'''UNTIL''' DUP SIZE NOT '''END''' |
|||
DROP |
|||
» '<span style="color:blue">TASK</span>' STO |
|||
{{out}} |
|||
<pre> |
|||
1: { 337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222 } |
|||
</pre> |
|||
=={{header|Ruby}}== |
|||
{{trans|C}} |
|||
<syntaxhighlight lang="ruby">def primeDigitsSum13(n) |
|||
sum = 0 |
|||
while n > 0 |
|||
r = n % 10 |
|||
if r != 2 and r != 3 and r != 5 and r != 7 then |
|||
return false |
|||
end |
|||
n = (n / 10).floor |
|||
sum = sum + r |
|||
end |
|||
return sum == 13 |
|||
end |
|||
c = 0 |
|||
for i in 1 .. 1000000 |
|||
if primeDigitsSum13(i) then |
|||
print "%6d " % [i] |
|||
if c == 10 then |
|||
c = 0 |
|||
print "\n" |
|||
else |
|||
c = c + 1 |
|||
end |
|||
end |
|||
end |
|||
print "\n" |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 337 355 373 535 553 733 2227 2272 2335 2353 2533 |
|||
2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 |
|||
22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 |
|||
33223 33232 33322 52222 222223 222232 222322 223222 232222 322222</pre> |
|||
=={{header|Sidef}}== |
|||
<syntaxhighlight lang="ruby">func generate_from_prefix(sum, p, base, digits) { |
|||
var seq = [p] |
|||
for d in (digits) { |
|||
seq << __FUNC__(sum, [d, p...], base, digits)... if (p.sum+d <= sum) |
|||
} |
|||
return seq |
|||
} |
|||
func numbers_with_digitsum(sum, base = 10, digits = (base-1 -> primes)) { |
|||
digits.map {|p| generate_from_prefix(sum, [p], base, digits)... }\ |
|||
.map {|t| digits2num(t, base) }\ |
|||
.grep {|t| t.sumdigits(base) == sum }\ |
|||
.sort |
|||
} |
|||
say numbers_with_digitsum(13)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[337, 355, 373, 535, 553, 733, 2227, 2272, 2335, 2353, 2533, 2722, 3235, 3253, 3325, 3352, 3523, 3532, 5233, 5323, 5332, 7222, 22225, 22252, 22333, 22522, 23233, 23323, 23332, 25222, 32233, 32323, 32332, 33223, 33232, 33322, 52222, 222223, 222232, 222322, 223222, 232222, 322222] |
|||
</pre> |
|||
=={{header|Tcl}}== |
|||
<syntaxhighlight lang="tcl">set res {} |
|||
set src [list {} 13] |
|||
while {[llength $src]} { |
|||
set src [lassign $src n r] |
|||
foreach d {2 3 5 7} { |
|||
if {$d >= $r} { |
|||
if {$d == $r} {lappend res "$n$d"} |
|||
break |
|||
} |
|||
lappend src "$n$d" [expr {$r - $d}] |
|||
} |
|||
} |
|||
puts $res</syntaxhighlight> |
|||
{{out}} |
|||
<pre>337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222</pre> |
|||
=={{header|UNIX Shell}}== |
|||
<syntaxhighlight lang="sh">set -- '' 13 |
|||
res='' |
|||
while [ $# -ne 0 ] |
|||
do |
|||
for d in 2 3 5 7 |
|||
do |
|||
[ $d -ge $2 ] && { |
|||
[ $d -eq $2 ] && res=$res${res:+ }$1$d |
|||
break |
|||
} |
|||
set -- "$@" $1$d $(($2 - d)) |
|||
done |
|||
shift 2 |
|||
done |
|||
echo "$res"</syntaxhighlight> |
|||
{{out}} |
|||
<pre>337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222</pre> |
|||
=={{header|Visual Basic .NET}}== |
=={{header|Visual Basic .NET}}== |
||
{{Trans|Phix}} |
{{Trans|Phix}} |
||
Same recursive method. |
Same recursive method. |
||
< |
<syntaxhighlight lang="vbnet">Imports System |
||
Imports System.Console |
Imports System.Console |
||
Imports LI = System.Collections.Generic.SortedSet(Of Integer) |
Imports LI = System.Collections.Generic.SortedSet(Of Integer) |
||
Line 1,533: | Line 2,404: | ||
unl(new LI From {}, new LI From { 2, 3, 5, 7 }, 13))) |
unl(new LI From {}, new LI From { 2, 3, 5, 7 }, 13))) |
||
End Sub |
End Sub |
||
End Module</ |
End Module</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre style="white-space:pre-wrap;">337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222 |
<pre style="white-space:pre-wrap;">337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222 |
||
Line 1,539: | Line 2,410: | ||
=== Alternate === |
=== Alternate === |
||
Thanks to '''Nigel Galloway's''' suggestion from the discussion page. |
Thanks to '''Nigel Galloway's''' suggestion from the discussion page. |
||
< |
<syntaxhighlight lang="vbnet">Imports Tu = System.Tuple(Of Integer, Integer) |
||
Module Module1 |
Module Module1 |
||
Line 1,554: | Line 2,425: | ||
End Sub |
End Sub |
||
End Module</ |
End Module</syntaxhighlight> |
||
Same output. |
Same output. |
||
Line 1,562: | Line 2,433: | ||
{{libheader|Wren-sort}} |
{{libheader|Wren-sort}} |
||
As the only digits which are prime are [2, 3, 5, 7], it is clear that a number must have between 3 and 6 digits for them to sum to 13. |
As the only digits which are prime are [2, 3, 5, 7], it is clear that a number must have between 3 and 6 digits for them to sum to 13. |
||
< |
<syntaxhighlight lang="wren">import "./math" for Nums |
||
import "/seq" for Lst |
import "./seq" for Lst |
||
import "/sort" for Sort |
import "./sort" for Sort |
||
var combrep // recursive |
var combrep // recursive |
||
Line 1,608: | Line 2,479: | ||
Sort.quick(res) |
Sort.quick(res) |
||
System.print("Those numbers whose digits are all prime and sum to 13 are:") |
System.print("Those numbers whose digits are all prime and sum to 13 are:") |
||
System.print(res)</ |
System.print(res)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,617: | Line 2,488: | ||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
<syntaxhighlight lang="xpl0"> |
|||
<lang XPL0> |
|||
int N, M, S, D; |
int N, M, S, D; |
||
[for N:= 2 to 322222 do |
[for N:= 2 to 322222 do |
||
Line 1,632: | Line 2,503: | ||
until M=0; \all digits in N tested or digit not prime |
until M=0; \all digits in N tested or digit not prime |
||
]; |
]; |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
Latest revision as of 21:06, 11 April 2024
Find all the positive integers whose decimal digits are all primes and sum to 13.
11l
F primeDigitsSum13(=n)
V sum = 0
L n > 0
V r = n % 10
I r !C (2, 3, 5, 7)
R 0B
n I/= 10
sum += r
R sum == 13
V c = 0
L(i) 1..999999
I primeDigitsSum13(i)
print(‘#6’.format(i), end' ‘ ’)
I ++c == 11
c = 0
print()
print()
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
Action!
DEFINE PRIMECOUNT="4"
BYTE ARRAY primedigits(PRIMECOUNT)=[2 3 5 7]
PROC PrintNum(BYTE ARRAY code BYTE count)
BYTE i,c
FOR i=0 TO count-1
DO
c=code(i)
Put(primedigits(c)+'0)
OD
RETURN
BYTE FUNC Sum(BYTE ARRAY code BYTE count)
BYTE i,res,c
res=0
FOR i=0 TO count-1
DO
c=code(i)
res==+primedigits(c)
OD
RETURN (res)
PROC Init(BYTE ARRAY code BYTE count)
Zero(code,count)
RETURN
BYTE FUNC Next(BYTE ARRAY code BYTE count)
INT pos,c
pos=count-1
DO
c=code(pos)+1
IF c<PRIMECOUNT THEN
code(pos)=c
RETURN (1)
FI
code(pos)=0
pos==-1
IF pos<0 THEN
RETURN (0)
FI
OD
RETURN (0)
PROC Main()
DEFINE MAXDIG="6"
BYTE ARRAY digits(MAXDIG)
BYTE count,pos
count=1 pos=0
Init(count)
DO
IF Sum(digits,count)=13 THEN
IF pos+count>=38 THEN
pos=0 PutE()
FI
PrintNum(digits,count) Put(32)
pos==+count+1
FI
IF Next(digits,count)=0 THEN
count==+1
IF count>MAXDIG THEN
EXIT
FI
Init(count)
FI
OD
RETURN
- Output:
Screenshot from Atari 8-bit computer
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
ALGOL 68
Based on the Algol W sample.
BEGIN
# find numbers whose digits are prime and whose digit sum is 13 #
# as noted by the Wren sample, the digits can only be 2, 3, 5, 7 #
# and there can only be 3, 4, 5 or 6 digits #
[]INT possible digits = []INT( 0, 2, 3, 5, 7 )[ AT 0 ];
INT number count := 0;
INT zero = ABS "0"; # integer value of the character "0" #
print( ( newline ) );
FOR d1 index FROM 0 TO UPB possible digits DO
INT d1 = possible digits[ d1 index ];
CHAR c1 = IF d1 /= 0 THEN REPR ( d1 + zero ) ELSE " " FI;
FOR d2 index FROM 0 TO UPB possible digits DO
INT d2 = possible digits[ d2 index ];
IF d2 /= 0 OR d1 = 0 THEN
CHAR c2 = IF ( d1 + d2 ) /= 0 THEN REPR ( d2 + zero ) ELSE " " FI;
FOR d3 index FROM 0 TO UPB possible digits DO
INT d3 = possible digits[ d3 index ];
IF d3 /= 0 OR ( d1 + d2 ) = 0 THEN
CHAR c3 = IF ( d1 + d2 + d3 ) /= 0 THEN REPR ( d3 + zero ) ELSE " " FI;
FOR d4 index FROM 1 TO UPB possible digits DO
INT d4 = possible digits[ d4 index ];
CHAR c4 = REPR ( d4 + zero );
FOR d5 index FROM 1 TO UPB possible digits DO
INT d5 = possible digits[ d5 index ];
CHAR c5 = REPR ( d5 + zero );
FOR d6 index FROM 1 TO UPB possible digits DO
INT d6 = possible digits[ d6 index ];
IF ( d1 + d2 + d3 + d4 + d5 + d6 ) = 13 THEN
# found a number whose prime digits sum to 13 #
CHAR c6 = REPR ( d6 + zero );
print( ( " ", c1, c2, c3, c4, c5, c6 ) );
number count := number count + 1;
IF ( number count +:= 1 ) MOD 12 = 0 THEN print( ( newline ) ) FI
FI
OD # d6 #
OD # d5 #
OD # d4 #
FI
OD # d3 #
FI
OD # d2 #
OD # d1 #
END
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
ALGOL W
Uses the observations about the digits and numbers in the Wren solution to generate the sequence.
begin
% find numbers whose digits are prime and whose digit sum is 13 %
% as noted by the Wren sample, the digits can only be 2, 3, 5, 7 %
% and there can only be 3, 4, 5 or 6 digits %
integer numberCount;
numberCount := 0;
write();
for d1 := 0, 2, 3, 5, 7 do begin
for d2 := 0, 2, 3, 5, 7 do begin
if d2 not = 0 or d1 = 0 then begin
for d3 := 0, 2, 3, 5, 7 do begin
if d3 not = 0 or ( d1 = 0 and d2 = 0 ) then begin
for d4 := 2, 3, 5, 7 do begin
for d5 := 2, 3, 5, 7 do begin
for d6 := 2, 3, 5, 7 do begin
integer sum;
sum := d1 + d2 + d3 + d4 + d5 + d6;
if sum = 13 then begin
% found a number whose prime digits sum to 13 %
integer n;
n := 0;
for d := d1, d2, d3, d4, d5, d6 do n := ( n * 10 ) + d;
writeon( i_w := 6, s_w := 1, n );
numberCount := numberCount + 1;
if numberCount rem 12 = 0 then write()
end if_sum_eq_13
end for_d6
end for_d5
end for_d4
end if_d3_ne_0_or_d1_eq_0_and_d2_e_0
end for_d3
end if_d2_ne_0_or_d1_eq_0
end for_d2
end for_d1
end.
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
Arturo
pDigits: [2 3 5 7]
lst: map pDigits 'd -> @[d]
result: new []
while [0 <> size lst][
nextList: new []
loop lst 'digitSeq [
currSum: sum digitSeq
loop pDigits 'n [
newSum: currSum + n
newDigitSeq: digitSeq ++ n
case [newSum]
when? [<13] -> 'nextList ++ @[newDigitSeq]
when? [=13] -> 'result ++ @[to :integer join to [:string] newDigitSeq]
else -> break
]
]
lst: new nextList
]
loop split.every: 10 result 'a ->
print map a => [pad to :string & 6]
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
AWK
Counting and testing
# syntax: GAWK -f NUMBERS_WITH_PRIME_DIGITS_WHOSE_SUM_IS_13.AWK
BEGIN {
for (i=1; i<=1000000; i++) {
if (prime_digits_sum13(i)) {
printf("%6d ",i)
if (++count % 10 == 0) {
printf("\n")
}
}
}
printf("\n")
exit(0)
}
function prime_digits_sum13(n, r,sum) {
while (n > 0) {
r = int(n % 10)
switch (r) {
case 2:
case 3:
case 5:
case 7:
break
default:
return(0)
}
n = int(n / 10)
sum += r
}
return(sum == 13)
}
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
Generate digit combinations directly
BEGIN {
o = 1
src[o++] = 13
do {
r = src[++i]
n = src[++i]
for (p = 2; p != 9; p += p % 2 + 1) {
if (p >= r) {
if (p == r) res = res " " n p
break
}
src[++o] = r - p
src[++o] = n p
}
} while (i != o)
print substr(res, 2)
}
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
bc
q[0] = 13
o = 2
while (i != o) {
r = q[i++]
n = q[i++]
for (p = 2; p != 9; p += p % 2 + 1) {
if (p >= r) {
if (p == r) n + p
break
}
q[o++] = r - p
q[o++] = (n + p) * 10
}
}
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
C
Brute force
#include <stdbool.h>
#include <stdio.h>
bool primeDigitsSum13(int n) {
int sum = 0;
while (n > 0) {
int r = n % 10;
switch (r) {
case 2:
case 3:
case 5:
case 7:
break;
default:
return false;
}
n /= 10;
sum += r;
}
return sum == 13;
}
int main() {
int i, c;
// using 2 for all digits, 6 digits is the max prior to over-shooting 13
c = 0;
for (i = 1; i < 1000000; i++) {
if (primeDigitsSum13(i)) {
printf("%6d ", i);
if (c++ == 10) {
c = 0;
printf("\n");
}
}
}
printf("\n");
return 0;
}
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
C#
Same recursive method.
using System;
using static System.Console;
using LI = System.Collections.Generic.SortedSet<int>;
class Program {
static LI unl(LI res, LI set, int lft, int mul = 1, int vlu = 0) {
if (lft == 0) res.Add(vlu);
else if (lft > 0) foreach (int itm in set)
res = unl(res, set, lft - itm, mul * 10, vlu + itm * mul);
return res; }
static void Main(string[] args) { WriteLine(string.Join(" ",
unl(new LI {}, new LI { 2, 3, 5, 7 }, 13))); }
}
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
Alternate
Based in Nigel Galloway's suggestion from the discussion page.
class Program {
static void Main(string[] args) { int[] lst; int sum;
var w = new System.Collections.Generic.List<(int digs, int sum)> {};
foreach (int x in lst = new int[] { 2, 3, 5, 7 } ) w.Add((x, x));
while (w.Count > 0) { var i = w[0]; w.RemoveAt(0);
foreach (var j in lst) if ((sum = i.sum + j) == 13)
System.Console.Write ("{0}{1} ", i.digs, j);
else if (sum < 12)
w.Add((i.digs * 10 + j, sum)); } }
}
Same output.
C++
(the alternate version)
#include <cstdio>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<tuple<int, int>> w; int lst[4] = { 2, 3, 5, 7 }, sum;
for (int x : lst) w.push_back({x, x});
while (w.size() > 0) { auto i = w[0]; w.erase(w.begin());
for (int x : lst) if ((sum = get<1>(i) + x) == 13)
printf("%d%d ", get<0>(i), x);
else if (sum < 12) w.push_back({get<0>(i) * 10 + x, sum}); }
return 0; }
Same output as C#.
D
import std.stdio;
bool primeDigitsSum13(int n) {
int sum = 0;
while (n > 0) {
int r = n % 10;
switch (r) {
case 2,3,5,7:
break;
default:
return false;
}
n /= 10;
sum += r;
}
return sum == 13;
}
void main() {
// using 2 for all digits, 6 digits is the max prior to over-shooting 13
int c = 0;
for (int i = 1; i < 1_000_000; i++) {
if (primeDigitsSum13(i)) {
writef("%6d ", i);
if (c++ == 10) {
c = 0;
writeln;
}
}
}
writeln;
}
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
EasyLang
func digprimsum13 n .
while n > 0
d = n mod 10
if d < 2 or d = 4 or d = 6 or d >= 8
return 0
.
sum += d
n = n div 10
.
return if sum = 13
.
p = 2
while p <= 322222
if digprimsum13 p = 1
write p & " "
.
p += 1
.
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
F#
// prime digits whose sum is 13. Nigel Galloway: October 21st., 2020
let rec fN g=let g=[for n in [2;3;5;7] do for g in g->n::g]|>List.groupBy(fun n->match List.sum n with 13->'n' |n when n<12->'g' |_->'x')|>Map.ofSeq
[yield! (if g.ContainsKey 'n' then g.['n'] else []); yield! (if g.ContainsKey 'g' then fN g.['g'] else [])]
fN [[]] |> Seq.iter(fun n->n|>List.iter(printf "%d");printf " ");printfn ""
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
Factor
Filtering selections
Generate all selections of the prime digits in the only possible lengths whose sum can be 13, then filter for sums that equal 13.
USING: formatting io kernel math math.combinatorics
math.functions math.ranges sequences sequences.extras ;
: digits>number ( seq -- n ) reverse 0 [ 10^ * + ] reduce-index ;
"Numbers whose digits are prime and sum to 13:" print
{ 2 3 5 7 } 3 6 [a,b] [ selections [ sum 13 = ] filter ] with
map-concat [ digits>number ] map "%[%d, %]\n" printf
- Output:
Numbers whose digits are prime and sum to 13: { 337, 355, 373, 535, 553, 733, 2227, 2272, 2335, 2353, 2533, 2722, 3235, 3253, 3325, 3352, 3523, 3532, 5233, 5323, 5332, 7222, 22225, 22252, 22333, 22522, 23233, 23323, 23332, 25222, 32233, 32323, 32332, 33223, 33232, 33322, 52222, 222223, 222232, 222322, 223222, 232222, 322222 }
Delphi
function IsPrime(N: int64): boolean;
{Fast, optimised prime test}
var I,Stop: int64;
begin
if (N = 2) or (N=3) then Result:=true
else if (n <= 1) or ((n mod 2) = 0) or ((n mod 3) = 0) then Result:= false
else
begin
I:=5;
Stop:=Trunc(sqrt(N+0.0));
Result:=False;
while I<=Stop do
begin
if ((N mod I) = 0) or ((N mod (I + 2)) = 0) then exit;
Inc(I,6);
end;
Result:=True;
end;
end;
procedure GetDigits(N: integer; var IA: TIntegerDynArray);
{Get an array of the integers in a number}
var T: integer;
begin
SetLength(IA,0);
repeat
begin
T:=N mod 10;
N:=N div 10;
SetLength(IA,Length(IA)+1);
IA[High(IA)]:=T;
end
until N<1;
end;
function IsPrimeDigitSum13(N: integer): boolean;
{Return true N's digits are prime and total 13}
var IA: TIntegerDynArray;
var I,Sum: integer;
begin
Result:=False;
GetDigits(N,IA);
for I:=0 to High(IA) do
if not IsPrime(IA[I]) then exit;
Sum:=0;
for I:=0 to High(IA) do Sum:=Sum+IA[I];
Result:=Sum=13;
end;
procedure ShowPrimeDigitSum13(Memo: TMemo);
{Show numbers whose digits are prime and total 13}
var I,Cnt: integer;
var S: string;
begin
Cnt:=0;
for I:=1 to 999999 do
if IsPrimeDigitSum13(I) then
begin
Inc(Cnt);
S:=S+Format('%8D',[I]);
If (Cnt mod 5)=0 then S:=S+#$0D#$0A;
end;
Memo.Lines.Add(S);
end;
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222 Elapsed Time: 627.207 ms.
F# translation
The following is based on Nigel Galloway's algorithm as described here on the talk page. It's about 10x faster than the previous method.
USING: io kernel math prettyprint sequences sequences.extras ;
{ } { { 2 } { 3 } { 5 } { 7 } } [
{ 2 3 5 7 } [ suffix ] cartesian-map concat
[ sum 13 = ] partition [ append ] dip [ sum 11 > ] reject
] until-empty [ bl ] [ [ pprint ] each ] interleave nl
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
FreeBASIC
Ho hum. Another prime digits task.
function digit_is_prime( n as integer ) as boolean
select case n
case 2,3,5,7
return true
case else
return false
end select
end function
function all_digits_prime( n as uinteger ) as boolean
dim as string sn = str(n)
for i as uinteger = 1 to len(sn)
if not digit_is_prime( val(mid(sn,i,1)) ) then return false
next i
return true
end function
function digit_sum_13( n as uinteger ) as boolean
dim as string sn = str(n)
dim as integer k = 0
for i as uinteger = 1 to len(sn)
k = k + val(mid(sn,i,1))
if k>13 then return false
next i
if k<>13 then return false else return true
end function
for i as uinteger = 1 to 322222
if all_digits_prime(i) andalso digit_sum_13(i) then print i,
next i
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
Go
Reuses code from some other tasks.
package main
import (
"fmt"
"sort"
"strconv"
)
func combrep(n int, lst []byte) [][]byte {
if n == 0 {
return [][]byte{nil}
}
if len(lst) == 0 {
return nil
}
r := combrep(n, lst[1:])
for _, x := range combrep(n-1, lst) {
r = append(r, append(x, lst[0]))
}
return r
}
func shouldSwap(s []byte, start, curr int) bool {
for i := start; i < curr; i++ {
if s[i] == s[curr] {
return false
}
}
return true
}
func findPerms(s []byte, index, n int, res *[]string) {
if index >= n {
*res = append(*res, string(s))
return
}
for i := index; i < n; i++ {
check := shouldSwap(s, index, i)
if check {
s[index], s[i] = s[i], s[index]
findPerms(s, index+1, n, res)
s[index], s[i] = s[i], s[index]
}
}
}
func main() {
primes := []byte{2, 3, 5, 7}
var res []string
for n := 3; n <= 6; n++ {
reps := combrep(n, primes)
for _, rep := range reps {
sum := byte(0)
for _, r := range rep {
sum += r
}
if sum == 13 {
var perms []string
for i := 0; i < len(rep); i++ {
rep[i] += 48
}
findPerms(rep, 0, len(rep), &perms)
res = append(res, perms...)
}
}
}
res2 := make([]int, len(res))
for i, r := range res {
res2[i], _ = strconv.Atoi(r)
}
sort.Ints(res2)
fmt.Println("Those numbers whose digits are all prime and sum to 13 are:")
fmt.Println(res2)
}
- Output:
Those numbers whose digits are all prime and sum to 13 are: [337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222]
only counting
See Julia [1]
package main
import (
"fmt"
)
var
Primes = []byte{2, 3, 5, 7};
var
gblCount = 0;
var
PrimesIdx = []byte{0, 1, 2, 3};
func combrep(n int, lst []byte) [][]byte {
if n == 0 {
return [][]byte{nil}
}
if len(lst) == 0 {
return nil
}
r := combrep(n, lst[1:])
for _, x := range combrep(n-1, lst) {
r = append(r, append(x, lst[0]))
}
return r
}
func Count(rep []byte)int {
var PrimCount [4]int
for i := 0; i < len(PrimCount); i++ {
PrimCount[i] = 0;
}
//get the count of every item
for i := 0; i < len(rep); i++ {
PrimCount[rep[i]]++
}
var numfac int = len(rep)
var numerator,denominator[]int
for i := 1; i <= len(rep); i++ {
numerator = append(numerator,i) // factors 1,2,3,4. n
denominator = append(denominator,1)
}
numfac = 0; //idx in denominator
for i := 0; i < len(PrimCount); i++ {
denfac := 1;
for j := 0; j < PrimCount[i]; j++ {
denominator[numfac] = denfac
denfac++
numfac++
}
}
//calculate permutations with identical items
numfac = 1;
for i := 0; i < len(numerator); i++ {
numfac = (numfac * numerator[i])/denominator[i]
}
return numfac
}
func main() {
for mySum := 2; mySum <= 103;mySum++ {
gblCount = 0;
//check for prime
for i := 2; i*i <= mySum;i++{
if mySum%i == 0 {
gblCount=1;
break
}
}
if gblCount != 0 {
continue
}
for n := 1; n <= mySum / 2 ; n++ {
reps := combrep(n, PrimesIdx)
for _, rep := range reps {
sum := byte(0)
for _, r := range rep {
sum += Primes[r]
}
if sum == byte(mySum) {
gblCount+=Count(rep);
}
}
}
fmt.Println("The count of numbers whose digits are all prime and sum to",mySum,"is",gblCount)
}
}
- Output:
The count of numbers whose digits are all prime and sum to 2 is 1 The count of numbers whose digits are all prime and sum to 3 is 1 The count of numbers whose digits are all prime and sum to 5 is 3 The count of numbers whose digits are all prime and sum to 7 is 6 The count of numbers whose digits are all prime and sum to 11 is 19 The count of numbers whose digits are all prime and sum to 13 is 43 The count of numbers whose digits are all prime and sum to 17 is 221 The count of numbers whose digits are all prime and sum to 19 is 468 The count of numbers whose digits are all prime and sum to 23 is 2098 The count of numbers whose digits are all prime and sum to 29 is 21049 The count of numbers whose digits are all prime and sum to 31 is 45148 The count of numbers whose digits are all prime and sum to 37 is 446635 The count of numbers whose digits are all prime and sum to 41 is 2061697 The count of numbers whose digits are all prime and sum to 43 is 4427752 The count of numbers whose digits are all prime and sum to 47 is 20424241 The count of numbers whose digits are all prime and sum to 53 is 202405001 The count of numbers whose digits are all prime and sum to 59 is 2005642061 The count of numbers whose digits are all prime and sum to 61 is 4307930784 The count of numbers whose digits are all prime and sum to 67 is 42688517778 The count of numbers whose digits are all prime and sum to 71 is 196942068394 The count of numbers whose digits are all prime and sum to 73 is 423011795680 The count of numbers whose digits are all prime and sum to 79 is 4191737820642 The count of numbers whose digits are all prime and sum to 83 is 19338456915087 The count of numbers whose digits are all prime and sum to 89 is 191629965405641 The count of numbers whose digits are all prime and sum to 97 is 4078672831913824 The count of numbers whose digits are all prime and sum to 101 is 18816835854129198 The count of numbers whose digits are all prime and sum to 103 is 40416663565084464 real 0m4,489s user 0m5,584s sys 0m0,188s
Haskell
As an unfold, in the recursive pattern described by Nigel Galloway on the Talk page.
import Data.List.Split (chunksOf)
import Data.List (intercalate, transpose, unfoldr)
import Text.Printf
primeDigitsNumsSummingToN :: Int -> [Int]
primeDigitsNumsSummingToN n = concat $ unfoldr go (return <$> primeDigits)
where
primeDigits = [2, 3, 5, 7]
go :: [[Int]] -> Maybe ([Int], [[Int]])
go xs
| null xs = Nothing
| otherwise = Just (nextLength xs)
nextLength :: [[Int]] -> ([Int], [[Int]])
nextLength xs =
let harvest nv =
[ unDigits $ fst nv
| n == snd nv ]
prune nv =
[ fst nv
| pred n > snd nv ]
in ((,) . concatMap harvest <*> concatMap prune)
(((,) <*> sum) <$> ((<$> xs) . (<>) . return =<< primeDigits))
--------------------------- TEST -------------------------
main :: IO ()
main = do
let n = 13
xs = primeDigitsNumsSummingToN n
mapM_
putStrLn
[ concat
[ (show . length) xs
, " numbers with prime digits summing to "
, show n
, ":\n"
]
, table " " $ chunksOf 10 (show <$> xs)
]
table :: String -> [[String]] -> String
table gap rows =
let ic = intercalate
ws = maximum . fmap length <$> transpose rows
pw = printf . flip ic ["%", "s"] . show
in unlines $ ic gap . zipWith pw ws <$> rows
unDigits :: [Int] -> Int
unDigits = foldl ((+) . (10 *)) 0
- Output:
43 numbers with prime digits summing to 13: 337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
J
Galloway's algorithm, from the talk page:
ps13=: {{
seq=. 0#,D=. ,Q=. ":,.p:i.4
while. #Q do.
N=. ,/D,"0 1/Q
i=. +/"1"."0 N
Q=. (12>i)#N
seq=. seq,,".(13=i)#N
end.
}}0
Here, upper case names are character arrays representing digits, lower case names are numeric arrays.
Q
(number suffixes) and N
(candidate numbers) represent sequences of sequences of characters. (The top level sequence -- rows -- distinguishes different potential numbers and the secondary sequence -- columns -- distinguishes digits within potential numbers).
Meanwhile, D
(prime digits), i
(digit sums) and seq
(numbers whose digit sum is 13) are simple sequences.
ps13
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
Java
public class PrimeDigits {
private static boolean primeDigitsSum13(int n) {
int sum = 0;
while (n > 0) {
int r = n % 10;
if (r != 2 && r != 3 && r != 5 && r != 7) {
return false;
}
n /= 10;
sum += r;
}
return sum == 13;
}
public static void main(String[] args) {
// using 2 for all digits, 6 digits is the max prior to over-shooting 13
int c = 0;
for (int i = 1; i < 1_000_000; i++) {
if (primeDigitsSum13(i)) {
System.out.printf("%6d ", i);
if (c++ == 10) {
c = 0;
System.out.println();
}
}
}
System.out.println();
}
}
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
JavaScript
As an unfold, in the recursive pattern described by Nigel Galloway on the Talk page.
(() => {
'use strict';
// ---- NUMBERS WITH PRIME DIGITS WHOSE SUM IS 13 ----
// primeDigitsSummingToN :: Int -> [Int]
const primeDigitsSummingToN = n => {
const primeDigits = [2, 3, 5, 7];
const go = xs =>
fanArrow(
concatMap( // Harvested,
nv => n === nv[1] ? (
[unDigits(nv[0])]
) : []
)
)(
concatMap( // Pruned.
nv => pred(n) > nv[1] ? (
[nv[0]]
) : []
)
)(
// Existing numbers with prime digits appended,
// tupled with the resulting digit sums.
xs.flatMap(
ds => primeDigits.flatMap(d => [
fanArrow(identity)(sum)(
ds.concat(d)
)
])
)
);
return concat(
unfoldr(
xs => 0 < xs.length ? (
Just(go(xs))
) : Nothing()
)(
primeDigits.map(pureList)
)
);
}
// ---------------------- TEST -----------------------
// main :: IO ()
const main = () =>
chunksOf(6)(
primeDigitsSummingToN(13)
).forEach(
x => console.log(x)
)
// ---------------- GENERIC FUNCTIONS ----------------
// Just :: a -> Maybe a
const Just = x => ({
type: 'Maybe',
Nothing: false,
Just: x
});
// Nothing :: Maybe a
const Nothing = () => ({
type: 'Maybe',
Nothing: true,
});
// Tuple (,) :: a -> b -> (a, b)
const Tuple = a =>
b => ({
type: 'Tuple',
'0': a,
'1': b,
length: 2
});
// chunksOf :: Int -> [a] -> [[a]]
const chunksOf = n =>
xs => enumFromThenTo(0)(n)(
xs.length - 1
).reduce(
(a, i) => a.concat([xs.slice(i, (n + i))]),
[]
);
// concat :: [[a]] -> [a]
// concat :: [String] -> String
const concat = xs => (
ys => 0 < ys.length ? (
ys.every(Array.isArray) ? (
[]
) : ''
).concat(...ys) : ys
)(list(xs));
// concatMap :: (a -> [b]) -> [a] -> [b]
const concatMap = f =>
xs => xs.flatMap(f)
// enumFromThenTo :: Int -> Int -> Int -> [Int]
const enumFromThenTo = x1 =>
x2 => y => {
const d = x2 - x1;
return Array.from({
length: Math.floor(y - x2) / d + 2
}, (_, i) => x1 + (d * i));
};
// fanArrow (&&&) :: (a -> b) -> (a -> c) -> (a -> (b, c))
const fanArrow = f =>
// A function from x to a tuple of (f(x), g(x))
// ((,) . f <*> g)
g => x => Tuple(f(x))(
g(x)
);
// identity :: a -> a
const identity = x =>
// The identity function.
x;
// list :: StringOrArrayLike b => b -> [a]
const list = xs =>
// xs itself, if it is an Array,
// or an Array derived from xs.
Array.isArray(xs) ? (
xs
) : Array.from(xs || []);
// pred :: Enum a => a -> a
const pred = x =>
x - 1;
// pureList :: a -> [a]
const pureList = x => [x];
// sum :: [Num] -> Num
const sum = xs =>
// The numeric sum of all values in xs.
xs.reduce((a, x) => a + x, 0);
// unDigits :: [Int] -> Int
const unDigits = ds =>
// The integer with the given digits.
ds.reduce((a, x) => 10 * a + x, 0);
// The 'unfoldr' function is a *dual* to 'foldr':
// while 'foldr' reduces a list to a summary value,
// 'unfoldr' builds a list from a seed value.
// unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
const unfoldr = f =>
v => {
const xs = [];
let xr = [v, v];
while (true) {
const mb = f(xr[1]);
if (mb.Nothing) {
return xs;
} else {
xr = mb.Just;
xs.push(xr[0]);
}
}
};
return main();
})();
- Output:
337,355,373,535,553,733 2227,2272,2335,2353,2533,2722 3235,3253,3325,3352,3523,3532 5233,5323,5332,7222,22225,22252 22333,22522,23233,23323,23332,25222 32233,32323,32332,33223,33232,33322 52222,222223,222232,222322,223222,232222 322222
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.
All three solutions are based on the observation that the only decimal digits which are prime are [2, 3, 5, 7].
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);
Simple Generate-and-Test Solution
# Output: a stream
def simple:
range(2; 7) as $n
| [2, 3, 5, 7]
| combinations($n)
| select(add == 13)
| join("") | tonumber;
count(simple)
- Output:
43
A Faster Solution
def faster:
def digits: [2, 3, 5, 7];
def wide($max):
def d: digits[] | select(. <= $max);
if . == 1 then d | [.]
else d as $first
| (. - 1 | wide($max - $first)) as $next
| [$first] + $next
end;
range(2; 7)
| wide(13)
| select(add == 13)
| join("") | tonumber;
count(faster)
- Output:
43
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.
# 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)
- Output:
43 349321957098598244959032342621956
Julia
using Combinatorics, Primes
function primedigitsums(targetsum)
possibles = mapreduce(x -> fill(x, div(targetsum, x)), vcat, [2, 3, 5, 7])
a = map(x -> evalpoly(BigInt(10), x),
mapreduce(x -> unique(collect(permutations(x))), vcat,
unique(filter(x -> sum(x) == targetsum, collect(combinations(possibles))))))
println("There are $(length(a)) prime-digit-only numbers summing to $targetsum : $a")
end
foreach(primedigitsums, [5, 7, 11, 13])
function primedigitcombos(targetsum)
possibles = [2, 3, 5, 7]
found = Vector{Vector{Int}}()
combos = [Int[]]
tempcombos = Vector{Vector{Int}}()
newcombos = Vector{Vector{Int}}()
while !isempty(combos)
for combo in combos, j in possibles
csum = sum(combo) + j
if csum <= targetsum
newcombo = sort!([combo; j])
csum < targetsum && !(newcombo in newcombos) && push!(newcombos, newcombo)
csum == targetsum && !(newcombo in found) && push!(found, newcombo)
end
end
empty!(combos)
tempcombos = combos
combos = newcombos
newcombos = tempcombos
end
return found
end
function countprimedigitsums(targetsum)
found = primedigitcombos(targetsum)
total = sum(arr -> factorial(BigInt(length(arr))) ÷
prod(x -> factorial(BigInt(count(y -> y == x, arr))), unique(arr)), found)
println("There are $total prime-digit-only numbers summing to $targetsum.")
end
foreach(countprimedigitsums, nextprimes(17, 40))
- Output:
There are 3 prime-digit-only numbers summing to 5 : [5, 32, 23] There are 6 prime-digit-only numbers summing to 7 : [7, 52, 25, 322, 232, 223] There are 19 prime-digit-only numbers summing to 11 : [722, 272, 227, 533, 353, 335, 5222, 2522, 2252, 2225, 3332, 3323, 3233, 2333, 32222, 23222, 22322, 22232, 22223] There are 43 prime-digit-only numbers summing to 13 : [733, 373, 337, 553, 535, 355, 7222, 2722, 2272, 2227, 5332, 3532, 3352, 5323, 3523, 5233, 2533, 3253, 2353, 3325, 3235, 2335, 52222, 25222, 22522, 22252, 22225, 33322, 33232, 32332, 23332, 33223, 32323, 23323, 32233, 23233, 22333, 322222, 232222, 223222, 222322, 222232, 222223] There are 221 prime-digit-only numbers summing to 17. There are 468 prime-digit-only numbers summing to 19. There are 2098 prime-digit-only numbers summing to 23. There are 21049 prime-digit-only numbers summing to 29. There are 45148 prime-digit-only numbers summing to 31. There are 446635 prime-digit-only numbers summing to 37. There are 2061697 prime-digit-only numbers summing to 41. There are 4427752 prime-digit-only numbers summing to 43. There are 20424241 prime-digit-only numbers summing to 47. There are 202405001 prime-digit-only numbers summing to 53. There are 2005642061 prime-digit-only numbers summing to 59. There are 4307930784 prime-digit-only numbers summing to 61. There are 42688517778 prime-digit-only numbers summing to 67. There are 196942068394 prime-digit-only numbers summing to 71. There are 423011795680 prime-digit-only numbers summing to 73. There are 4191737820642 prime-digit-only numbers summing to 79. There are 19338456915087 prime-digit-only numbers summing to 83. There are 191629965405641 prime-digit-only numbers summing to 89. There are 4078672831913824 prime-digit-only numbers summing to 97. There are 18816835854129198 prime-digit-only numbers summing to 101. There are 40416663565084464 prime-digit-only numbers summing to 103. There are 186461075642340151 prime-digit-only numbers summing to 107. There are 400499564627237889 prime-digit-only numbers summing to 109. There are 1847692833654336940 prime-digit-only numbers summing to 113. There are 389696778451488128521 prime-digit-only numbers summing to 127. There are 1797854500757846669066 prime-digit-only numbers summing to 131. There are 17815422682488317051838 prime-digit-only numbers summing to 137. There are 38265729200380568226735 prime-digit-only numbers summing to 139. There are 1749360471151229472803187 prime-digit-only numbers summing to 149. There are 3757449669085729778349997 prime-digit-only numbers summing to 151. There are 37233577041224219717325533 prime-digit-only numbers summing to 157. There are 368957506121989278337474430 prime-digit-only numbers summing to 163. There are 1702174484494837917764813972 prime-digit-only numbers summing to 167. There are 16867303726643249517987636148 prime-digit-only numbers summing to 173. There are 167142638782573042636172836062 prime-digit-only numbers summing to 179. There are 359005512666242240589945886415 prime-digit-only numbers summing to 181. There are 16412337250779890525195727788488 prime-digit-only numbers summing to 191. There are 35252043354611887665339338710961 prime-digit-only numbers summing to 193. There are 162634253887997896351270835136345 prime-digit-only numbers summing to 197. There are 349321957098598244959032342621956 prime-digit-only numbers summing to 199.
Kotlin
fun primeDigitsSum13(n: Int): Boolean {
var nn = n
var sum = 0
while (nn > 0) {
val r = nn % 10
if (r != 2 && r != 3 && r != 5 && r != 7) {
return false
}
nn /= 10
sum += r
}
return sum == 13
}
fun main() {
// using 2 for all digits, 6 digits is the max prior to over-shooting 13
var c = 0
for (i in 1 until 1000000) {
if (primeDigitsSum13(i)) {
print("%6d ".format(i))
if (c++ == 10) {
c = 0
println()
}
}
}
println()
}
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
Lua
function prime_digits_sum_13(n)
local sum = 0
while n > 0 do
local r = n % 10
if r ~= 2 and r ~= 3 and r ~= 5 and r ~= 7 then
return false
end
n = math.floor(n / 10)
sum = sum + r
end
return sum == 13
end
local c = 0
for i=1,999999 do
if prime_digits_sum_13(i) then
io.write(string.format("%6d ", i))
if c == 10 then
c = 0
print()
else
c = c + 1
end
end
end
print()
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
Nim
import math, sequtils, strutils
type Digit = 0..9
proc toInt(s: seq[Digit]): int =
## Convert a sequence of digits to an integer.
for n in s:
result = 10 * result + n
const PrimeDigits = @[Digit 2, 3, 5, 7]
var list = PrimeDigits.mapIt(@[it]) # List of sequences of digits.
var result: seq[int]
while list.len != 0:
var nextList: seq[seq[Digit]] # List with one more digit.
for digitSeq in list:
let currSum = sum(digitSeq)
for n in PrimeDigits:
let newSum = currSum + n
let newDigitSeq = digitSeq & n
if newSum < 13: nextList.add newDigitSeq
elif newSum == 13: result.add newDigitSeq.toInt
else: break
list = move(nextList)
for i, n in result:
stdout.write ($n).align(6), if (i + 1) mod 9 == 0: '\n' else: ' '
echo()
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
OCaml
let prime_digits_13 =
let digits = [2; 3; 5; 7] in
let rec next ds ns = function
| [] -> if ns = [] then [] else next digits [] (List.rev ns)
| (n, r) :: cs' as cs ->
match ds with
| d :: ds' when d < r -> next ds' (((n + d) * 10, r - d) :: ns) cs
| d :: ds' when d = r -> n + d :: next digits ns cs'
| _ -> next digits ns cs'
in next digits [] [0, 13]
let () =
List.map string_of_int prime_digits_13 |> String.concat " " |> print_endline
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
Pascal
Only counting.
Extreme fast in finding the sum of primesdigits = value.
Limited by Uint64
program PrimSumUpTo13;
{$IFDEF FPC}
{$MODE DELPHI}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF}
uses
sysutils;
type
tDigits = array[0..3] of Uint32;
const
MAXNUM = 113;
var
gblPrimDgtCnt :tDigits;
gblCount: NativeUint;
function isPrime(n: NativeUint):boolean;
var
i : NativeUInt;
Begin
result := (n>1);
if n<4 then
EXIT;
result := false;
if n AND 1 = 0 then
EXIT;
i := 3;
while i*i<= n do
Begin
If n MOD i = 0 then
EXIT;
inc(i,2);
end;
result := true;
end;
procedure Sort(var t:tDigits);
var
i,j,k: NativeUint;
temp : Uint32;
Begin
For k := 0 to high(tdigits)-1 do
Begin
temp:= t[k];
j := k;
For i := k+1 to high(tdigits) do
Begin
if temp < t[i] then
Begin
temp := t[i];
j := i;
end;
end;
t[j] := t[k];
t[k] := temp;
end;
end;
function CalcPermCount:NativeUint;
//TempDgtCnt[0] = 3 and TempDgtCnt[1..3]= 2 -> dgtcnt = 3+3*2= 9
//permcount = dgtcnt! /(TempDgtCnt[0]!*TempDgtCnt[1]!*TempDgtCnt[2]!*TempDgtCnt[3]!);
//nom of n! = 1,2,3, 4,5, 6,7, 8,9
//denom = 1,2,3, 1,2, 1,2, 1,2
var
TempDgtCnt : tdigits;
i,f : NativeUint;
begin
TempDgtCnt := gblPrimDgtCnt;
Sort(TempDgtCnt);
//jump over 1/1*2/2*3/3*4/4*..* TempDgtCnt[0]/TempDgtCnt[0]
f := TempDgtCnt[0]+1;
result :=1;
For i := 1 to TempDgtCnt[1] do
Begin
result := (result*f) DIV i;
inc(f);
end;
For i := 1 to TempDgtCnt[2] do
Begin
result := (result*f) DIV i;
inc(f);
end;
For i := 1 to TempDgtCnt[3] do
Begin
result := (result*f) DIV i;
inc(f);
end;
end;
procedure check32(sum3 :NativeUint);
var
n3 : nativeInt;
begin
n3 := sum3 DIV 3;
gblPrimDgtCnt[1]:= 0;
while n3 >= 0 do
begin
//divisible by 2
if sum3 AND 1 = 0 then
Begin
gblPrimDgtCnt[0] := sum3 shr 1;
inc(gblCount,CalcPermCount);
sum3 -= 3;
inc(gblPrimDgtCnt[1]);
dec(n3);
end;
sum3 -= 3;
inc(gblPrimDgtCnt[1]);
dec(n3);
end;
end;
var
Num : NativeUint;
i,sum7,sum5: NativeInt;
BEGIN
writeln('Sum':6,'Count of arrangements':25);
Num := 1;
repeat
inc(num);
if Not(isPrime(Num)) then
CONTINUE;
gblCount := 0;
sum7 :=num;
gblPrimDgtCnt[3] := 0;
while sum7 >=0 do
Begin
sum5 := sum7;
gblPrimDgtCnt[2]:=0;
while sum5 >= 0 do
Begin
check32(sum5);
dec(sum5,5);
inc(gblPrimDgtCnt[2]);
end;
inc(gblPrimDgtCnt[3]);
dec(sum7,7);
end;
writeln(num:6,gblCount:25,' ');
until num > MAXNUM;
END.
- Output:
Sum Count of arrangements 2 1 3 1 5 3 7 6 11 19 13 43 17 221 19 468 23 2098 29 21049 31 45148 37 446635 41 2061697 43 4427752 47 20424241 53 202405001 59 2005642061 61 4307930784 67 42688517778 71 196942068394 73 423011795680 79 4191737820642 83 19338456915087 89 191629965405641 97 4078672831913824 101 18816835854129198 103 40416663565084464 107 186461075642340151 109 400499564627237889 113 1847692833654336940 real 0m0,003s
using gmp
program PrimSumUpTo13_GMP;
{$IFDEF FPC}
{$OPTIMIZATION ON,ALL}
{$MODE DELPHI}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF}
uses
sysutils,gmp;
type
tDigits = array[0..3] of Uint32;
const
MAXNUM = 199;//999
var
//split factors of n! in Uint64 groups
Fakul : array[0..MAXNUM] of UInt64;
IdxLimits : array[0..MAXNUM DIV 3] of word;
gblPrimDgtCnt :tDigits;
gblSum,
gbldelta : MPInteger; // multi precision (big) integers selve cleaning
s : AnsiString;
procedure Init;
var
i,j,tmp,n :NativeUint;
Begin
//generate n! by Uint64 factors
j := 1;
n := 0;
For i := 1 to MAXNUM do
begin
tmp := j;
j *= i;
if j div i <> tmp then
Begin
IdxLimits[n]:= i-1;
j := i;
inc(n);
end;
Fakul[i] := j;
end;
setlength(s,512);// 997 -> 166
z_init_set_ui(gblSum,0);
z_init_set_ui(gbldelta,0);
end;
function isPrime(n: NativeUint):boolean;
var
i : NativeUInt;
Begin
result := (n>1);
if n<4 then
EXIT;
result := false;
if n AND 1 = 0 then
EXIT;
i := 3;
while i*i<= n do
Begin
If n MOD i = 0 then
EXIT;
inc(i,2);
end;
result := true;
end;
procedure Sort(var t:tDigits);
// sorting descending to reduce calculations
var
i,j,k: NativeUint;
temp : Uint32;
Begin
For k := 0 to high(tdigits)-1 do
Begin
temp:= t[k];
j := k;
For i := k+1 to high(tdigits) do
Begin
if temp < t[i] then
Begin
temp := t[i];
j := i;
end;
end;
t[j] := t[k];
t[k] := temp;
end;
end;
function calcOne(f,n: NativeUint):NativeUint;
var
i,idx,MaxMulLmt : NativeUint;
Begin
result := f;
if n = 0 then
EXIT;
MaxMulLmt := High(MaxMulLmt) DIV (f+n);
z_mul_ui(gbldelta,gbldelta,result);
inc(result);
if n > 1 then
Begin
//multiply by parts of (f+n)!/f! with max Uint64 factors
i := 2;
while (i<=n) do
begin
idx := 1;
while (i<=n) AND (idx<MaxMulLmt) do
Begin
idx *= result;
inc(i);
inc(result);
end;
z_mul_ui(gbldelta,gbldelta,idx);
end;
//divide by n! with max Uint64 divisors
idx := 0;
if n > IdxLimits[idx] then
repeat
z_divexact_ui(gbldelta,gbldelta,Fakul[IdxLimits[idx]]);
inc(idx);
until IdxLimits[idx] >= n;
z_divexact_ui(gbldelta,gbldelta,Fakul[n]);
end;
end;
procedure CalcPermCount;
//TempDgtCnt[0] = 3 and TempDgtCnt[1..3]= 2 -> dgtcnt = 3+3*2= 9
//permcount = dgtcnt! /(TempDgtCnt[0]!*TempDgtCnt[1]!*TempDgtCnt[2]!*TempDgtCnt[3]!);
//nom of n! = 1,2,3, 4,5, 6,7, 8,9
//denom = 1,2,3, 1,2, 1,2, 1,2
var
TempDgtCnt : tdigits;
f : NativeUint;
begin
TempDgtCnt := gblPrimDgtCnt;
Sort(TempDgtCnt);
//jump over 1/1*2/2*3/3*4/4*..*
//res := 1;
f := TempDgtCnt[0]+1;
z_set_ui(gbldelta,1);
f := calcOne(f,TempDgtCnt[1]);
f := calcOne(f,TempDgtCnt[2]);
f := calcOne(f,TempDgtCnt[3]);
z_add(gblSum,gblSum,gblDelta);
end;
procedure check32(sum3 :NativeInt);
var
n3 : nativeInt;
begin
n3 := sum3 DIV 3;
gblPrimDgtCnt[1]:= 0;
while n3 >= 0 do
begin
//divisible by 2
if sum3 AND 1 = 0 then
Begin
gblPrimDgtCnt[0] := sum3 shr 1;
CalcPermCount;
end;
sum3 -= 3;
inc(gblPrimDgtCnt[1]);
dec(n3);
end;
end;
procedure CheckAll(num:NativeUint);
var
sum7,sum5: NativeInt;
BEGIN
z_set_ui(gblSum,0);
sum7 :=num;
gblPrimDgtCnt[3] := 0;
while sum7 >=0 do
Begin
sum5 := sum7;
gblPrimDgtCnt[2]:=0;
while sum5 >= 0 do
Begin
check32(sum5);
dec(sum5,5);
inc(gblPrimDgtCnt[2]);
end;
inc(gblPrimDgtCnt[3]);
dec(sum7,7);
end;
end;
var
T0 : Int64;
Num : NativeUint;
BEGIN
Init;
T0 := GettickCount64;
// Number crunching goes here
writeln('Sum':6,'Count of arrangements':25);
For num := 2 to MAXNUM do
IF isPrime(Num) then
Begin
CheckAll(num);
z_get_str(pChar(s),10,gblSum);
writeln(num:6,' ',pChar(s));
end;
writeln('Time taken : ',GettickCount64-T0,' ms');
z_clear(gblSum);
z_clear(gbldelta);
END.
- Output:
tio.run/#pascal-fpc Sum Count of arrangements 2 1 3 1 5 3 7 6 11 19 13 43 17 221 19 468 23 2098 29 21049 31 45148 37 446635 41 2061697 43 4427752 47 20424241 53 202405001 59 2005642061 61 4307930784 67 42688517778 71 196942068394 73 423011795680 79 4191737820642 83 19338456915087 89 191629965405641 97 4078672831913824 101 18816835854129198 103 40416663565084464 107 186461075642340151 109 400499564627237889 113 1847692833654336940 127 389696778451488128521 131 1797854500757846669066 137 17815422682488317051838 139 38265729200380568226735 149 1749360471151229472803187 151 3757449669085729778349997 157 37233577041224219717325533 163 368957506121989278337474430 167 1702174484494837917764813972 173 16867303726643249517987636148 179 167142638782573042636172836062 181 359005512666242240589945886415 191 16412337250779890525195727788488 193 35252043354611887665339338710961 197 162634253887997896351270835136345 199 349321957098598244959032342621956 Time taken : 23 ms
Perl
#!/usr/bin/perl
use strict;
use warnings;
my @queue = my @primedigits = ( 2, 3, 5, 7 );
my $numbers;
while( my $n = shift @queue )
{
if( eval $n == 13 )
{
$numbers .= $n =~ tr/+//dr . " ";
}
elsif( eval $n < 13 )
{
push @queue, map "$n+$_", @primedigits;
}
}
print $numbers =~ s/.{1,80}\K /\n/gr;
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
Phix
with javascript_semantics
function unlucky(sequence set, integer needed, string v="", sequence res={})
if needed=0 then
res = append(res,sprintf("%6s",v))
elsif needed>0 then
for i=length(set) to 1 by -1 do
res = unlucky(set,needed-set[i],(set[i]+'0')&v,res)
end for
end if
return res
end function
sequence r = sort(unlucky({2,3,5,7},13))
puts(1,join_by(r,1,11," "))
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
iterative
Queue-based version of Nigel's recursive algorithm, same output.
with javascript_semantics
requires("0.8.2") -- uses latest apply() mods, rest is fine
constant dgts = {2,3,5,7}
function unlucky()
sequence res = {}, q = {{0,0}}
integer s, -- partial digit sum, <=11
v -- corresponding value
while length(q) do
{{s,v}, q} = {q[1], q[2..$]}
for i=1 to length(dgts) do
integer d = dgts[i], {ns,nv} = {s+d,v*10+d}
if ns<=11 then q &= {{ns,nv}}
elsif ns=13 then res &= nv end if
end for
end while
return res
end function
sequence r = unlucky()
r = apply(true,sprintf,{{"%6d"},r})
puts(1,join_by(r,1,11," "))
I've archived a slightly more OTT version: Numbers_with_prime_digits_whose_sum_is_13/Phix.
Prolog
digit_sum(N, M) :- digit_sum(N, 0, M).
digit_sum(0, A, B) :- !, A = B.
digit_sum(N, A0, M) :-
divmod(N, 10, Q, R),
plus(A0, R, A1),
digit_sum(Q, A1, M).
prime_digits(0).
prime_digits(N) :-
prime_digits(M),
member(D, [2, 3, 5, 7]),
N is 10 * M + D.
prime13(N) :-
prime_digits(N),
(N > 333_333 -> !, false ; true),
digit_sum(N, 13).
main :-
findall(N, prime13(N), S),
format("Those numbers whose digits are all prime and sum to 13 are: ~n~w~n", [S]),
halt.
?- main.
- Output:
Those numbers whose digits are all prime and sum to 13 are: [337,355,373,535,553,733,2227,2272,2335,2353,2533,2722,3235,3253,3325,3352,3523,3532,5233,5323,5332,7222,22225,22252,22333,22522,23233,23323,23332,25222,32233,32323,32332,33223,33232,33322,52222,222223,222232,222322,223222,232222,322222]
Python
With improvements to the ideas from the discussion page:
from collections import deque
def prime_digits_sum(r):
q = deque([(r, 0)])
while q:
r, n = q.popleft()
for d in 2, 3, 5, 7:
if d >= r:
if d == r: yield n + d
break
q.append((r - d, (n + d) * 10))
print(*prime_digits_sum(13))
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
Quackery
[] ' [ [ ] ]
[ behead
' [ 2 3 5 7 ] witheach
[ dip dup join
0 over witheach +
dup 13 = iff
[ drop nested
dip rot join
unrot conclude ]
done
11 > iff drop done
nested swap dip join ]
drop dup [] = until ]
swap witheach
[ 0 swap witheach
[ swap 10 * + ]
number$ nested join ]
60 wrap$
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
Raku
put join ', ', sort +*, unique flat
< 2 2 2 2 2 3 3 3 5 5 7 >.combinations
.grep( *.sum == 13 )
.map( { .join => $_ } )
.map: { .value.permutations».join }
- Output:
337, 355, 373, 535, 553, 733, 2227, 2272, 2335, 2353, 2533, 2722, 3235, 3253, 3325, 3352, 3523, 3532, 5233, 5323, 5332, 7222, 22225, 22252, 22333, 22522, 23233, 23323, 23332, 25222, 32233, 32323, 32332, 33223, 33232, 33322, 52222, 222223, 222232, 222322, 223222, 232222, 322222
REXX
/*REXX pgm finds and displays all decimal numbers whose digits are prime and sum to 13. */
parse arg LO HI COLS . /*obtain optional arguments from the CL*/
if LO=='' | LO=="," then LO= 337 /*Not specified? Then use the default.*/
if HI=='' | HI=="," then HI= 322222 /* " " " " " " */
if cols=='' | cols=="," then cols= 10 /* " " " " " " */
w= 10 /*width of a number in any column. */
title= ' decimal numbers found whose digits are prime and sum to 13 '
say ' index │'center(title, 1 + cols*(w+1) )
say '───────┼'center("" , 1 + cols*(w+1), '─')
w= 10 /*max width of a integer in any column.*/
found= 0; idx= 1 /*the number of numbers found (so far).*/
$= /*variable to hold the list of #s found*/
do j=LO for HI-LO+1 /*search for numbers in this range. */
if verify(j, 2357) \== 0 then iterate /*J must be comprised of prime digits.*/
parse var j a 2 b 3 '' -1 z /*parse: 1st, 2nd, & last decimal digs.*/
sum= a + b + z /*sum: " " " " " " */
do k=3 for length(j)-3 /*only need to sum #s with #digits ≥ 4 */
sum= sum + substr(j, k, 1) /*sum some middle decimal digits of J.*/
end /*k*/
if sum\==13 then iterate /*Sum not equal to 13? Then skip this #*/
found= found + 1 /*bump the number of numbers found. */
c= commas(j) /*maybe add commas to the number. */
$= $ right( commas(j), w) /*add the found number ───► the $ list.*/
if found//cols\==0 then iterate /*have we populated a line of output? */
say center(idx, 7)'│' substr($, 2); $= /*display what we have so far (cols). */
idx= idx + cols /*bump the index count for the output*/
end /*j*/
if $\=='' then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/
say '───────┴'center("" , 1 + cols*(w+1), '─')
say
say 'Found ' commas(found) title
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg _; do jc=length(_)-3 to 1 by -3; _=insert(',', _, jc); end; return _
- output when using the internal default inputs:
index │ decimal numbers found whose digits are prime and sum to 13 ───────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────── 1 │ 337 355 373 535 553 733 2,227 2,272 2,335 2,353 11 │ 2,533 2,722 3,235 3,253 3,325 3,352 3,523 3,532 5,233 5,323 21 │ 5,332 7,222 22,225 22,252 22,333 22,522 23,233 23,323 23,332 25,222 31 │ 32,233 32,323 32,332 33,223 33,232 33,322 52,222 222,223 222,232 222,322 41 │ 223,222 232,222 322,222 ───────┴─────────────────────────────────────────────────────────────────────────────────────────────────────────────── Found 43 decimal numbers found whose digits are prime and sum to 13
Ring
load "stdlib.ring"
sum = 0
limit = 1000000
aPrimes = []
for n = 1 to limit
sum = 0
st = string(n)
for m = 1 to len(st)
num = number(st[m])
if isprime(num)
sum = sum + num
flag = 1
else
flag = 0
exit
ok
next
if flag = 1 and sum = 13
add(aPrimes,n)
ok
next
see "Unlucky numbers are:" + nl
see showArray(aPrimes)
func showarray vect
svect = ""
for n in vect
svect += "" + n + ","
next
? "[" + left(svect, len(svect) - 1) + "]"
- Output:
Unlucky numbers are: [337,355,373,535,553,733,2227,2272,2335,2353,2533,2722,3235,3253,3325,3352,3523,3532,5233,5323,5332,7222,22225,22252,22333,22522,23233,23323,23332,25222,32233,32323,32332,33223,33232,33322,52222,222223,222232,222322,223222,232222,322222]
RPL
Nice recursive solution from the discussion page:
« { } { "" } DO { } 1 PICK3 SIZE FOR j 2 7 FOR d OVER j GET d + 0 1 PICK3 SIZE FOR k OVER k DUP SUB STR→ + NEXT CASE DUP 13 == THEN DROP 4 ROLL SWAP + UNROT END 11 > THEN DROP END + END d 2 ≠ 1 + STEP @ generates 2 3 5 7 index sequence NEXT NIP UNTIL DUP SIZE NOT END DROP » 'TASK' STO
- Output:
1: { 337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222 }
Ruby
def primeDigitsSum13(n)
sum = 0
while n > 0
r = n % 10
if r != 2 and r != 3 and r != 5 and r != 7 then
return false
end
n = (n / 10).floor
sum = sum + r
end
return sum == 13
end
c = 0
for i in 1 .. 1000000
if primeDigitsSum13(i) then
print "%6d " % [i]
if c == 10 then
c = 0
print "\n"
else
c = c + 1
end
end
end
print "\n"
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
Sidef
func generate_from_prefix(sum, p, base, digits) {
var seq = [p]
for d in (digits) {
seq << __FUNC__(sum, [d, p...], base, digits)... if (p.sum+d <= sum)
}
return seq
}
func numbers_with_digitsum(sum, base = 10, digits = (base-1 -> primes)) {
digits.map {|p| generate_from_prefix(sum, [p], base, digits)... }\
.map {|t| digits2num(t, base) }\
.grep {|t| t.sumdigits(base) == sum }\
.sort
}
say numbers_with_digitsum(13)
- Output:
[337, 355, 373, 535, 553, 733, 2227, 2272, 2335, 2353, 2533, 2722, 3235, 3253, 3325, 3352, 3523, 3532, 5233, 5323, 5332, 7222, 22225, 22252, 22333, 22522, 23233, 23323, 23332, 25222, 32233, 32323, 32332, 33223, 33232, 33322, 52222, 222223, 222232, 222322, 223222, 232222, 322222]
Tcl
set res {}
set src [list {} 13]
while {[llength $src]} {
set src [lassign $src n r]
foreach d {2 3 5 7} {
if {$d >= $r} {
if {$d == $r} {lappend res "$n$d"}
break
}
lappend src "$n$d" [expr {$r - $d}]
}
}
puts $res
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
UNIX Shell
set -- '' 13
res=''
while [ $# -ne 0 ]
do
for d in 2 3 5 7
do
[ $d -ge $2 ] && {
[ $d -eq $2 ] && res=$res${res:+ }$1$d
break
}
set -- "$@" $1$d $(($2 - d))
done
shift 2
done
echo "$res"
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
Visual Basic .NET
Same recursive method.
Imports System
Imports System.Console
Imports LI = System.Collections.Generic.SortedSet(Of Integer)
Module Module1
Function unl(ByVal res As LI, ByVal lst As LI, ByVal lft As Integer, ByVal Optional mul As Integer = 1, ByVal Optional vlu As Integer = 0) As LI
If lft = 0 Then
res.Add(vlu)
ElseIf lft > 0 Then
For Each itm As Integer In lst
res = unl(res, lst, lft - itm, mul * 10, vlu + itm * mul)
Next
End If
Return res
End Function
Sub Main(ByVal args As String())
WriteLine(string.Join(" ",
unl(new LI From {}, new LI From { 2, 3, 5, 7 }, 13)))
End Sub
End Module
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222
Alternate
Thanks to Nigel Galloway's suggestion from the discussion page.
Imports Tu = System.Tuple(Of Integer, Integer)
Module Module1
Sub Main()
Dim w As New List(Of Tu), sum, x As Integer,
lst() As Integer = { 2, 3, 5, 7 }
For Each x In lst : w.Add(New Tu(x, x)) : Next
While w.Count > 0 : With w(0) : For Each j As Integer In lst
sum = .Item2 + j
If sum = 13 Then Console.Write("{0}{1} ", .Item1, j)
If sum < 12 Then w.Add(New Tu(.Item1 * 10 + j, sum))
Next : End With : w.RemoveAt(0) : End While
End Sub
End Module
Same output.
Wren
As the only digits which are prime are [2, 3, 5, 7], it is clear that a number must have between 3 and 6 digits for them to sum to 13.
import "./math" for Nums
import "./seq" for Lst
import "./sort" for Sort
var combrep // recursive
combrep = Fn.new { |n, lst|
if (n == 0 ) return [[]]
if (lst.count == 0) return []
var r = combrep.call(n, lst[1..-1])
for (x in combrep.call(n-1, lst)) {
var y = x.toList
y.add(lst[0])
r.add(y)
}
return r
}
var permute // recursive
permute = Fn.new { |input|
if (input.count == 1) return [input]
var perms = []
var toInsert = input[0]
for (perm in permute.call(input[1..-1])) {
for (i in 0..perm.count) {
var newPerm = perm.toList
newPerm.insert(i, toInsert)
perms.add(newPerm)
}
}
return perms
}
var primes = [2, 3, 5, 7]
var res = []
for (n in 3..6) {
var reps = combrep.call(n, primes)
for (rep in reps) {
if (Nums.sum(rep) == 13) {
var perms = permute.call(rep)
for (i in 0...perms.count) perms[i] = Num.fromString(perms[i].join())
res.addAll(Lst.distinct(perms))
}
}
}
Sort.quick(res)
System.print("Those numbers whose digits are all prime and sum to 13 are:")
System.print(res)
- Output:
Those numbers whose digits are all prime and sum to 13 are: [337, 355, 373, 535, 553, 733, 2227, 2272, 2335, 2353, 2533, 2722, 3235, 3253, 3325, 3352, 3523, 3532, 5233, 5323, 5332, 7222, 22225, 22252, 22333, 22522, 23233, 23323, 23332, 25222, 32233, 32323, 32332, 33223, 33232, 33322, 52222, 222223, 222232, 222322, 223222, 232222, 322222]
XPL0
int N, M, S, D;
[for N:= 2 to 322222 do
[M:= N; S:= 0;
repeat M:= M/10; \get digit D
D:= remainder(0);
case D of
2, 3, 5, 7:
[S:= S+D;
if S=13 and M=0 \all digits included\ then
[IntOut(0, N); ChOut(0, ^ )];
]
other M:= 0; \digit not prime so exit repeat loop
until M=0; \all digits in N tested or digit not prime
];
]
- Output:
337 355 373 535 553 733 2227 2272 2335 2353 2533 2722 3235 3253 3325 3352 3523 3532 5233 5323 5332 7222 22225 22252 22333 22522 23233 23323 23332 25222 32233 32323 32332 33223 33232 33322 52222 222223 222232 222322 223222 232222 322222