# Primes whose sum of digits is 25

Primes whose sum of digits is 25 is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Show primes which sum of its decimal digits is   25

Find primes     n     such that     0  <  n  <  5000

Stretch goal

Show the total number of all such primes that do not contain any zeroes (997 <= n <= 1,111,111,111,111,111,111,111,111).

## ALGOL W

<lang algolw>begin % find some primes whose digits sum to 25 %

```   % sets p( 1 :: n ) to a sieve of primes up to n %
procedure Eratosthenes ( logical array p( * ) ; integer value n ) ;
begin
p( 1 ) := false; p( 2 ) := true;
for i := 3 step 2 until n do p( i ) := true;
for i := 4 step 2 until n do p( i ) := false;
for i := 3 step 2 until truncate( sqrt( n ) ) do begin
integer ii; ii := i + i;
if p( i ) then for pr := i * i step ii until n do p( pr ) := false
end for_i ;
end Eratosthenes ;
integer MAX_NUMBER;
MAX_NUMBER := 4999;
begin
logical array prime( 1 :: MAX_NUMBER );
integer       pCount;
% sieve the primes to MAX_NUMBER %
Eratosthenes( prime, MAX_NUMBER );
% find the primes whose digits sum to 25 %
pCount := 0;
for i := 1 until MAX_NUMBER do begin
if prime( i ) then begin
integer dSum, v;
v    := i;
dSum := 0;
while v > 0 do begin
dSum := dSum + ( v rem 10 );
v    := v div 10
end while_v_gt_0 ;
if dSum = 25 then begin
writeon( i_w := 4, s_w := 0, " ", i );
pCount := pCount + 1;
if pCount rem 20 = 0 then write()
end if_prime_pReversed
end if_prime_i
end for_i ;
write( i_w := 1, s_w := 0, "Found ", pCount, " sum25 primes below ", MAX_NUMBER + 1 )
end
```

end.</lang>

Output:
```  997 1699 1789 1879 1987 2689 2797 2887 3499 3697 3769 3877 3967 4597 4759 4957 4993
Found 17 sum25 primes below 5000
```

## Delphi

Library: PrimTrial
Translation of: Ring

<lang Delphi> program Primes_which_sum_of_digits_is_25;

{\$APPTYPE CONSOLE}

uses

``` System.SysUtils,
PrimTrial;
```

var

``` row: Integer = 0;
limit1: Integer = 25;
limit2: Integer = 5000;
```

function Sum25(n: Integer): boolean; var

``` sum: Integer;
str: string;
c: char;
```

begin

``` sum := 0;
str := n.ToString;
for c in str do
inc(sum, strToInt(c));
Result := sum = limit1;
```

end;

begin

``` for var n := 1 to limit2-1 do
begin
if isPrime(n) and sum25(n) then
begin
inc(row);
write(n: 4, ' ');
if (row mod 5) = 0 then
writeln;
end;
end;
```

end.</lang>

Output:
``` 997 1699 1789 1879 1987
2689 2797 2887 3499 3697
3769 3877 3967 4597 4759
4957 4993```

## Go

This uses the Phix routine for the stretch goal though I've had to plug in a GMP wrapper to better the Phix time. Using Go's native big.Int, the time was slightly slower than Phix at 1 minute 28 seconds. <lang go>package main

import (

```   "fmt"
big "github.com/ncw/gmp"
"time"
```

)

// for small numbers func sieve(limit int) []bool {

```   limit++
// True denotes composite, false denotes prime.
c := make([]bool, limit) // all false by default
c[0] = true
c[1] = true
// no need to bother with even numbers over 2 for this task
p := 3 // Start from 3.
for {
p2 := p * p
if p2 >= limit {
break
}
for i := p2; i < limit; i += 2 * p {
c[i] = true
}
for {
p += 2
if !c[p] {
break
}
}
}
return c
```

}

func sumDigits(n int) int {

```   sum := 0
for n > 0 {
sum += n % 10
n /= 10
}
return sum
```

}

func min(a, b int) int {

```   if a < b {
return a
}
return b
```

}

// for big numbers func countAll(p string, rem, res int) int {

```   if rem == 0 {
b := p[len(p)-1]
if b == '1' || b == '3' || b == '7' || b == '9' {
z := new(big.Int)
z.SetString(p, 10)
if z.ProbablyPrime(1) {
res++
}
}
} else {
for i := 1; i <= min(9, rem); i++ {
res = countAll(p+fmt.Sprintf("%d", i), rem-i, res)
}
}
return res
```

}

func commatize(n int) string {

```   s := fmt.Sprintf("%d", n)
if n < 0 {
s = s[1:]
}
le := len(s)
for i := le - 3; i >= 1; i -= 3 {
s = s[0:i] + "," + s[i:]
}
if n >= 0 {
return s
}
return "-" + s
```

}

func main() {

```   start := time.Now()
c := sieve(4999)
var primes25 []int
for i := 997; i < 5000; i += 2 {
if !c[i] && sumDigits(i) == 25 {
primes25 = append(primes25, i)
}
}
fmt.Println("The", len(primes25), "primes under 5,000 whose digits sum to 25 are:")
fmt.Println(primes25)
n := countAll("", 25, 0)
fmt.Println("\nThere are", commatize(n), "primes whose digits sum to 25 and include no zeros.")
fmt.Printf("\nTook %s\n", time.Since(start))
```

}</lang>

Output:
```The 17 primes under 5,000 whose digits sum to 25 are:
[997 1699 1789 1879 1987 2689 2797 2887 3499 3697 3769 3877 3967 4597 4759 4957 4993]

There are 1,525,141 primes whose digits sum to 25 and include no zeros.

Took 25.300758564s
```

## Phix

<lang Phix>function sum25(integer p) return sum(sq_sub(sprint(p),'0'))=25 end function sequence res = filter(get_primes_le(5000),sum25) string r = join(shorten(apply(res,sprint),"",4)) printf(1,"%d sum25 primes less than 5000 found: %s\n",{length(res),r})</lang>

Output:
```17 sum25 primes less than 5000 found: 997 1699 1789 1879 ... 4597 4759 4957 4993
```

### Stretch goal

Library: Phix/mpfr

<lang Phix>include mpfr.e atom t0 = time(), t1 = time()+1 mpz pz = mpz_init(0)

function sum25(string p, integer rem, res=0)

```   if rem=0 then
if find(p[\$],"1379") then -- (saves 13s)
mpz_set_str(pz,p)
if mpz_prime(pz) then
res += 1
if time()>t1 then
progress("%d, %s...",{res,p})
t1 = time()+1
end if
end if
end if
else
for i=1 to min(rem,9) do
res = sum25(p&'0'+i,rem-i,res)
end for
end if
return res
```

end function

printf(1,"There are %,d sum25 primes that contain no zeroes\n",sum25("",25)) ?elapsed(time()-t0)</lang>

Output:
```There are 1,525,141 sum25 primes that contain no zeroes
"1 minute and 27s"
```

## Raku

<lang perl6>unit sub MAIN (\$limit = 5000); say "{+\$_} primes < \$limit with digital sum 25:\n{\$_».fmt("%" ~ \$limit.chars ~ "d").batch(10).join("\n")}",

```   with ^\$limit .grep: { .is-prime and .comb.sum == 25 }</lang>
```
Output:
```17 primes < 5000 with digital sum 25:
997 1699 1789 1879 1987 2689 2797 2887 3499 3697
3769 3877 3967 4597 4759 4957 4993```

## Ring

see "working..." + nl decimals(0) row = 0 num = 0 nr = 0 numsum25 = 0 limit1 = 25 limit2 = 5000

for n = 1 to limit2

```   if isprime(n)
bool = sum25(n)
if bool = 1
row = row + 1
see "" + n + " "
if (row%5) = 0
see nl
ok
ok
ok
```

next

see nl + "Found " + row + " sum25 primes below 5000" + nl

time1 = clock() see nl row = 0

while true

```     num = num + 1
str = string(num)
for m = 1 to len(str)
if str[m] = 0
loop
ok
next
if isprime(num)
bool = sum25(num)
if bool = 1
nr = num
numsum25 = numsum25 + 1
ok
ok
time2 = clock()
time3 = (time2-time1)/1000/60
if time3 > 30
exit
ok
```

end

see "There are " + numsum25 + " sum25 primes that contain no zeroes" + nl see "The last sum25 prime found during 30 mins is: " + nr + nl see "time = " + time3 + " mins" + nl see "done..." + nl

func sum25(n)

```    sum = 0
str = string(n)
for n = 1 to len(str)
sum = sum + number(str[n])
next
if sum = limit1
return 1
ok
```

</lang>

Output:
```working...
997 1699 1789 1879 1987
2689 2797 2887 3499 3697
3769 3877 3967 4597 4759
4957 4993
Found 17 sum25 primes below 5000

There are 1753 sum25 primes that contain no zeroes
The last sum25 prime found during 30 mins is: 230929
time = 30 mins
done...
```