Numbers with prime digits whose sum is 13
Find all the 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
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
function primedigitsums(targetsum)
possibles = mapreduce(x -> fill(x, div(targetsum, x)), vcat, [2, 3, 5, 7])
a = map(x -> evalpoly(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])
</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]
Phix
<lang Phix>function unlucky(sequence set, integer needed, atom mult=1, v=0, sequence res={})
if needed=0 then
res = append(res,v)
elsif needed>0 then
for i=length(set) to 1 by -1 do
res = unlucky(set,needed-set[i],mult*10,v+set[i]*mult,res)
end for
end if
return res
end function
for i=6 to 6 do -- (see below)
integer p = get_prime(i)
sequence r = sort(unlucky({2,3,5,7},p)),
s = shorten(r,"numbers",3)
integer l = length(s),
m = l<length(r) -- (ie shortened?)
for j=1 to l-m do
if s[j]!="..." then s[j] = sprintf("%d",s[j]) end if
end for
printf(1,"Prime_digit-only numbers summing to %d: %s\n",{p,join(s)})
end for</lang> Originally I thought I wouldn't need to sort the output of unlucky(), but it generates all numbers ending in 7 first, and alas (eg) 355 < 2227, not that it hurts any.
- Output:
Prime_digit-only numbers summing to 13: 337 355 373 ... 223222 232222 322222 (43 numbers)
With "for i=1 to 11" you get:
Prime_digit-only numbers summing to 2: 2 Prime_digit-only numbers summing to 3: 3 Prime_digit-only numbers summing to 5: 5 23 32 Prime_digit-only numbers summing to 7: 7 25 52 223 232 322 Prime_digit-only numbers summing to 11: 227 272 335 ... 22322 23222 32222 (19 numbers) Prime_digit-only numbers summing to 13: 337 355 373 ... 223222 232222 322222 (43 numbers) Prime_digit-only numbers summing to 17: 377 557 575 ... 22322222 23222222 32222222 (221 numbers) Prime_digit-only numbers summing to 19: 577 757 775 ... 223222222 232222222 322222222 (468 numbers) Prime_digit-only numbers summing to 23: 2777 7277 7727 ... 22322222222 23222222222 32222222222 (2,098 numbers) Prime_digit-only numbers summing to 29: 35777 37577 37757 ... 22322222222222 23222222222222 32222222222222 (21,049 numbers) Prime_digit-only numbers summing to 31: 37777 55777 57577 ... 223222222222222 232222222222222 322222222222222 (45,148 numbers)
Note that the largest sum-to-37, 322222222222222222, being as it is 18 digits long, exceeds the capacity of a 64-bit float.
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]
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 []
System.write("") // guard against VM recursion bug
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]
System.write("") // guard against VM recursion bug
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]