Extra primes
n is an extra prime if n is prime and its decimal digits and sum of digits are also primes.
- Definition
- Task
Show the extra primes under 10,000.
- Reference
OEIS:A062088 - Primes with every digit a prime and the sum of the digits a prime.
- Related tasks
AWK
<lang AWK>
- syntax: GAWK -f EXTRA_PRIMES.AWK
BEGIN {
for (i=1; i<10000; i++) { if (is_prime(i)) { sum = fail = 0 for (j=1; j<=length(i); j++) { sum += n = substr(i,j,1) if (!is_prime(n)) { fail = 1 break } } if (is_prime(sum) && fail == 0) { printf("%2d %4d\n",++count,i) } } } 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:
1 2 2 3 3 5 4 7 5 23 6 223 7 227 8 337 9 353 10 373 11 557 12 577 13 733 14 757 15 773 16 2333 17 2357 18 2377 19 2557 20 2753 21 2777 22 3253 23 3257 24 3323 25 3527 26 3727 27 5233 28 5237 29 5273 30 5323 31 5527 32 7237 33 7253 34 7523 35 7723 36 7727
C
<lang c>#include <locale.h>
- include <stdbool.h>
- include <stdio.h>
unsigned int next_prime_digit_number(unsigned int n) {
if (n == 0) return 2; switch (n % 10) { case 2: return n + 1; case 3: case 5: return n + 2; default: return 2 + next_prime_digit_number(n/10) * 10; }
}
bool is_prime(unsigned int n) {
if (n < 2) return false; if ((n & 1) == 0) return n == 2; if (n % 3 == 0) return n == 3; if (n % 5 == 0) return n == 5; static const unsigned int wheel[] = { 4,2,4,2,4,6,2,6 }; unsigned int p = 7; for (;;) { for (int w = 0; w < sizeof(wheel)/sizeof(wheel[0]); ++w) { if (p * p > n) return true; if (n % p == 0) return false; p += wheel[w]; } }
}
unsigned int digit_sum(unsigned int n) {
unsigned int sum = 0; for (; n > 0; n /= 10) sum += n % 10; return sum;
}
int main() {
setlocale(LC_ALL, ""); const unsigned int limit1 = 10000; const unsigned int limit2 = 1000000000; const int last = 10; unsigned int p = 0, n = 0; unsigned int extra_primes[last]; printf("Extra primes under %'u:\n", limit1); while (p < limit2) { p = next_prime_digit_number(p); if (is_prime(p) && is_prime(digit_sum(p))) { ++n; if (p < limit1) printf("%2u: %'u\n", n, p); extra_primes[n % last] = p; } } printf("\nLast %d extra primes under %'u:\n", last, limit2); for (int i = last - 1; i >= 0; --i) printf("%'u: %'u\n", n-i, extra_primes[(n-i) % last]); return 0;
}</lang>
- Output:
Extra primes under 10,000: 1: 2 2: 3 3: 5 4: 7 5: 23 6: 223 7: 227 8: 337 9: 353 10: 373 11: 557 12: 577 13: 733 14: 757 15: 773 16: 2,333 17: 2,357 18: 2,377 19: 2,557 20: 2,753 21: 2,777 22: 3,253 23: 3,257 24: 3,323 25: 3,527 26: 3,727 27: 5,233 28: 5,237 29: 5,273 30: 5,323 31: 5,527 32: 7,237 33: 7,253 34: 7,523 35: 7,723 36: 7,727 Last 10 extra primes under 1,000,000,000: 9,049: 777,753,773 9,050: 777,755,753 9,051: 777,773,333 9,052: 777,773,753 9,053: 777,775,373 9,054: 777,775,553 9,055: 777,775,577 9,056: 777,777,227 9,057: 777,777,577 9,058: 777,777,773
C++
<lang cpp>#include <iomanip>
- include <iostream>
unsigned int next_prime_digit_number(unsigned int n) {
if (n == 0) return 2; switch (n % 10) { case 2: return n + 1; case 3: case 5: return n + 2; default: return 2 + next_prime_digit_number(n/10) * 10; }
}
bool is_prime(unsigned int n) {
if (n < 2) return false; if ((n & 1) == 0) return n == 2; if (n % 3 == 0) return n == 3; if (n % 5 == 0) return n == 5; static constexpr unsigned int wheel[] = { 4,2,4,2,4,6,2,6 }; unsigned int p = 7; for (;;) { for (unsigned int w : wheel) { if (p * p > n) return true; if (n % p == 0) return false; p += w; } }
}
unsigned int digit_sum(unsigned int n) {
unsigned int sum = 0; for (; n > 0; n /= 10) sum += n % 10; return sum;
}
int main() {
std::cout.imbue(std::locale("")); const unsigned int limit1 = 10000; const unsigned int limit2 = 1000000000; const int last = 10; unsigned int p = 0, n = 0; unsigned int extra_primes[last]; std::cout << "Extra primes under " << limit1 << ":\n"; while (p < limit2) { p = next_prime_digit_number(p); if (is_prime(p) && is_prime(digit_sum(p))) { ++n; if (p < limit1) std::cout << std::setw(2) << n << ": " << p << '\n'; extra_primes[n % last] = p; } } std::cout << "\nLast " << last << " extra primes under " << limit2 << ":\n"; for (int i = last - 1; i >= 0; --i) std::cout << n-i << ": " << extra_primes[(n-i) % last] << '\n'; return 0;
}</lang>
- Output:
Extra primes under 10,000: 1: 2 2: 3 3: 5 4: 7 5: 23 6: 223 7: 227 8: 337 9: 353 10: 373 11: 557 12: 577 13: 733 14: 757 15: 773 16: 2,333 17: 2,357 18: 2,377 19: 2,557 20: 2,753 21: 2,777 22: 3,253 23: 3,257 24: 3,323 25: 3,527 26: 3,727 27: 5,233 28: 5,237 29: 5,273 30: 5,323 31: 5,527 32: 7,237 33: 7,253 34: 7,523 35: 7,723 36: 7,727 Last 10 extra primes under 1,000,000,000: 9,049: 777,753,773 9,050: 777,755,753 9,051: 777,773,333 9,052: 777,773,753 9,053: 777,775,373 9,054: 777,775,553 9,055: 777,775,577 9,056: 777,777,227 9,057: 777,777,577 9,058: 777,777,773
Factor
<lang factor>USING: formatting io kernel math math.functions math.primes sequences sequences.extras ;
- digit ( seq seq -- seq ) [ suffix ] cartesian-map concat ;
- front ( -- seq ) { { 2 } { 3 } { 5 } { 7 } } ;
- middle ( seq -- newseq ) { 2 3 5 7 } digit ;
- end ( seq -- newseq ) { 3 7 } digit ;
- candidates ( -- seq )
front front end front middle end front middle middle end append append append ;
- digits>number ( seq -- n )
<reversed> 0 [ 10^ * + ] reduce-index ;
"The extra primes with up to 4 digits are:" print candidates [ sum prime? ] filter [ digits>number ] [ prime? ] map-filter [ 1 + swap "%2d: %4d\n" printf ] each-index</lang>
- Output:
The extra primes with up to 4 digits are: 1: 2 2: 3 3: 5 4: 7 5: 23 6: 223 7: 227 8: 337 9: 353 10: 373 11: 557 12: 577 13: 733 14: 757 15: 773 16: 2333 17: 2357 18: 2377 19: 2557 20: 2753 21: 2777 22: 3253 23: 3257 24: 3323 25: 3527 26: 3727 27: 5233 28: 5237 29: 5273 30: 5323 31: 5527 32: 7237 33: 7253 34: 7523 35: 7723 36: 7727
FreeBASIC
<lang freebasic> dim as uinteger p(0 to 4) = {0,2,3,5,7}, d3, d2, d1, d0, pd1, pd2, pd3, pd0
function isprime( n as uinteger ) as boolean
if n mod 2 = 0 then return false for i as uinteger = 3 to int(sqr(n))+1 step 2 if n mod i = 0 then return false next i return true
end function
print "0002" 'special case for d3 = 0 to 4
pd3 = p(d3) for d2 = 0 to 4 if d3 > 0 and d2 = 0 then continue for pd2 = p(d2) for d1 = 0 to 4 if d2+d3 > 0 and d1 = 0 then continue for pd1 = p(d1) for d0 = 2 to 4 pd0 = p(d0) if isprime(pd0 + 10*pd1 + 100*pd2 + 1000*pd3 ) and isprime( pd0 + pd1 + pd2 + pd3) then print pd3;pd2;pd1;pd0 next d0 next d1 next d2
next d3</lang>
- Output:
0002 0003 0005 0007 0023 0223 0227 0337 0353 0373 0557 0577 0733 0757 0773 2333 2357 2377 2557 2753 2777 3253 3257 3323 3527 3727 5233 5237 5273 5323 5527 7237 7253 7523 7723 7727
Go
<lang go>package main
import "fmt"
func isPrime(n int) bool {
if n < 2 { return false } if n%2 == 0 { return n == 2 } if n%3 == 0 { return n == 3 } d := 5 for d*d <= n { if n%d == 0 { return false } d += 2 if n%d == 0 { return false } d += 4 } return true
}
func main() {
digits := [4]int{2, 3, 5, 7} // the only digits which are primes digits2 := [2]int{3, 7} // a prime > 5 can't end in 2 or 5 cands := [][2]int{{2, 2}, {3, 3}, {5, 5}, {7, 7}} // {number, digits sum}
for _, a := range digits { for _, b := range digits2 { cands = append(cands, [2]int{10*a + b, a + b}) } }
for _, a := range digits { for _, b := range digits { for _, c := range digits2 { cands = append(cands, [2]int{100*a + 10*b + c, a + b + c}) } } }
for _, a := range digits { for _, b := range digits { for _, c := range digits { for _, d := range digits2 { cands = append(cands, [2]int{1000*a + 100*b + 10*c + d, a + b + c + d}) } } } }
fmt.Println("The extra primes under 10,000 are:") count := 0 for _, cand := range cands { if isPrime(cand[0]) && isPrime(cand[1]) { count++ fmt.Printf("%2d: %4d\n", count, cand[0]) } }
}</lang>
- Output:
The extra primes under 10,000 are: 1: 2 2: 3 3: 5 4: 7 5: 23 6: 223 7: 227 8: 337 9: 353 10: 373 11: 557 12: 577 13: 733 14: 757 15: 773 16: 2333 17: 2357 18: 2377 19: 2557 20: 2753 21: 2777 22: 3253 23: 3257 24: 3323 25: 3527 26: 3727 27: 5233 28: 5237 29: 5273 30: 5323 31: 5527 32: 7237 33: 7253 34: 7523 35: 7723 36: 7727
Julia
<lang julia>using Primes
function extraprimes(maxlen)
for i in 1:maxlen, combo in Iterators.product([[2, 3, 5, 7] for _ in 1:i]...) if isprime(sum(combo)) n = evalpoly(10, combo) isprime(n) && println(n) end end
end
extraprimes(4)
</lang>
- Output:
2 3 5 7 23 223 227 337 353 373 557 577 733 757 773 2333 2357 2377 2557 2753 2777 3253 3257 3323 3527 3727 5233 5237 5273 5323 5527 7237 7253 7523 7723 7727
Phix
Minor reworking of Numbers_with_prime_digits_whose_sum_is_13#Phix#iterative <lang Phix>constant limit = 1_000_000_000, --constant limit = 10_000,
lim = limit/10-1, dgts = {2,3,5,7}
function extra_primes()
sequence res = {}, q = Template:0,0 integer s, -- partial digit sum v -- corresponding value while length(q) do {s,v} = q[1] q = q[2..$] for i=1 to length(dgts) do integer d = dgts[i], {ns,nv} = {s+d,v*10+d} if is_prime(ns) and is_prime(nv) then res &= nv end if if nv<lim then q &= Template:Ns,nv end if end for end while return res
end function
atom t0 = time() printf(1,"Extra primes < %,d:\n",{limit}) sequence res = extra_primes() integer ml = min(length(res),37) printf(1,"[1..%d]: %s\n",{ml,ppf(res[1..ml],{pp_Indent,9,pp_Maxlen,94})}) if length(res)>ml then
printf(1,"[991..1000]: %v\n",{res[991..1000]}) integer l = length(res) printf(1,"[%d..%d]: %v\n",{l-8,l,res[l-8..l]})
end if ?elapsed(time()-t0)</lang>
- Output:
Extra primes < 1,000,000,000: [1..37]: {2,3,5,7,23,223,227,337,353,373,557,577,733,757,773,2333,2357,2377,2557,2753,2777, 3253,3257,3323,3527,3727,5233,5237,5273,5323,5527,7237,7253,7523,7723,7727,22573} [991..1000]: {25337353,25353227,25353373,25353577,25355227,25355333,25355377,25357333,25357357,25357757} [9050..9058]: {777755753,777773333,777773753,777775373,777775553,777775577,777777227,777777577,777777773} "1.9s"
with the smaller limit in place:
Extra primes < 10,000: [1..36]: {2,3,5,7,23,223,227,337,353,373,557,577,733,757,773,2333,2357,2377,2557,2753,2777, 3253,3257,3323,3527,3727,5233,5237,5273,5323,5527,7237,7253,7523,7723,7727} "0.1s"
Raku
For the time being, (Doctor?), I'm going to assume that the task is really "Sequence of primes with every digit a prime and the sum of the digits a prime". Outputting my own take on a reasonable display of results, compact and easily doable but exercising it a bit.
<lang perl6>my @ppp = lazy flat 2, 3, 5, 7, 23, grep { .is-prime && .comb.sum.is-prime },
flat (2..*).map: { flat ([X~] (2, 3, 5, 7) xx $_) X~ (3, 7) };
put 'Terms < 10,000: '.fmt('%34s'), @ppp[^(@ppp.first: * > 1e4, :k)]; put '991st through 1000th: '.fmt('%34s'), @ppp[990 .. 999]; put 'Crossing 10th order of magnitude: ', @ppp[9055..9060];</lang>
- Output:
Terms < 10,000: 2 3 5 7 23 223 227 337 353 373 557 577 733 757 773 2333 2357 2377 2557 2753 2777 3253 3257 3323 3527 3727 5233 5237 5273 5323 5527 7237 7253 7523 7723 7727 991st through 1000th: 25337353 25353227 25353373 25353577 25355227 25355333 25355377 25357333 25357357 25357757 Crossing 10th order of magnitude: 777777227 777777577 777777773 2222222377 2222222573 2222225273
REXX
<lang rexx>/*REXX pgm finds & shows all primes whose digits are prime and the digits sum to a prime*/ parse arg HI . if HI== | HI=="," then HI= 10000 /*obtain optional argument from the CL.*/ y= 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 @.= 0; !.= @. /*initialize two stemmed arrays to zero*/
do k=1 for words(y); p= word(y, k) /*obtain a prime number from the list. */ @.k= p; !.p= 1 /*define a prime by it's index & value.*/ end /*k*/
- = 0
$= /*a list that holds "extra" primes. */
do j=1 while j<HI /*search for numbers in this range. */ if verify(j, 2357) \== 0 then iterate /*J must be comprised of prime digits.*/ s= left(j, 1) do k=2 to length(j) /*only need to sum #s with #digits ≥ 4 */ s= s + substr(j, k, 1) /*sum some middle decimal digits of J.*/ end /*k*/ if \!.s then iterate /*Is the sum not equal to prime? Skip.*/ do p=1 while @.p**2<=j /*perform division up to the sqrt of J.*/ if j//@.p==0 then iterate j /*J divisible by a prime? Then ¬ prime*/ end /*p*/ #= # + 1; $= $ j /*bump # count; append J to the $ list.*/ end /*j*/
say # ' primes found whose digits are prime and the digits sum to a prime' ,
"and which are less than " HI":"
say strip($) /*stick a fork in it, we're all done. */</lang>
- output when using the default input:
(Shown at three-quarter size.)
36 primes found whose digits are prime and the digits sum to a prime and which are less than 10000: 2 3 5 7 23 223 227 337 353 373 557 577 733 757 773 2333 2357 2377 2557 2753 2777 3253 3257 3323 3527 3727 5233 5237 5273 5323 5527 7237 7253 7523 7723 7727
Ring
<lang ring> load "stdlib.ring"
limit = 10000 num = 0 for n = 1 to limit
x1 = prime1(n) x2 = prime2(n) x3 = isprime(n) if x1 = 1 and x2 = 1 and x3 num = num + 1 see "The " + num + "th Extra Prime is: " + n + nl ok
next
func prime1(x)
pstr = string(x) len = len(pstr) count = 0 for n = 1 to len if isprime(number(pstr[n])) count = count + 1 ok next if count = len return 1 else return 0 ok
func prime2(x)
pstr = string(x) len = len(pstr) sum = 0 for n = 1 to len sum = sum + number(pstr[n]) next if isprime(sum) return 1 else return 0 ok
</lang> Output:
The 1th Extra Prime is: 2 The 2th Extra Prime is: 3 The 3th Extra Prime is: 5 The 4th Extra Prime is: 7 The 5th Extra Prime is: 23 The 6th Extra Prime is: 223 The 7th Extra Prime is: 227 The 8th Extra Prime is: 337 The 9th Extra Prime is: 353 The 10th Extra Prime is: 373 The 11th Extra Prime is: 557 The 12th Extra Prime is: 577 The 13th Extra Prime is: 733 The 14th Extra Prime is: 757 The 15th Extra Prime is: 773 The 16th Extra Prime is: 2333 The 17th Extra Prime is: 2357 The 18th Extra Prime is: 2377 The 19th Extra Prime is: 2557 The 20th Extra Prime is: 2753 The 21th Extra Prime is: 2777 The 22th Extra Prime is: 3253 The 23th Extra Prime is: 3257 The 24th Extra Prime is: 3323 The 25th Extra Prime is: 3527 The 26th Extra Prime is: 3727 The 27th Extra Prime is: 5233 The 28th Extra Prime is: 5237 The 29th Extra Prime is: 5273 The 30th Extra Prime is: 5323 The 31th Extra Prime is: 5527 The 32th Extra Prime is: 7237 The 33th Extra Prime is: 7253 The 34th Extra Prime is: 7523 The 35th Extra Prime is: 7723 The 36th Extra Prime is: 7727
Rust
<lang rust>// [dependencies] // primal = "0.3"
fn is_prime(n: u32) -> bool {
primal::is_prime(n as u64)
}
fn next_prime_digit_number(n: u32) -> u32 {
if n == 0 { return 2; } match n % 10 { 2 => n + 1, 3 | 5 => n + 2, _ => 2 + next_prime_digit_number(n / 10) * 10, }
}
fn digit_sum(mut n: u32) -> u32 {
let mut sum = 0; while n > 0 { sum += n % 10; n /= 10; } return sum;
}
fn main() {
let limit1 = 10000; let limit2 = 1000000000; let last = 10; let mut p = 0; let mut n = 0; let mut extra_primes = vec![0; last]; println!("Extra primes under {}:", limit1); while p < limit2 { p = next_prime_digit_number(p); if is_prime(p) && is_prime(digit_sum(p)) { n += 1; if p < limit1 { println!("{:2}: {}", n, p); } extra_primes[n % last] = p; } } println!("\nLast {} extra primes under {}:", last, limit2); let mut i = last; while i > 0 { i -= 1; println!("{}: {}", n - i, extra_primes[(n - i) % last]); }
}</lang>
- Output:
Extra primes under 10000: 1: 2 2: 3 3: 5 4: 7 5: 23 6: 223 7: 227 8: 337 9: 353 10: 373 11: 557 12: 577 13: 733 14: 757 15: 773 16: 2333 17: 2357 18: 2377 19: 2557 20: 2753 21: 2777 22: 3253 23: 3257 24: 3323 25: 3527 26: 3727 27: 5233 28: 5237 29: 5273 30: 5323 31: 5527 32: 7237 33: 7253 34: 7523 35: 7723 36: 7727 Last 10 extra primes under 1000000000: 9049: 777753773 9050: 777755753 9051: 777773333 9052: 777773753 9053: 777775373 9054: 777775553 9055: 777775577 9056: 777777227 9057: 777777577 9058: 777777773
Wren
<lang ecmascript>import "/math" for Int import "/fmt" for Fmt
var digits = [2, 3, 5, 7] // the only digits which are primes var digits2 = [3, 7] // a prime > 5 can't end in 2 or 5 var candidates = [[2, 2], [3, 3], [5, 5], [7, 7]] // [number, sum of its digits]
for (a in digits) {
for (b in digits2) candidates.add([10*a + b, a + b])
}
for (a in digits) {
for (b in digits) { for (c in digits2) candidates.add([100*a + 10*b + c, a + b + c]) }
}
for (a in digits) {
for (b in digits) { for (c in digits) { for (d in digits2) candidates.add([1000*a + 100*b + 10*c + d, a + b + c + d]) } }
}
System.print("The extra primes under 10,000 are:") var count = 0 for (cand in candidates) {
if (Int.isPrime(cand[0]) && Int.isPrime(cand[1])) { count = count + 1 Fmt.print("$2d: $4d", count, cand[0]) }
}</lang>
- Output:
The extra primes under 10,000 are: 1: 2 2: 3 3: 5 4: 7 5: 23 6: 223 7: 227 8: 337 9: 353 10: 373 11: 557 12: 577 13: 733 14: 757 15: 773 16: 2333 17: 2357 18: 2377 19: 2557 20: 2753 21: 2777 22: 3253 23: 3257 24: 3323 25: 3527 26: 3727 27: 5233 28: 5237 29: 5273 30: 5323 31: 5527 32: 7237 33: 7253 34: 7523 35: 7723 36: 7727
XPL0
<lang XPL0>func IsPrime(N); \Return 'true' if N is a prime number int N, I; [if N <= 1 then return false; for I:= 2 to sqrt(N) do
if rem(N/I) = 0 then return false;
return true; ];
int T, T2, N, M, I, S, D, P; [T:= [0, 2, 3, 5, 7]; \prime digits T2:= [1, 10, 100, 1000]; \10^I for N:= 1 to $7FFF_FFFF do
[M:= N; S:= 0; P:= 0; for I:= 0 to 3 do [M:= M/5; D:= T(rem(0)); S:= S+D; P:= P + D*T2(I); if M = 0 then I:= 3; if D = 0 then [S:= 0; I:=3]; ]; if P >= 7777 then exit; if IsPrime(S) then if IsPrime(P) then [IntOut(0, P); CrLf(0)]; ];
]</lang>
- Output:
2 3 5 7 23 223 227 337 353 373 557 577 733 757 773 2333 2357 2377 2557 2753 2777 3253 3257 3323 3527 3727 5233 5237 5273 5323 5527 7237 7253 7523 7723 7727