Numbers with prime digits whose sum is 13
Find all the decimal numbers whose digits are all primes and sum to 13.
ALGOL W
Uses the observations about the digits and numbers in the Wren solution to generate the sequence. <lang algolw>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.</lang>
- 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. <lang csharp>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))); }
}</lang>
- 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#
<lang fsharp> // 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 "" </lang>
- 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
<lang factor>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</lang>
- 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 }
Go
Reuses code from some other tasks. <lang go>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)
}</lang>
- 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]
Julia
<lang 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))
</lang>
- 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.
Phix
<lang Phix>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," "))</lang>
- 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
I've archived a slightly more OTT version: Numbers_with_prime_digits_whose_sum_is_13/Phix.
Raku
<lang perl6>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 }</lang>
- 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
<lang rexx>/*REXX pgm finds and displays all decimal numbers whose digits are prime and sum to 13. */ LO= 337; HI= 322222 /*define the low and high range for #s.*/ pDigs= 2357; #= 0 /*define prime digits; found #s count.*/ $= /*variable to hold the list of #s found*/
do j=LO for HI-LO+1 /*search for numbers in this range. */ if verify(j, pDigs) \== 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 #*/ #= # + 1; $= $ j /*bump # count; append # to the $ list.*/ end /*j*/
say strip($); say /*display the output list to the term. */ say # ' decimal numbers found whose digits are prime and the decimal digits sum to 13'</lang>
- output when using the internal default inputs:
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 43 decimal numbers found whose digits are prime and the decimal digits sum to 13
Ring
<lang 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) + "]"
</lang>
- 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]
Visual Basic .NET
Same recursive method. <lang vbnet>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</lang>
- 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
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. <lang ecmascript>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)</lang>
- 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
<lang 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 ];
]</lang>
- 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