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.

Task

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: System.SysUtils

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;
 readln;

end.</lang>

Output:

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

Factor

Works with: Factor version 0.99 2021-02-05

<lang factor>USING: kernel lists lists.lazy math math.primes.lists prettyprint ;

digit-sum ( n -- sum )

   0 swap [ 10 /mod rot + swap ] until-zero ;

lprimes25 ( -- list ) lprimes [ digit-sum 25 = ] lfilter ;

lprimes25 [ 5,000 < ] lwhile [ . ] leach</lang>

Output:

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

Go

Library: GMP(Go wrapper)

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

Nanoquery

<lang Nanoquery>// find primes using the sieve of eratosthenes // https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Pseudocode def find_primes(upper_bound)

   a = {true} * (upper_bound + 1)
   for i in range(2, int(sqrt(upper_bound)))
       if a[i]
           for j in range(i ^ 2, upper_bound, i)
               a[j] = false
           end for
       end if
   end for

   primes = {}
   for i in range(2, len(a) - 1)
       if a[i]
           primes.append(i)
       end if
   end for
   return primes

end find_primes

def sum_digits(num)

   digits = str(num)
   digit_sum = 0

   for i in range(0, len(digits) - 1)
       digit_sum += int(digits[i])
   end for

   return digit_sum

end sum_digits

primes_to_check = find_primes(5000) for prime in primes_to_check

   if sum_digits(prime) = 25
       print prime + " "
   end if

end for println</lang>

Output:

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

Perl

Library: ntheory

<lang perl>use strict; use warnings; use feature 'say'; use List::Util 'sum'; use ntheory 'is_prime';

my($limit, @p25) = 5000; is_prime($_) and 25 == sum(split , $_) and push @p25, $_ for 1..$limit; say @p25 . " primes < $limit with digital sum 25:\n" . join ' ', @p25; </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

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

REXX

This REXX version allows the following to be specified on the command line:

•   the high number   (HI)
•   the number of columns shown per line   (COLS)
•   the target sum   (TARGET)

<lang rexx>/*REXX pgm finds and displays primes less than HI whose decimal digits sum to TARGET.*/ parse arg hi cols target . /*obtain optional argument from the CL.*/ if hi== | hi=="," then hi= 5000 /*Not specified? Then use the default.*/ if cols== | cols=="," then cols= 10 /* " " " " " " */ if target== | target=="," then target= 25 /* " " " " " " */ call genP /*build array of semaphores for primes.*/ w= 10 /*width of a number in any column. */

         @primes= ' primes that are  < '  commas(hi)  " and whose decimal digits sum to "

if cols>0 then say ' index │'center(@primes commas(target), 1 + cols*(w+1) ) if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─') primesT= 0; idx= 1 /*define # target primes found & index.*/ $= /*list of target primes found (so far).*/

    do j=1  for #;     y= @.j                   /*examine all the primes generated.    */
    if sumDigs(y)\==target  then iterate        /*Is sum≡target sum?  No, then skip it.*/
    primesT= primesT + 1                        /*bump the number of target primes.    */
    if cols==0              then iterate        /*Build the list  (to be shown later)? */
    c= commas(y)                                /*maybe add commas to the number.      */
    $= $ right(c, max(w, length(c) ) )          /*add a prime ──► list,  allow big #'s.*/
    if primesT//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 say 'Found ' commas(primesT) @primes commas(target) 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 ? /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: !.= 0 /*placeholders for primes' semaphores. */

     @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6=13 /*define some  low primes.             */
     !.2=1; !.3=1; !.5=1; !.7=1; !.11=1; @.13=1 /*   "     "   "   primes' semaphores. */
                          #= 6;    s.#= @.# **2 /*number of primes so far;     prime². */
                                                /* [↓]  generate more  primes  ≤  high.*/
       do j=@.#+2  by 2  to hi                  /*find odd primes from here on.        */
       parse var j  -1 _; if     _==5  then iterate  /*J divisible by  5? (right dig)*/
                            if j// 3==0  then iterate  /*"     "      "  3?            */
                            if j// 7==0  then iterate  /*"     "      "  7?            */
                            if j//11==0  then iterate  /*"     "      " 11?            */
              do k=6  while s.k<=j              /* [↓]  divide by the known odd primes.*/
              if j // @.k == 0  then iterate j  /*Is  J ÷ X?  Then not prime.     ___  */
              end   /*k*/                       /* [↑]  only process numbers  ≤  √ J   */
       #= #+1;    @.#= j;    s.#= j*j;   !.j= 1 /*bump # of Ps; assign next P;  P²; P# */
       end          /*j*/;   return

/*──────────────────────────────────────────────────────────────────────────────────────*/ sumDigs: parse arg x 1 s 2 -1 z; L= length(x); if L==1 then return s; s= s + z

                  do m=2  for L-2;   s= s + substr(x, m, 1);  end;  return s</lang>

output   when using the default inputs:

 index │                         primes that are  <  5,000  and whose decimal digits sum to  25
───────┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────
   1   │        997      1,699      1,789      1,879      1,987      2,689      2,797      2,887      3,499      3,697
  11   │      3,769      3,877      3,967      4,597      4,759      4,957      4,993

Found  17  primes that are  <  5,000  and whose decimal digits sum to  25

output   when using the input of:     1000000   0

Found  6,198  primes that are  <  1,000,000  and whose decimal digits sum to  25

Ring

<lang ring> load "stdlib.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 (during 30 mins)" + 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 (during 30 mins)
The last sum25 prime found during 30 mins is: 230929
time = 30 mins
done...

Wren

Library: Wren-math

Library: Wren-fmt

Library: Wren-seq

Although do-able, the stretch goal would take too long in Wren so I haven't bothered. <lang ecmascript>import "/math" for Int import "/fmt" for Fmt import "/seq" for Lst

var sumDigits = Fn.new { |n|

   var sum = 0
   while (n > 0) {
       sum = sum + (n % 10)
       n = (n/10).floor
   }
   return sum

}

var primes = Int.primeSieve(4999).where { |p| p >= 997 } var primes25 = [] for (p in primes) {

   if (sumDigits.call(p) == 25) primes25.add(p)

} System.print("The %(primes25.count) primes under 5,000 whose digits sum to 25 are:") for (chunk in Lst.chunks(primes25, 6)) Fmt.print("$,6d", chunk)</lang>

Output:

The 17 primes under 5,000 whose digits sum to 25 are:
   997  1,699  1,789  1,879  1,987  2,689
 2,797  2,887  3,499  3,697  3,769  3,877
 3,967  4,597  4,759  4,957  4,993