Extra primes: Difference between revisions

Content added Content deleted

Inline

Revision as of 00:15, 20 December 2020

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

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:

Factor

Translation of: Wren

Works with: Factor version 0.99 2020-08-14

<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:

Go

Translation of: Wren

<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:

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; !.= @.

     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($) /*display the output list to the term. */</lang>

output when using the default input:

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

    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

Wren

Library: Wren-math

Library: Wren-fmt

<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