Primes whose sum of digits is 25
Show primes which sum of its decimal digits is 25
- Task
Find primes n such that n < 5000
- Stretch goal
Show the count of all such primes that do not contain any zeroes in the range:
- (997 ≤ n ≤ 1,111,111,111,111,111,111,111,111).
ALGOL 68
<lang algol68>BEGIN # find primes whose digits sum to 25 #
# returns a sieve of primes up to n # PROC eratosthenes = ( INT n )[]BOOL: BEGIN [ 1 : n ]BOOL p; p[ 1 ] := FALSE; p[ 2 ] := TRUE; FOR i FROM 3 BY 2 TO n DO p[ i ] := TRUE OD; FOR i FROM 4 BY 2 TO n DO p[ i ] := FALSE OD; FOR i FROM 3 BY 2 TO ENTIER sqrt( n ) DO IF p[ i ] THEN FOR c FROM i * i BY i + i TO n DO p[ c ] := FALSE OD FI OD; p END # eratosthenes # ; # show all sum25 primes below 5000 # INT max show sum25 = 4999; []BOOL prime = eratosthenes( max show sum25 ); INT p25 count := 0; FOR n TO max show sum25 DO IF prime[ n ] THEN # have a prime, check for a sum25 prime # INT digit sum := 0; INT v := n; WHILE v > 0 DO INT digit = v MOD 10; digit sum +:= digit; v OVERAB 10 OD; IF digit sum = 25 THEN print( ( " ", whole( n, 0 ) ) ); p25 count +:= 1 FI FI OD; print( ( newline, "Found ", whole( p25 count, 0 ), " sum25 primes below ", whole( max show sum25 + 1, 0 ), newline ) )
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
Stretch Goal
Uses the candidate generating algorithm used by Phix, Go
Uses the Miller Rabin primality test and the pow mod procedure from prelude/pow_mod
<lang algol68>BEGIN
PROC pow mod = (LONG LONG INT b,in e, modulus)LONG LONG INT: ( LONG LONG INT sq := b, e := in e; LONG LONG INT out:= IF ODD e THEN b ELSE 1 FI; e OVERAB 2; WHILE e /= 0 DO sq := sq * sq MOD modulus; IF ODD e THEN out := out * sq MOD modulus FI ; e OVERAB 2 OD; out ); INT p25 count := 0; PROC sum25 = ( LONG LONG INT p, INT rem )VOID: FOR i TO IF rem > 9 THEN 9 ELSE rem FI DO IF rem > i THEN sum25( ( p * 10 ) + i, rem - i ) ELIF ODD i AND i /= 5 THEN LONG LONG INT n = ( p * 10 ) + i; IF n MOD 3 /= 0 THEN BOOL is prime := TRUE; # miller rabin primality test # INT k = 10; LONG LONG INT d := n - 1; INT s := 0; WHILE NOT ODD d DO d OVERAB 2; s +:= 1 OD; TO k WHILE is prime DO LONG LONG INT a := 2 + ENTIER (random*(n-3)); LONG LONG INT x := pow mod(a, d, n); IF x /= 1 THEN BOOL done := FALSE; TO s WHILE NOT done DO IF x = n-1 THEN done := TRUE ELSE x := x * x MOD n FI OD; IF NOT done THEN IF x /= n-1 THEN is prime := FALSE FI FI FI OD; # END miller rabin primality test # IF is prime THEN # IF ( p25 count + 1 ) MOD 100 = 0 THEN print( ( whole( p25 count + 1, -8 ), whole( n, -30 ), newline ) ) FI; # p25 count +:= 1 FI FI FI OD; sum25( 0, 25 ); print( ( "There are ", whole( p25 count, 0 ), " sum25 primes that contain no zeroes", newline ) )
END</lang>
- Output:
Note that ALGOL 68G under Windows is fully interpreted so runtime is not of the same order as the Phix and Go samples, under Linux with optimisation and compilation. it may be faster.
There are 1525141 sum25 primes that contain no zeroes
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
AppleScript
Functional
Not fast. This approach takes over 20 seconds here. <lang applescript>use AppleScript version "2.4" use framework "Foundation" use scripting additions
PRIMES WITH DECIMAL DIGITS SUMMING TO 25 -------
-- primes :: [Int] on primes()
-- A non-finite list of primes. set ca to current application script property dict : ca's NSMutableDictionary's alloc's init() property n : 2 on |λ|() set xs to dict's objectForKey:(n as string) repeat until missing value = xs repeat with x in (xs as list) set m to x as number set k to (n + m) as string set ys to (dict's objectForKey:(k)) if missing value ≠ ys then set zs to ys else set zs to ca's NSMutableArray's alloc's init() end if (zs's addObject:(m)) (dict's setValue:(zs) forKey:(k)) (dict's removeObjectForKey:(n as string)) end repeat set n to 1 + n set xs to (dict's objectForKey:(n as string)) end repeat set p to n dict's setValue:({n}) forKey:((n * n) as string) set n to 1 + n set xs to missing value return p end |λ| end script
end primes
-- digitSum :: Int -> Int on digitSum(n)
-- Sum of the decimal digits of n. set m to 0 set cs to characters of (n as string) repeat with c in cs set m to m + ((id of c) - 48) end repeat
end digitSum
TEST -------------------------
on run
script q on |λ|(x) 5000 > x end |λ| end script script p on |λ|(n) 25 = digitSum(n) end |λ| end script set startTime to current date set xs to takeWhile(q, filterGen(p, primes())) set elapsedSeconds to ((current date) - startTime) as string showList(xs)
end run
GENERIC ------------------------
-- filterGen :: (a -> Bool) -> Gen [a] -> Gen [a] on filterGen(p, gen)
-- Non-finite stream of values which are -- drawn from gen, and satisfy p script property mp : mReturn(p)'s |λ| on |λ|() set v to gen's |λ|() repeat until mp(v) set v to gen's |λ|() end repeat return v end |λ| end script
end filterGen
-- intercalateS :: String -> [String] -> String
on intercalate(delim, xs)
set {dlm, my text item delimiters} to ¬ {my text item delimiters, delim} set s to xs as text set my text item delimiters to dlm s
end intercalate
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
-- The list obtained by applying f -- to each element of xs. tell mReturn(f) set lng to length of xs set lst to {} repeat with i from 1 to lng set end of lst to |λ|(item i of xs, i, xs) end repeat return lst end tell
end map
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
-- 2nd class handler function lifted into 1st class script wrapper. if script is class of f then f else script property |λ| : f end script end if
end mReturn
-- showList :: [a] -> String
on showList(xs)
"[" & intercalate(",", map(my str, xs)) & "]"
end showList
-- str :: a -> String
on str(x)
x as string
end str
-- takeWhile :: (a -> Bool) -> Gen [a] -> [a]
on takeWhile(p, xs)
set ys to {} set v to |λ|() of xs tell mReturn(p) repeat while (its |λ|(v)) set end of ys to v set v to xs's |λ|() end repeat end tell return ys
end takeWhile</lang>
- Output:
[997,1699,1789,1879,1987,2689,2797,2887,3499,3697,3769,3877,3967,4597,4759,4957,4993]
Idiomatic
Primes with silly properties are getting a bit tedious. But hey. This takes just under 0.02 seconds.
<lang applescript>on sieveOfEratosthenes(limit)
script o property numberList : {missing value} end script repeat with n from 2 to limit set end of o's numberList to n end repeat repeat with n from 2 to (limit ^ 0.5) div 1 if (item n of o's numberList is n) then repeat with multiple from n * n to limit by n set item multiple of o's numberList to missing value end repeat end if end repeat return o's numberList's numbers
end sieveOfEratosthenes
on sumOfDigits(n) -- n assumed to be a positive decimal integer.
set sum to n mod 10 set n to n div 10 repeat until (n = 0) set sum to sum + n mod 10 set n to n div 10 end repeat return sum
end sumOfDigits
on numbersWhoseDigitsSumTo(numList, targetSum)
script o property numberList : numList property output : {} end script repeat with n in o's numberList if (sumOfDigits(n) = targetSum) then set end of o's output to n's contents end repeat return o's output
end numbersWhoseDigitsSumTo
-- Task code: return numbersWhoseDigitsSumTo(sieveOfEratosthenes(4999), 25)</lang>
- Output:
<lang applescript>{997, 1699, 1789, 1879, 1987, 2689, 2797, 2887, 3499, 3697, 3769, 3877, 3967, 4597, 4759, 4957, 4993}</lang>
Arturo
<lang rebol>primes: select 1..5000 => prime?
loop split.every: 3 select primes 'p [25 = sum digits p] 'a ->
print map a => [pad to :string & 5]</lang>
- Output:
997 1699 1789 1879 1987 2689 2797 2887 3499 3697 3769 3877 3967 4597 4759 4957 4993
AWK
<lang AWK>
- syntax: GAWK -f PRIMES_WHICH_SUM_OF_DIGITS_IS_25.AWK
BEGIN {
start = 1 stop = 5000 for (i=start; i<=stop; i++) { if (is_prime(i)) { sum = 0 for (j=1; j<=length(i); j++) { sum += substr(i,j,1) } if (sum == 25) { printf("%d ",i) count++ } } } printf("\nPrime numbers %d-%d whose digits sum to 25: %d\n",start,stop,count) exit(0)
} function is_prime(x, i) {
if (x <= 1) { return(0) } for (i=2; i<=int(sqrt(x)); i++) { if (x % i == 0) { return(0) } } return(1)
} </lang>
- Output:
997 1699 1789 1879 1987 2689 2797 2887 3499 3697 3769 3877 3967 4597 4759 4957 4993 Prime numbers 1-5000 whose digits sum to 25: 17
BASIC
BASIC256
<lang BASIC256> function isprime(num) for i = 2 to int(sqr(num)) if (num mod i = 0) then return False next i return True end function
function digit_sum(num) sum25 = 0 for j = 1 to length(num) sum25 += int(mid(string(num),j,1)) next j return sum25 end function
inicio = 1: final = 5000 total = 0 for i = inicio to final if isprime(i) and (digit_sum(i) = 25) then total += 1 print i; " "; end if next i print chr(13) + chr(13) print "Se encontraron "; total; " primos sum25 por debajo de "; final end </lang>
- Output:
Igual que la entrada de FreeBASIC.
C
<lang c>#include <stdbool.h>
- include <stdio.h>
bool is_prime(int n) {
int i = 5;
if (n < 2) { return false; } if (n % 2 == 0) { return n == 2; } if (n % 3 == 0) { return n == 3; }
while (i * i <= n) { if (n % i == 0) { return false; } i += 2;
if (n % i == 0) { return false; } i += 4; }
return true;
}
int digit_sum(int n) {
int sum = 0; while (n > 0) { int rem = n % 10; n /= 10; sum += rem; } return sum;
}
int main() {
int n;
for (n = 2; n < 5000; n++) { if (is_prime(n) && digit_sum(n) == 25) { printf("%d ", n); } }
return 0;
}</lang>
- Output:
997 1699 1789 1879 1987 2689 2797 2887 3499 3697 3769 3877 3967 4597 4759 4957 4993
C++
Stretch goal solved the same way as Phix and Go. <lang cpp>#include <algorithm>
- include <chrono>
- include <iomanip>
- include <iostream>
- include <string>
- include <gmpxx.h>
bool is_probably_prime(const mpz_class& n) {
return mpz_probab_prime_p(n.get_mpz_t(), 3) != 0;
}
bool is_prime(int n) {
if (n < 2) return false; if (n % 2 == 0) return n == 2; if (n % 3 == 0) return n == 3; for (int p = 5; p * p <= n; p += 4) { if (n % p == 0) return false; p += 2; if (n % p == 0) return false; } return true;
}
int digit_sum(int n) {
int sum = 0; for (; n > 0; n /= 10) sum += n % 10; return sum;
}
int count_all(const std::string& str, int rem) {
int count = 0; if (rem == 0) { switch (str.back()) { case '1': case '3': case '7': case '9': if (is_probably_prime(mpz_class(str))) ++count; break; default: break; } } else { for (int i = 1; i <= std::min(9, rem); ++i) count += count_all(str + char('0' + i), rem - i); } return count;
}
int main() {
std::cout.imbue(std::locale("")); const int limit = 5000; std::cout << "Primes < " << limit << " whose digits sum to 25:\n"; int count = 0; for (int p = 1; p < limit; ++p) { if (digit_sum(p) == 25 && is_prime(p)) { ++count; std::cout << std::setw(6) << p << (count % 10 == 0 ? '\n' : ' '); } } std::cout << '\n';
auto start = std::chrono::steady_clock::now(); count = count_all("", 25); auto end = std::chrono::steady_clock::now(); std::cout << "\nThere are " << count << " primes whose digits sum to 25 and include no zeros.\n"; std::cout << "Time taken: " << std::chrono::duration<double>(end - start).count() << "s\n"; return 0;
}</lang>
- Output:
//https://tio.run/#cpp-gcc -lgmp -O3 Primes < 5,000 whose digits sum to 25: 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 There are 1,525,141 primes whose digits sum to 25 and include no zeros. Time taken: 10.6088s ..... Real time: 11.214 s User time: 11.075 s Sys. time: 0.082 s CPU share: 99.50 % Exit code: 0
D
<lang d>import std.bigint; import std.stdio;
bool isPrime(BigInt n) {
if (n < 2) { return false; }
if (n % 2 == 0) { return n == 2; } if (n % 3 == 0) { return n == 3; }
auto i = BigInt(5); while (i * i <= n) { if (n % i == 0){ return false; } i += 2;
if (n % i == 0){ return false; } i += 4; }
return true;
}
int digitSum(BigInt n) {
int result; while (n > 0) { result += n % 10; n /= 10; } return result;
}
void main() {
for (auto n = BigInt(2); n < 5_000; n++) { if (n.isPrime && n.digitSum == 25) { write(n, ' '); } } writeln;
}</lang>
- Output:
997 1699 1789 1879 1987 2689 2797 2887 3499 3697 3769 3877 3967 4597 4759 4957 4993
Delphi
<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
F#
<lang fsharp> // Primes to 5000 who's sum of digits is 25. Nigel Galloway: April 1st., 2021 let rec fN g=function n when n<10->n+g=25 |n->fN(g+n%10)(n/10) primes32()|>Seq.takeWhile((>)5000)|>Seq.filter fN|>Seq.iter(printf "%d "); printfn "" </lang>
- Output:
997 1699 1789 1879 1987 2689 2797 2887 3499 3697 3769 3877 3967 4597 4759 4957 4993
Factor
<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
Forth
<lang forth>: prime? ( n -- ? ) here + c@ 0= ;
- notprime! ( n -- ) here + 1 swap c! ;
- prime_sieve { n -- }
here n erase 0 notprime! 1 notprime! n 4 > if n 4 do i notprime! 2 +loop then 3 begin dup dup * n < while dup prime? if n over dup * do i notprime! dup 2* +loop then 2 + repeat drop ;
- digit_sum ( u -- u )
dup 10 < if exit then 10 /mod recurse + ;
- prime25? { p -- ? }
p prime? if p digit_sum 25 = else false then ;
- .prime25 { n -- }
." Primes < " n . ." whose digits sum to 25:" cr n prime_sieve 0 n 0 do i prime25? if i 5 .r 1+ dup 10 mod 0= if cr then then loop cr ." Count: " . cr ;
5000 .prime25 bye</lang>
- Output:
Primes < 5000 whose digits sum to 25: 997 1699 1789 1879 1987 2689 2797 2887 3499 3697 3769 3877 3967 4597 4759 4957 4993 Count: 17
FreeBASIC
<lang freebasic> Function isprime(num As Ulongint) As Boolean
For i As Integer = 2 To Sqr(num) If (num Mod i = 0) Then Return False Next i Return True
End Function
Function digit_sum(num As Integer) As Integer
Dim As Integer sum25 = 0 For j As Integer = 1 To Len(num) sum25 += Val(Mid(Str(num),j,1)) Next j Return sum25
End Function
Dim As Integer inicio = 1, final = 5000, total = 0 For i As Integer = inicio To final
If (isprime(i)) And (digit_sum(i) = 25) Then total += 1 Print Using " ####"; i; If (total Mod 9) = 0 Then Print End If
Next i Print !"\n\nSe encontraron"; total; " primos sum25 por debajo de"; finalSleep </lang>
- Output:
997 1699 1789 1879 1987 2689 2797 2887 3499 3697 3769 3877 3967 4597 4759 4957 4993 Se encontraron 17 primos sum25 por debajo de 5000
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
Haskell
<lang haskell>import Data.Bifunctor (second) import Data.List (replicate) import Data.List.Split (chunksOf) import Data.Numbers.Primes (primes)
PRIMES WITH DECIMAL DIGITS SUMMING TO 25 -------
matchingPrimes :: [Int] matchingPrimes =
takeWhile (< 5000) [n | n <- primes, 25 == decimalDigitSum n]
decimalDigitSum :: Int -> Int decimalDigitSum n =
snd $ until ((0 ==) . fst) (\(n, x) -> second (+ x) $ quotRem n 10) (n, 0)
TEST -------------------------
main :: IO () main = do
let w = length (show (last matchingPrimes)) mapM_ putStrLn $ ( show (length matchingPrimes) <> " primes (< 5000) with decimal digits totalling 25:\n" ) : ( unwords <$> chunksOf 4 (justifyRight w ' ' . show <$> matchingPrimes) )
justifyRight :: Int -> Char -> String -> String justifyRight n c = (drop . length) <*> (replicate n c <>)</lang>
- Output:
17 primes (< 5000) with decimal digits totalling 25: 997 1699 1789 1879 1987 2689 2797 2887 3499 3697 3769 3877 3967 4597 4759 4957 4993
Java
<lang java>import java.math.BigInteger;
public class PrimeSum {
private static int digitSum(BigInteger bi) { int sum = 0; while (bi.compareTo(BigInteger.ZERO) > 0) { BigInteger[] dr = bi.divideAndRemainder(BigInteger.TEN); sum += dr[1].intValue(); bi = dr[0]; } return sum; }
public static void main(String[] args) { BigInteger fiveK = BigInteger.valueOf(5_000); BigInteger bi = BigInteger.valueOf(2); while (bi.compareTo(fiveK) < 0) { if (digitSum(bi) == 25) { System.out.print(bi); System.out.print(" "); } bi = bi.nextProbablePrime(); } System.out.println(); }
}</lang>
- Output:
997 1699 1789 1879 1987 2689 2797 2887 3499 3697 3769 3877 3967 4597 4759 4957 4993
JavaScript
<lang javascript>(() => {
"use strict";
// ---- PRIMES WITH DECIMAL DIGITS SUMMING TO 25 -----
// digitSum :: Int -> Int const digitSum = n => `${n}`.split("").reduce( (a, c) => a + (c.codePointAt(0) - 48), 0 );
// primes :: [Int] const primes = function* () { // Non finite sequence of prime numbers. const dct = {}; let n = 2;
while (true) { if (n in dct) { dct[n].forEach(p => { const np = n + p;
dct[np] = (dct[np] || []).concat(p); delete dct[n]; }); } else { yield n; dct[n * n] = [n]; } n = 1 + n; } };
// ---------------------- TEST ----------------------- // main :: IO () const main = () => unlines( chunksOf(5)( takeWhileGen(n => 5000 > n)( filterGen(n => 25 === digitSum(n))( primes() ) ).map(str) ).map(unwords) );
// --------------------- GENERIC ---------------------
// chunksOf :: Int -> [a] -> a const chunksOf = n => { // xs split into sublists of length n. // The last sublist will be short if n // does not evenly divide the length of xs . const go = xs => { const chunk = xs.slice(0, n);
return 0 < chunk.length ? ( [chunk].concat( go(xs.slice(n)) ) ) : []; };
return go; };
// filterGen :: (a -> Bool) -> Gen [a] -> Gen [a] const filterGen = p => xs => { // Non-finite stream of values which are // drawn from gen, and satisfy p const go = function* () { let x = xs.next();
while (!x.done) { const v = x.value;
if (p(v)) { yield v; } x = xs.next(); } };
return go(xs); };
// str :: a -> String const str = x => x.toString();
// takeWhileGen :: (a -> Bool) -> Gen [a] -> [a] const takeWhileGen = p => // Values drawn from xs until p matches. xs => { const ys = []; let nxt = xs.next(), v = nxt.value;
while (!nxt.done && p(v)) { ys.push(v); nxt = xs.next(); v = nxt.value; }
return ys; };
// unlines :: [String] -> String const unlines = xs => // A single string formed by the intercalation // of a list of strings with the newline character. xs.join("\n");
// unwords :: [String] -> String const unwords = xs => // A space-separated string derived // from a list of words. xs.join(" ");
return main();
})();</lang>
997 1699 1789 1879 1987 2689 2797 2887 3499 3697 3769 3877 3967 4597 4759 4957 4993
Julia
<lang julia>using Primes
let
pmask, pcount = primesmask(1, 5000), 0 issum25prime(n) = pmask[n] && sum(digits(n)) == 25
println("Primes with digits summing to 25 between 0 and 5000:") for n in 1:4999 if issum25prime(n) pcount += 1 print(rpad(n, 5)) end end println("\nTotal found: $pcount")
end
</lang>
- Output:
Primes with digits summing to 25 between 0 and 5000: 997 1699 1789 1879 1987 2689 2797 2887 3499 3697 3769 3877 3967 4597 4759 4957 4993 Total found: 17
Stretch goal
<lang julia>using Primes, Formatting
function sum25(p::String, rm, res)
if rm == 0 if p[end] in "1379" && isprime(parse(Int128, p)) res += 1 end else for i in 1:min(rm, 9) res = sum25(p * string(i), rm - i, res) end end return res
end
@time println("There are ", format(sum25("", 25, 0), commas=true),
" primes whose digits sum to 25 without any zero digits.")
</lang>
- Output:
There are 1,525,141 primes whose digits sum to 25 without any zero digits. 29.377893 seconds (100.61 M allocations: 4.052 GiB, 0.55% gc time)
Kotlin
<lang scala>import java.math.BigInteger
fun digitSum(bi: BigInteger): Int {
var bi2 = bi var sum = 0 while (bi2 > BigInteger.ZERO) { val dr = bi2.divideAndRemainder(BigInteger.TEN) sum += dr[1].toInt() bi2 = dr[0] } return sum
}
fun main() {
val fiveK = BigInteger.valueOf(5_000)
var bi = BigInteger.valueOf(2) while (bi < fiveK) { if (digitSum(bi) == 25) { print(bi) print(" ") }
bi = bi.nextProbablePrime() } println()
}</lang>
- Output:
997 1699 1789 1879 1987 2689 2797 2887 3499 3697 3769 3877 3967 4597 4759 4957 4993
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
Nim
Task
<lang Nim>import strutils, sugar
func isPrime(n: Natural): bool =
if n < 2: return false if n mod 2 == 0: return n == 2 if n mod 3 == 0: return n == 3 var d = 5 while d * d <= n: if n mod d == 0: return false inc d, 2 if n mod d == 0: return false inc d, 4 result = true
func digitSum(n: Natural): int =
var n = n while n != 0: result += n mod 10 n = n div 10
let result = collect(newSeq):
for n in countup(3, 5000, 2): if digitSum(n) == 25 and n.isPrime: n
for i, n in result:
stdout.write ($n).align(4), if (i + 1) mod 6 == 0: '\n' else: ' '
echo()</lang>
- Output:
997 1699 1789 1879 1987 2689 2797 2887 3499 3697 3769 3877 3967 4597 4759 4957 4993
Stretch goal
<lang Nim>import std/monotimes, strformat, strutils import bignum
func sum25(p: string; rm, res: Natural): Natural =
result = res if rm == 0: if p[^1] in "1379" and probablyPrime(newInt(p), 25) != 0: inc result else: for i in 1..min(rm, 9): result = sum25(p & chr(i + ord('0')), rm - i, result)
let t0 = getMonoTime() let count = $sum25("", 25, 0) echo &"There are {count.insertSep()} primes whose digits sum to 25 without any zero digits." echo "\nExecution time: ", getMonoTime() - t0</lang>
- Output:
There are 1_525_141 primes whose digits sum to 25 without any zero digits. Execution time: (seconds: 12, nanosecond: 182051288)
Pascal
added only strechted goal.Generating the combination of the digits for the numbers and afterwards generating the Permutations with some identical elements
Now seting one digit out of 1,3,7,9 to the end and permute the rest of the digits in front.
So much less numbers have to be tested.10.5e6 instead of 16.4e6.Generating of the numbers is reduced in the same ratio.
<lang pascal>program Perm5aus8;
//formerly roborally take 5 cards out of 8
{$IFDEF FPC}
{$mode Delphi} {$Optimization ON,All}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF} uses
sysutils, gmp;
const
cTotalSum = 31;
cMaxCardsOnDeck = cTotalSum;//8 CMaxCardsUsed = cTotalSum;//5
type
tDeckIndex = 0..cMaxCardsOnDeck-1; tSequenceIndex = 0..CMaxCardsUsed-1;
tDiffCardCount = 0..9;
tSetElem = record Elem : tDiffCardCount; Elemcount : tDeckIndex; end;
tSet = record RemSet : array [low(tDiffCardCount)..High(tDiffCardCount)] of tSetElem; MaxUsedIdx, TotElemCnt : byte; end;
tRemainSet = array [low(tSequenceIndex)..High(tSequenceIndex)+1] of tSet;
tCardSequence = array [low(tSequenceIndex)..High(tSequenceIndex)] of tDiffCardCount;
var
ManifoldOfDigit : array[tDiffCardCount] of Byte; TotalUsedDigits : array[tDeckIndex] of Byte; RemainSets : tRemainSet;
CardString : AnsiString;
PrimeCount : integer; PermCount : integer;
//***************************************************************************** var
CS : pchar; z : mpz_t;
procedure SetInit(var ioSet:tSet); var
i : integer;
begin
with ioSet do begin MaxUsedIdx := 0; For i := Low(tDiffCardCount) to High(tDiffCardCount) do with RemSet[i] do begin ElemCount := 0; Elem := 0; end; end;
end;
procedure CheckPrime;inline; begin
mpz_set_str(z,CS,10); inc(PrimeCount,ORD(mpz_probab_prime_p(z,3)>0));
end;
procedure Permute(depth,MaxCardsUsed:NativeInt); var
pSetElem : ^tSetElem; i : NativeInt;
begin
i := 0; pSetElem := @RemainSets[depth].RemSet[i]; repeat if pSetElem^.Elemcount <> 0 then begin //take one of the same elements of the stack //insert in result here string CS[depth] := chr(pSetElem^.Elem+Ord('0')); //done one permutation IF depth = MaxCardsUsed then begin inc(permCount); CheckPrime; end else begin dec(pSetElem^.ElemCount); RemainSets[depth+1]:= RemainSets[depth]; Permute(depth+1,MaxCardsUsed); //re-insert that element inc(pSetElem^.ElemCount); end; end; //move on to the next digit inc(pSetElem); inc(i); until i >=RemainSets[depth].MaxUsedIdx;
end;
procedure Check(n:nativeInt); var
i,dgtCnt,cnt,dgtIdx : NativeInt;
Begin
SetInit(RemainSets[0]); dgtCnt := 0; dgtIdx := 0; //creating the start set. with RemainSets[0] do Begin For i in tDiffCardCount do Begin cnt := ManifoldOfDigit[i]; if cnt > 0 then Begin with RemSet[dgtIdx] do Begin Elemcount := cnt; Elem := i; end; inc(dgtCnt,cnt); inc(dgtIdx); end; end; TotElemCnt := dgtCnt; MaxUsedIdx := dgtIdx;
CS := @CardString[1]; //Check only useful end-digits For i := 0 to dgtIdx-1 do Begin if RemSet[i].Elem in[1,3,7,9]then Begin CS[dgtCnt-1] := chr(RemSet[i].Elem+Ord('0')); CS[dgtCnt] := #00;
dec(RemSet[i].ElemCount); permute(0,dgtCnt-2); inc(RemSet[i].ElemCount); end; end; end;
end;
procedure AppendToSum(n,dgt,remsum:NativeInt); var
i: NativeInt;
begin
inc(ManifoldOfDigit[dgt]); IF remsum > 0 then For i := dgt to 9 do AppendToSum(n+1,i,remsum-i) else Begin if remsum = 0 then Begin Check(n); //n is 0 based PrimeCount combinations of length n inc(TotalUsedDigits[n+1]); end; end; dec(ManifoldOfDigit[dgt]);
end;
procedure CheckAll(SumGoal:NativeInt); var
i :NativeInt;
begin
setlength(CardString,SumGoal); IF sumGoal>cTotalSum then EXIT; fillchar(ManifoldOfDigit[0],SizeOf(ManifoldOfDigit),#0); permcount:=0; PrimeCount := 0;
For i := 1 to 9 do AppendToSum(0,i,SumGoal-i);
writeln('PrimeCount of generated numbers with digits sum of ',SumGoal,' are ',permcount); writeln('Propably primes ',PrimeCount); writeln;
end; var
T1,T0 : Int64; SumGoal: NativeInt;
BEGIN
writeln('GMP-Version ',gmp.version); mpz_init_set_ui(z,0); T0 := GetTickCount64; For SumGoal := 25 to 25 do Begin CheckAll(SumGoal); T1 := GetTickCount64;Writeln((T1-T0)/1000:7:3,' s'); T0 := T1; end; mpz_clear(z);
END. </lang>
- Output:
//Runnning on TIO.RUN GMP-Version 6.1.2 PrimeCount of generated numbers with digits sum of 25 are 10488498 Propably primes 1525141 9.932 s .... Free Pascal Compiler version 3.0.4 [2018/07/13] for x86_64 Copyright (c) 1993-2017 by Florian Klaempfl and others Target OS: Linux for x86-64 Compiling .code.tio.pp Linking .bin.tio /usr/bin/ld: warning: link.res contains output sections; did you forget -T? 204 lines compiled, 0.2 sec Real time: 10.135 s User time: 10.027 s Sys. time: 0.052 s CPU share: 99.45 % Exit code: 0
Perl
<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
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})
- Output:
17 sum25 primes less than 5000 found: 997 1699 1789 1879 ... 4597 4759 4957 4993
Stretch goal
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)
- Output:
There are 1,525,141 sum25 primes that contain no zeroes "1 minute and 27s"
Python
<lang python>Primes with a decimal digit sum of 25
from itertools import takewhile
- primesWithGivenDigitSum :: Int -> Int -> [Int]
def primesWithGivenDigitSum(below, n):
Primes below a given value with decimal digits sums equal to n. return list( takewhile( lambda x: below > x, ( x for x in primes() if n == sum(int(c) for c in str(x)) ) ) )
- ------------------------- TEST -------------------------
- main :: IO ()
def main():
Test matches = primesWithGivenDigitSum(5000, 25) print( str(len(matches)) + ( ' primes below 5000 with a decimal digit sum of 25:\n' ) ) print( '\n'.join([ ' '.join([str(x).rjust(4, ' ') for x in xs]) for xs in chunksOf(4)(matches) ]) )
- ----------------------- GENERIC ------------------------
- chunksOf :: Int -> [a] -> a
def chunksOf(n):
A series of lists of length n, subdividing the contents of xs. Where the length of xs is not evenly divible, the final list will be shorter than n. def go(xs): return ( xs[i:n + i] for i in range(0, len(xs), n) ) if 0 < n else None return go
- primes :: [Int]
def primes():
Non-finite sequence of prime numbers. n = 2 dct = {} while True: if n in dct: for p in dct[n]: dct.setdefault(n + p, []).append(p) del dct[n] else: yield n dct[n * n] = [n] n = 1 + n
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
17 primes below 5000 with a decimal digit sum of 25: 997 1699 1789 1879 1987 2689 2797 2887 3499 3697 3769 3877 3967 4597 4759 4957 4993
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...
Tcl
Could be made prettier with the staple helper proc lfilter. <lang tcl>package require Tcl 8.5 package require math::numtheory namespace path ::tcl::mathop
puts [lmap x [math::numtheory::primesLowerThan 5000] {
if {[+ {*}[split $x {}]] == 25} {set x} else continue
}]</lang>
- Output:
997 1699 1789 1879 1987 2689 2797 2887 3499 3697 3769 3877 3967 4597 4759 4957 4993
Wren
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