Extra primes: Difference between revisions
(Frink) |
|||
Line 1,119:
7723
7727</pre>
=={{header|Frink}}==
<lang frink>select[primes[2,10000], {|n| isPrime[n] and isPrime[sum[integerDigits[n]]] and isSubset[toSet[integerDigits[n]], new set[2,3,5,7]]}]</lang>
{{out}}
<pre>
[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]
</pre>
=={{header|Go}}==
|
Revision as of 04:06, 8 March 2022
- Definition
n is an extra prime if n is prime and its decimal digits and sum of digits are also primes.
- 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
11l
<lang 11l>V limit = 10'000
V is_prime = [0B] * 2 [+] [1B] * (limit - 1) L(n) 0 .< Int(limit ^ 0.5 + 1.5)
I is_prime[n] L(i) (n * n .< limit + 1).step(n) is_prime[i] = 0B
F is_extra_prime(n)
I !:is_prime[n] R 0B V s = 0 L(digit_char) String(n) V digit = Int(digit_char) I !:is_prime[digit] R 0B s += digit R Bool(:is_prime[s])
V i = 0 L(n) 0 .< limit
I is_extra_prime(n) i++ print(‘#4’.format(n), end' I i % 9 == 0 {"\n"} E ‘ ’)</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
Action!
<lang Action!>INCLUDE "H6:SIEVE.ACT"
BYTE Func IsExtraPrime(INT i BYTE ARRAY primes)
BYTE sum,d
IF primes(i)=0 THEN RETURN (0) FI
sum=0 WHILE i#0 DO d=i MOD 10 IF primes(d)=0 THEN RETURN (0) FI sum==+d i==/10 OD
RETURN (primes(sum))
PROC Main()
DEFINE MAX="9999" BYTE ARRAY primes(MAX+1) INT i,count=[0]
Put(125) PutE() Sieve(primes,MAX+1) FOR i=2 TO MAX DO IF IsExtraPrime(i,primes) THEN PrintI(i) Put(32) count==+1 FI OD PrintF("%E%EThere are %I extra primes",count)
RETURN</lang>
- Output:
Screenshot from Atari 8-bit computer
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 523 7 5273 5323 5527 7237 7253 7523 7723 7727 There are 36 extra primes
Ada
<lang Ada>with Ada.Text_Io;
procedure Extra_Primes is
type Number is new Long_Integer range 0 .. Long_Integer'Last;
package Number_Io is new Ada.Text_Io.Integer_Io (Number);
function Is_Prime (A : Number) return Boolean is D : Number; begin if A < 2 then return False; end if; if A in 2 .. 3 then return True; end if; if A mod 2 = 0 then return False; end if; if A mod 3 = 0 then return False; end if; D := 5; while D * D <= A loop if A mod D = 0 then return False; end if; D := D + 2; if A mod D = 0 then return False; end if; D := D + 4; end loop; return True; end Is_Prime;
subtype Digit is Number range 0 .. 9; type Digit_Array is array (Positive range <>) of Digit;
function To_Digits (N : Number) return Digit_Array is Image : constant String := Number'Image (N); Res : Digit_Array (2 .. Image'Last); begin for A in Image'First + 1 .. Image'Last loop Res (A) := Character'Pos (Image (A)) - Character'Pos ('0'); end loop; return Res; end To_Digits;
function All_Prime (Dig : Digit_Array) return Boolean is (for all D of Dig => Is_Prime (D));
function Sum_Of (Dig : Digit_Array) return Number is Sum : Number := 0; begin for D of Dig loop Sum := Sum + D; end loop; return Sum; end Sum_Of;
use Ada.Text_Io; Count : Natural := 0;
begin
for N in Number range 1 .. 9_999 loop if Is_Prime (N) then declare Dig : constant Digit_Array := To_Digits (N); begin if All_Prime (Dig) and Is_Prime (Sum_Of (Dig)) then Count := Count + 1; Number_Io.Put (N, Width => 4); Put (" "); if Count mod 8 = 0 then New_Line; end if; end if; end; end if; end loop; New_Line; Put_Line (Count'Image & " extra primes.");
end Extra_Primes;</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 36 extra primes.
ALGOL W
As the digits can only be 2, 3, 5 or 7 (see the Wren sample) we can easily generate the candidates for the sequence. <lang algolw>begin
% find extra primes - numbers whose digits are prime and whose % % digit sum is prime % % the digits can only be 2, 3, 5, 7 % % as we are looking for extra primes below 10 000, the maximum % % number to consider is 7 777, whose digit sum is 28 % integer MAX_PRIME; MAX_PRIME := 7777; begin logical array isPrime ( 1 :: MAX_PRIME ); integer numberCount; % sieve the primes up to MAX_PRIME % for i := 1 until MAX_PRIME do isPrime ( i ) := true; isPrime( 1 ) := false; for i := 2 until truncate( sqrt( MAX_PRIME ) ) do begin if isPrime ( i ) then for p := i * i step i until MAX_PRIME do isPrime( p ) := false end for_i ; % find the extra primes % 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 integer sum, n; n := 0; for d := d1, d2, d3, d4 do n := ( n * 10 ) + d; sum := d1 + d2 + d3 + d4; if isPrime( sum ) and isPrime( n ) then begin % found a prime whose prime % % digits sum to a prime % writeon( i_w := 5, s_w := 1, n ); numberCount := numberCount + 1; if numberCount rem 12 = 0 then write() end if_isPrime_sum 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
end.</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
APL
<lang APL>extraPrimes←{
pd←0 2 3 5 7 ds←↓⍉(∧⌿ds∊pd)/ds←10(⊥⍣¯1)1↓⍳⍵ ds←↑((∧/2(≤≥0=⊢)/⊢)¨ds)/ds ns←(ns≤⍵)/ns←10⊥⍉ds ss←+/(⍴ns)↑ds sieve←~(1+⌈/ns,ss){ r←1↓⍺⍴(⍺⌊⍵)↑1 ∨/r:(r∧⍵≠⍳⍺-1)∨⍺∇1+2*r⍳1 (⍺-1)/0 }2 (sieve[ns]∧sieve[ss])/ns
}</lang>
- Output:
<lang APL> extraPrimes 10000 2 3 5 7 23 27 223 227 333 337 353 373 377 533 553 557 577 733 737 757
773 777 2223 2227 2333 2353 2357 2377 2533 2537 2557 2573 2577 2737 2753 2757 2773 2777 3233 3253 3257 3277 3323 3523 3527 3727 5233 5237 5257 5273 5277 5323 5327 5527 5723 5727 7237 7253 7257 7273 7277 7327 7523 7527 7723 7727</lang>
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
BASIC
<lang basic>10 DEFINT A-Z: DIM S(7777),D(4): DATA 0,2,3,5,7 15 FOR I=0 TO 4: READ D(I): NEXT 20 FOR I=2 TO SQR(7777) 30 FOR J=I*I TO 7777 STEP I: S(J)=-1: NEXT 40 NEXT 50 FOR A=0 TO 4 60 FOR B=0 TO 4: IF A<>0 AND B=0 THEN 130 70 FOR C=0 TO 4: IF B<>0 AND C=0 THEN 120 80 FOR D=1 TO 4 90 I=D(A)*1000 + D(B)*100 + D(C)*10 + D(D) 95 S=D(A) + D(B) + D(C) + D(D) 100 IF NOT (S(S) OR S(I)) THEN PRINT I, 110 NEXT 120 NEXT 130 NEXT 140 NEXT</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
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 = next_prime_digit_number(p)) < limit2) { if (is_prime(digit_sum(p)) && is_prime(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 = next_prime_digit_number(p)) < limit2) { if (is_prime(digit_sum(p)) && is_prime(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
Cowgol
<lang cowgol>include "cowgol.coh"; const MAXPRIME := 7777;
var sieve: uint8[MAXPRIME+1]; MemZero(&sieve[0], @bytesof sieve); typedef Candidate is @indexof sieve; var cand: Candidate := 2; loop
var mark := cand * cand; if mark > MAXPRIME then break; end if; while mark <= MAXPRIME loop sieve[mark] := 1; mark := mark + cand; end loop; cand := cand + 1;
end loop;
var digits: Candidate[] := {0, 2, 3, 5, 7}; var i1: uint8; var i2: uint8; var i3: uint8; var i4: uint8; i1 := 0; while i1 < 5 loop
i2 := 0; while i2 < 5 loop if i1 == 0 or i2 != 0 then i3 := 0; while i3 < 5 loop if i2 == 0 or i3 != 0 then i4 := 1; while i4 < 5 loop cand := digits[i1] * 1000 + digits[i2] * 100 + digits[i3] * 10 + digits[i4]; var sum := digits[i1] + digits[i2] + digits[i3] + digits[i4]; if sieve[cand] | sieve[sum] == 0 then print_i32(cand as uint32); print_nl(); end if; i4 := i4 + 1; end loop; end if; i3 := i3 + 1; end loop; end if; i2 := i2 + 1; end loop; i1 := i1 + 1;
end loop;</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
D
<lang d>import std.stdio;
int nextPrimeDigitNumber(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 + nextPrimeDigitNumber(n / 10) * 10; }
}
bool isPrime(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; }
int p = 7; while (true) { foreach (w; [4, 2, 4, 2, 4, 6, 2, 6]) { if (p * p > n) { return true; } if (n % p == 0) { return false; } p += w; } }
}
int digitSum(int n) {
int sum = 0; for (; n > 0; n /= 10) { sum += n % 10; } return sum;
}
void main() {
immutable limit = 10_000; int p = 0; int n = 0;
writeln("Extra primes under ", limit); while (p < limit) { p = nextPrimeDigitNumber(p); if (isPrime(p) && isPrime(digitSum(p))) { n++; writefln("%2d: %d", n, p); } } writeln;
}</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
F#
The Function
This task uses Permutations/Derangements#F.23 <lang fsharp> // Extra Primes. Nigel Galloway: January 9th., 2021 let izXprime g=let rec fN n g=match n with 0L->isPrime64 g |_->if isPrime64(n%10L) then fN (n/10L) (n%10L+g) else false in fN g 0L </lang>
The tasks
- Extra primes below 10,000
<lang fsharp> primes64() |> Seq.filter izXprime |> Seq.takeWhile((>) 10000L) |> Seq.iteri(printfn "%3d->%d") </lang>
- Output:
0->2 1->3 2->5 3->7 4->23 5->223 6->227 7->337 8->353 9->373 10->557 11->577 12->733 13->757 14->773 15->2333 16->2357 17->2377 18->2557 19->2753 20->2777 21->3253 22->3257 23->3323 24->3527 25->3727 26->5233 27->5237 28->5273 29->5323 30->5527 31->7237 32->7253 33->7523 34->7723 35->7727
- Last 10 Extra primes below 1,000,000,000
<lang fsharp> primes64()|>Seq.takeWhile((>)1000000000L)|>Seq.rev|>Seq.filter izXprime|>Seq.take 10|>Seq.rev|>Seq.iter(printf "%d ");printfn "" </lang>
- Output:
777753773 777755753 777773333 777773753 777775373 777775553 777775577 777777227 777777577 777777773
- Last 10 Extra primes below 10,000,000,000
<lang fsharp> primes64()|>Seq.skipWhile((>)7770000000L)|>Seq.takeWhile((>)7777777777L)|>List.ofSeq|>List.filter izXprime|>List.rev|>List.take 10|>List.rev|>List.iter(printf "%d ");printfn "" </lang>
- Output:
7777733273 7777737727 7777752737 7777753253 7777772773 7777773257 7777773277 7777775273 7777777237 7777777327
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
Forth
<lang forth>: is_prime? ( n -- flag )
dup 2 < if drop false exit then dup 2 mod 0= if 2 = exit then dup 3 mod 0= if 3 = exit then 5 begin 2dup dup * >= while 2dup mod 0= if 2drop false exit then 2 + 2dup mod 0= if 2drop false exit then 4 + repeat 2drop true ;
- next_prime_digit_number ( n -- n )
dup 0= if drop 2 exit then dup 10 mod dup 2 = if drop 1+ exit then dup 3 = if drop 2 + exit then 5 = if 2 + exit then 10 / recurse 10 * 2 + ;
- digit_sum ( u -- u )
dup 10 < if exit then 10 /mod recurse + ;
- next_extra_prime ( n -- n )
begin next_prime_digit_number dup digit_sum is_prime? if dup is_prime? else false then until ;
- print_extra_primes ( n -- )
0 begin next_extra_prime 2dup > while dup . cr repeat 2drop ;
- count_extra_primes ( n -- n )
0 0 >r begin next_extra_prime 2dup > while r> 1+ >r repeat 2drop r> ;
." Extra primes under 10000:" cr 10000 print_extra_primes
100000000 count_extra_primes ." Number of extra primes under 100000000: " . cr
bye</lang>
- Output:
Extra primes under 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 Number of extra primes under 100000000: 2498
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
Frink
<lang frink>select[primes[2,10000], {|n| isPrime[n] and isPrime[sum[integerDigits[n]]] and isSubset[toSet[integerDigits[n]], new set[2,3,5,7]]}]</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]
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
J
<lang j>exprimes =: (] #~ *./@(1&p:)@(+/ , ])@(10 #.^:_1 ])"0)@(i.&.(p:^:_1))</lang>
- Output:
<lang j> exprimes 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</lang>
Java
<lang java>public class ExtraPrimes {
private static int nextPrimeDigitNumber(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 + nextPrimeDigitNumber(n / 10) * 10; } }
private static boolean isPrime(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; }
int[] wheel = new int[]{4, 2, 4, 2, 4, 6, 2, 6}; int p = 7; while (true) { for (int w : wheel) { if (p * p > n) { return true; } if (n % p == 0) { return false; } p += w; } } }
private static int digitSum(int n) { int sum = 0; for (; n > 0; n /= 10) { sum += n % 10; } return sum; }
public static void main(String[] args) { final int limit = 10_000; int p = 0, n = 0;
System.out.printf("Extra primes under %d:\n", limit); while (p < limit) { p = nextPrimeDigitNumber(p); if (isPrime(p) && isPrime(digitSum(p))) { n++; System.out.printf("%2d: %d\n", n, p); } } System.out.println(); }
}</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
jq
Works with gojq, the Go implementation of jq
For the definition of `is_prime` used here, see https://rosettacode.org/wiki/Additive_primes
One small point of interest is the declaration of $p before the inner function that references it. <lang jq>
- Input: the maximum width
- Output: a stream
def extraprimes:
[2,3,5,7] as $p # Input: width # Output: a stream of arrays of length $n drawn from $p | def wide: . as $n | if . == 0 then [] else $p[] | [.] + (($n-1)|wide) end;
range(1;.+1) as $maxlen | ($maxlen | wide) | select( add | is_prime) | join("") | tonumber | select(is_prime) ;
- The task:
4|extraprimes</lang>
- Output:
2 3 5 7 23 ... 7253 7523 7723 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
Kotlin
<lang scala>private fun nextPrimeDigitNumber(n: Int): Int {
return if (n == 0) { 2 } else when (n % 10) { 2 -> n + 1 3, 5 -> n + 2 else -> 2 + nextPrimeDigitNumber(n / 10) * 10 }
}
private fun isPrime(n: Int): Boolean {
if (n < 2) { return false } if (n and 1 == 0) { return n == 2 } if (n % 3 == 0) { return n == 3 } if (n % 5 == 0) { return n == 5 } val wheel = intArrayOf(4, 2, 4, 2, 4, 6, 2, 6) var p = 7 while (true) { for (w in wheel) { if (p * p > n) { return true } if (n % p == 0) { return false } p += w } }
}
private fun digitSum(n: Int): Int {
var nn = n var sum = 0 while (nn > 0) { sum += nn % 10 nn /= 10 } return sum
}
fun main() {
val limit = 10000 var p = 0 var n = 0 println("Extra primes under $limit:") while (p < limit) { p = nextPrimeDigitNumber(p) if (isPrime(p) && isPrime(digitSum(p))) { n++ println("%2d: %d".format(n, p)) } } println()
}</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
Lua
<lang lua>function next_prime_digit_number(n)
if n == 0 then return 2 end local r = n % 10 if r == 2 then return n + 1 end if r == 3 or r == 5 then return n + 2 end return 2 + next_prime_digit_number(math.floor(n / 10)) * 10
end
function is_prime(n)
if n < 2 then return false end
if n % 2 == 0 then return n == 2 end if n % 3 == 0 then return n == 3 end if n % 5 == 0 then return n == 5 end
local wheel = { 4, 2, 4, 2, 4, 6, 2, 6 } local p = 7 while true do for w = 1, #wheel do if p * p > n then return true end if n % p == 0 then return false end p = p + wheel[w] end end
end
function digit_sum(n)
local sum = 0 while n > 0 do sum = sum + n % 10 n = math.floor(n / 10) end return sum
end
local limit1 = 10000 local limit2 = 1000000000 local last = 10 local p = 0 local n = 0 local extra_primes = {}
print("Extra primes under " .. limit1 .. ":") while true do
p = next_prime_digit_number(p) if p >= limit2 then break end if is_prime(digit_sum(p)) and is_prime(p) then n = n + 1 if p < limit1 then print(string.format("%2d: %d", n, p)) end extra_primes[n % last] = p end
end
print(string.format("\nLast %d extra primes under %d:", last, limit2)) local i = last - 1 while i >= 0 do
print(string.format("%d: %d", n - i, extra_primes[(n - i) % last])) i = i - 1
end</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 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
MAD
<lang MAD> NORMAL MODE IS INTEGER
BOOLEAN PRIME DIMENSION PRIME(7777) VECTOR VALUES FMT = $I4*$ PRINT COMMENT $ EXTRA PRIMES UP TO 10000$ THROUGH SET, FOR P=1, 1, P.G.7777
SET PRIME(P) = 1B
THROUGH SIEVE, FOR P=2, 1, P*P.G.7777 THROUGH SIEVE, FOR C=P*P, P, C.G.7777
SIEVE PRIME(C) = 0B
THROUGH X, FOR VALUES OF A = 0,2,3,5,7 THROUGH X, FOR VALUES OF B = 0,2,3,5,7 WHENEVER A.NE.0 .AND. B.E.0, TRANSFER TO X THROUGH Y, FOR VALUES OF C = 0,2,3,5,7 WHENEVER B.NE.0 .AND. C.E.0, TRANSFER TO Y THROUGH Z, FOR VALUES OF D = 2,3,5,7 NUM = A*1000 + B*100 + C*10 + D SUM = A+B+C+D
Z WHENEVER PRIME(NUM) .AND. PRIME(SUM),
0 PRINT FORMAT FMT, NUM
Y CONTINUE X CONTINUE
END OF PROGRAM </lang>
- Output:
EXTRA PRIMES UP TO 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
Mathematica/Wolfram Language
<lang Mathematica>Select[Range[10000], PrimeQ[#] && AllTrue[IntegerDigits[#], PrimeQ] &]</lang>
- Output:
{2,3,5,7,23,37,53,73,223,227,233,257,277,337,353,373,523,557,577,727,733,757,773,2237,2273,2333,2357,2377,2557,2753,2777,3253,3257,3323,3373,3527,3533,3557,3727,3733,5227,5233,5237,5273,5323,5333,5527,5557,5573,5737,7237,7253,7333,7523,7537,7573,7577,7723,7727,7753,7757}
Nim
<lang Nim>import sequtils, strutils
const N = 10_000
func isPrime(n: Positive): bool =
if (n and 1) == 0: return n == 2 var m = 3 while m * m <= n: if n mod m == 0: return false inc m, 2 result = true
var primeList: seq[0..N] var primeSet: set[0..N]
for n in 2..N:
if n.isPrime: primeList.add n primeSet.incl n
type Digit = 0..9
proc digits(n: Positive): seq[Digit] =
var n = n.int while n != 0: result.add n mod 10 n = n div 10
proc isExtraPrime(prime: Positive): bool =
var sum = 0 for digit in prime.digits: if digit notin primeSet: return false inc sum, digit result = sum in primeSet
let result = primeList.filterIt(it.isExtraPrime) echo "Found $1 extra primes less than $2:".format(result.len, N) for i, p in result:
stdout.write ($p).align(4) stdout.write if (i + 1) mod 9 == 0: '\n' else: ' '</lang>
- Output:
Found 36 extra primes 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
Perl
<lang perl>use strict; use warnings; use feature 'say'; use ntheory qw(is_prime vecsum todigits forprimes);
my $str; forprimes {
is_prime(vecsum(todigits($_))) and /^[2357]+$/ and $str .= sprintf '%-5d', $_;
} 1e4; say $str =~ s/.{1,80}\K /\n/gr;</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
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 = {{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 &= {{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)
- 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"
Python
<lang python>from itertools import * from functools import reduce
class Sieve(object):
"""Sieve of Eratosthenes""" def __init__(self): self._primes = [] self._comps = {} self._max = 2; def isprime(self, n): """check if number is prime""" if n >= self._max: self._genprimes(n) return n >= 2 and n in self._primes def _genprimes(self, max): while self._max <= max: if self._max not in self._comps: self._primes.append(self._max) self._comps[self._max*self._max] = [self._max] else: for p in self._comps[self._max]: ps = self._comps.setdefault(self._max+p, []) ps.append(p) del self._comps[self._max] self._max += 1
def extra_primes():
"""Successively generate all extra primes.""" d = [2,3,5,7] s = Sieve() for cand in chain.from_iterable(product(d, repeat=r) for r in count(1)): num = reduce(lambda x, y: x*10+y, cand) if s.isprime(num) and s.isprime(sum(cand)): yield num
for n in takewhile(lambda n: n < 10000, extra_primes()):
print(n)
</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
Racket
<lang racket>#lang racket
(require math/number-theory)
(define (extra-prime? p)
(define (prime-sum-of-prime-digits? p (s 0)) (if (zero? p) (prime? s) (let-values (((q r) (quotient/remainder p 10))) (case r ((2 3 5 7) (prime-sum-of-prime-digits? q (+ s r))) (else #f))))) (and (prime? p) (prime-sum-of-prime-digits? p)))
(displayln (filter extra-prime? (range 10000)))</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)
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
Some optimization was done for the generation of primes, way more than was needed for this task's limit.
If the limit is negative, the list of primes found isn't shown, but the count of primes found is always shown. <lang rexx>/*REXX pgm finds & shows all primes whose digits are prime and the digits sum to a prime*/ parse arg hi . /*obtain optional argument from the CL.*/ if hi== | hi=="," then hi= 10000 /*Not specified? Then use the default.*/ list= hi>=0; hi= abs(hi) /*set a switch; use the absolute value*/ call genP /*invoke subroutine to generate primes.*/ xp= 1 /*number of extra primes found (so far)*/ $= 2 /*a list that holds "extra" primes. */
do j=3 by 2 for (hi-1)%2 /*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 for length(j)-1 /*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.*/ if j<=hP then do /*J may be small enough to see if prime*/ if \!.j then iterate /*is J a prime? No, then skip it. */ end /* _____ */ else do p=1 while @.p**2<=j /*perform division up to the √ J */ if j//@.p==0 then iterate j /*J divisible by a prime? Then ¬ prime*/ end /*p*/ xp= xp + 1 /*bump the count of primes found so far*/ if list then $= $ j /*maybe append extra prime ───► $ list.*/ end /*j*/
say commas(xp) ' primes found whose digits are prime and the digits sum to a prime' ,
"and which are less than " commas(hi)word(. ":", list + 1)
if list then say $ /*maybe display the list ───► terminal.*/ 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 ? /*──────────────────────────────────────────────────────────────────────────────────────*/ iSqrt: procedure; parse arg x; r= 0; q= 1; do while q<=x; q=q*4; end
do while q>1; q= q%4; _= x-r-q; r= r%2; if _>=0 then do; x= _; r= r+q; end end /*while*/; return r
/*──────────────────────────────────────────────────────────────────────────────────────*/ genP: @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6=13
!.=0; !.2=1; !.3=1; !.5=1; !.7=1; !.11=1; !.13=1 high= max(9 * digits(), iSqrt(hi) ) /*enough primes for sums & primality ÷ */ #= 6; sq.#= @.# ** 2 /*define # primes; define squared prime*/ do j=@.#+4 by 2 while #<=high /*continue on with the next odd prime. */ parse var j -1 _ /*obtain the last digit of the J var.*/ if _==5 then iterate; if j// 3==0 then iterate /*J ÷ by 5? J ÷ by 3?*/ if j//7==0 then iterate; if j//11==0 then iterate /*J ÷ by 7? J ÷ by 11?*/ /* [↓] divide by the primes. ___ */ do k=6 to # while sq.k<=j /*divide J by other primes ≤ √ J */ if j//@.k == 0 then iterate j /*÷ by prev. prime? ¬prime ___ */ end /*k*/ /* [↑] only divide up to √ J */ #=#+1; @.#= j; sq.#= j*j; !.j= 1 /*bump number of primes; assign prime#.*/ end /*j*/ hP= @.#; return # /*hP: is the highest prime generated. */</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 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
- output when using the input: -100000
89 primes found whose digits are prime and the digits sum to a prime and which are less than 100,000.
- output when using the input: -1000000
222 primes found whose digits are prime and the digits sum to a prime and which are less than 1,000,000.
- output when using the input: -10000000
718 primes found whose digits are prime and the digits sum to a prime and which are less than 10,000,000.
- output when using the input: -100000000
2,498 primes found whose digits are prime and the digits sum to a prime and which are less than 100,000,000.
- output when using the input: -1000000000
9,058 primes found whose digits are prime and the digits sum to a prime and which are less than 1,000,000,000.
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
Ruby
<lang ruby>def nextPrimeDigitNumber(n)
if n == 0 then return 2 end if n % 10 == 2 then return n + 1 end if n % 10 == 3 or n % 10 == 5 then return n + 2 end return 2 + nextPrimeDigitNumber((n / 10).floor) * 10
end
def isPrime(n)
if n < 2 then return false end if n % 2 == 0 then return n == 2 end if n % 3 == 0 then return n == 3 end if n % 5 == 0 then return n == 5 end
wheel = [4, 2, 4, 2, 4, 6, 2, 6] p = 7 loop do for w in wheel if p * p > n then return true end if n % p == 0 then return false end p = p + w end end
end
def digitSum(n)
sum = 0 while n > 0 sum = sum + n % 10 n = (n / 10).floor end return sum
end
LIMIT = 10000 p = 0 n = 0
print "Extra primes under %d:\n" % [LIMIT] while p < LIMIT
p = nextPrimeDigitNumber(p) if isPrime(p) and isPrime(digitSum(p)) then n = n + 1 print "%2d: %d\n" % [n, p] end
end print "\n"</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
Rust
<lang rust>// [dependencies] // primal = "0.3"
fn is_prime(n: u64) -> bool {
primal::is_prime(n)
}
fn next_prime_digit_number(n: u64) -> u64 {
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: u64) -> u64 {
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); loop { p = next_prime_digit_number(p); if p >= limit2 { break; } if is_prime(digit_sum(p)) && is_prime(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
Sidef
Simple solution: <lang ruby>say 1e4.primes.grep { .digits.all { .is_prime } && .sumdigits.is_prime }</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]
Generate such primes from digits (faster): <lang ruby>func extra_primes(upto, base = 10) {
upto = prev_prime(upto+1)
var list = [] var digits = @(^base)
var prime_digits = digits.grep { .is_prime } var end_digits = prime_digits.grep { .is_coprime(base) }
list << prime_digits.grep { !.is_coprime(base) }...
for k in (0 .. upto.ilog(base)) { prime_digits.variations_with_repetition(k, {|*a| next if ([end_digits[0], a...].digits2num(base) > upto) end_digits.each {|d| var n = [d, a...].digits2num(base) list << n if (n.is_prime && n.sumdigits(base).is_prime) } }) }
list.sort
}
with (1e4) { |n|
say "Extra primes <= #{n.commify}:" say extra_primes(n).join(' ')
}
with (1000000000) {|n|
say "\nLast 10 extra primes <= #{n.commify}:" say extra_primes(n).last(10).join(' ')
}</lang>
- Output:
Extra primes <= 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 Last 10 extra primes <= 1,000,000,000: 777753773 777755753 777773333 777773753 777775373 777775553 777775577 777777227 777777577 777777773
Swift
<lang swift>import Foundation
let wheel = [4,2,4,2,4,6,2,6]
func isPrime(_ number: Int) -> Bool {
if number < 2 { return false } if number % 2 == 0 { return number == 2 } if number % 3 == 0 { return number == 3 } if number % 5 == 0 { return number == 5 } var p = 7 while true { for w in wheel { if p * p > number { return true } if number % p == 0 { return false } p += w } }
}
func nextPrimeDigitNumber(_ number: Int) -> Int {
if number == 0 { return 2 } switch number % 10 { case 2: return number + 1 case 3, 5: return number + 2 default: return 2 + nextPrimeDigitNumber(number/10) * 10 }
}
func digitSum(_ num: Int) -> Int {
var sum = 0 var n = num while n > 0 { sum += n % 10 n /= 10 } return sum
}
func pad(string: String, width: Int) -> String {
if string.count >= width { return string } return String(repeating: " ", count: width - string.count) + string
}
func commatize(_ number: Int) -> String {
let n = NSNumber(value: number) return NumberFormatter.localizedString(from: n, number: .decimal)
}
let limit1 = 10000 let limit2 = 1000000000 let last = 10 var p = nextPrimeDigitNumber(0) var n = 0
print("Extra primes less than \(commatize(limit1)):") while p < limit1 {
if isPrime(digitSum(p)) && isPrime(p) { n += 1 print(pad(string: commatize(p), width: 5), terminator: n % 10 == 0 ? "\n" : " ") } p = nextPrimeDigitNumber(p)
}
print("\n\nLast \(last) extra primes less than \(commatize(limit2)):")
var extraPrimes = Array(repeating: 0, count: last) while p < limit2 {
if isPrime(digitSum(p)) && isPrime(p) { n += 1 extraPrimes[n % last] = p } p = nextPrimeDigitNumber(p)
}
for i in stride(from: last - 1, through: 0, by: -1) {
print("\(commatize(n - i)): \(commatize(extraPrimes[(n - i) % last]))")
}</lang>
- Output:
Extra primes less than 10,000: 2 3 5 7 23 223 227 337 353 373 557 577 733 757 773 2,333 2,357 2,377 2,557 2,753 2,777 3,253 3,257 3,323 3,527 3,727 5,233 5,237 5,273 5,323 5,527 7,237 7,253 7,523 7,723 7,727 Last 10 extra primes less than 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
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