Smarandache prime-digital sequence

From Rosetta Code
Smarandache prime-digital sequence is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

The Smarandache prime-digital sequence (SPDS for brevity) is the sequence of primes whose digits are themselves prime.

For example 257 is an element of this sequence because it is prime itself and its digits: 2, 5 and 7 are also prime.

Task
  • Show the first 25 SPDS primes.
  • Show the hundredth SPDS prime.


See also



F#[edit]

This task uses Extensible Prime Generator (F#)

 
// Generate Smarandache prime-digital sequence. Nigel Galloway: May 31st., 2019
let rec spds g=seq{yield! g; yield! (spds (Seq.collect(fun g->[g*10+2;g*10+3;g*10+5;g*10+7]) g))}|>Seq.filter(isPrime)
spds [2;3;5;7] |> Seq.take 25 |> Seq.iter(printfn "%d")
printfn "\n\n100th item of this sequence is %d" (spds [2;3;5;7] |> Seq.item 99)
printfn "1000th item of this sequence is %d" (spds [2;3;5;7] |> Seq.item 999)
 
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


100th item of this sequence is 33223
1000th item of this sequence is 3273527

Factor[edit]

Naive[edit]

USING: combinators.short-circuit io lists lists.lazy math
math.parser math.primes prettyprint sequences ;
IN: rosetta-code.smarandache-naive
 
: smarandache? ( n -- ? )
{
[ number>string string>digits [ prime? ] all? ]
[ prime? ]
} 1&& ;
 
: smarandache ( -- list ) 1 lfrom [ smarandache? ] lfilter ;
 
: smarandache-demo ( -- )
"First 25 members of the Smarandache prime-digital sequence:"
print 25 smarandache ltake list>array .
"100th member: " write smarandache 99 [ cdr ] times car . ;
 
MAIN: smarandache-demo
Output:
First 25 members of the Smarandache prime-digital sequence:
{
    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
}
100th member: 33223

Optimized[edit]

USING: combinators generalizations io kernel math math.functions
math.primes prettyprint sequences ;
IN: rosetta-code.smarandache
 
! Observations:
! * For 2-digit numbers and higher, only 3 and 7 are viable in
! the ones place.
! * Only 2, 3, 5, and 7 are viable anywhere else.
! * It is possible to use this information to drastically
! reduce the amount of numbers to check for primality.
! * For instance, by these rules we can tell that the next
! potential Smarandache prime digital after 777 is 2223.
 
: next-one ( n -- n' ) 3 = 7 3 ? ; inline
 
: next-ten ( n -- n' )
{ { 2 [ 3 ] } { 3 [ 5 ] } { 5 [ 7 ] } [ drop 2 ] } case ;
 
: inc ( seq quot: ( n -- n' ) -- seq' )
[ 0 ] 2dip [ change-nth ] curry keep ; inline
 
: inc1 ( seq -- seq' ) [ next-one ] inc ;
: inc10 ( seq -- seq' ) [ next-ten ] inc ;
 
: inc-all ( seq -- seq' )
inc1 [ zero? not [ next-ten ] when ] V{ } map-index-as ;
 
: carry ( seq -- seq' )
dup [ 7 = not ] find drop {
{ 0 [ inc1 ] }
{ f [ inc-all 2 suffix! ] }
[ cut [ inc-all ] [ inc10 ] bi* append! ]
} case ;
 
: digits>integer ( seq -- n ) [ 10 swap ^ * ] map-index sum ;
 
: next-smarandache ( seq -- seq' )
[ digits>integer prime? ] [ carry dup ] do until ;
 
: .sm ( seq -- ) <reversed> [ pprint ] each nl ;
 
: first25 ( -- )
2 3 5 7 [ . ] 4 napply V{ 7 } clone
21 [ next-smarandache dup .sm ] times drop ;
 
: nth-smarandache ( n -- )
4 - V{ 7 } clone swap [ next-smarandache ] times .sm ;
 
: smarandache-demo ( -- )
"First 25 members of the Smarandache prime-digital sequence:"
print first25 nl { 100 1000 10000 100000 } [
dup pprint "th member: " write nth-smarandache
] each ;
 
MAIN: smarandache-demo
Output:
First 25 members of the Smarandache prime-digital sequence:
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

100th member: 33223
1000th member: 3273527
10000th member: 273322727
100000th member: 23325232253

Go[edit]

package main
 
import (
"fmt"
"math/big"
)
 
var b = new(big.Int)
 
func isSPDSPrime(n uint64) bool {
nn := n
for nn > 0 {
r := nn % 10
if r != 2 && r != 3 && r != 5 && r != 7 {
return false
}
nn /= 10
}
b.SetUint64(n)
if b.ProbablyPrime(0) { // 100% accurate up to 2 ^ 64
return true
}
return false
}
 
func listSPDSPrimes(startFrom, countFrom, countTo uint64, printOne bool) uint64 {
count := countFrom
for n := startFrom; ; n += 2 {
if isSPDSPrime(n) {
count++
if !printOne {
fmt.Printf("%2d. %d\n", count, n)
}
if count == countTo {
if printOne {
fmt.Println(n)
}
return n
}
}
}
}
 
func main() {
fmt.Println("The first 25 terms of the Smarandache prime-digital sequence are:")
fmt.Println(" 1. 2")
n := listSPDSPrimes(3, 1, 25, false)
fmt.Println("\nHigher terms:")
indices := []uint64{25, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000, 100000}
for i := 1; i < len(indices); i++ {
fmt.Printf("%6d. ", indices[i])
n = listSPDSPrimes(n+2, indices[i-1], indices[i], true)
}
}
Output:
The first 25 terms of the Smarandache prime-digital sequence are:
 1. 2
 2. 3
 3. 5
 4. 7
 5. 23
 6. 37
 7. 53
 8. 73
 9. 223
10. 227
11. 233
12. 257
13. 277
14. 337
15. 353
16. 373
17. 523
18. 557
19. 577
20. 727
21. 733
22. 757
23. 773
24. 2237
25. 2273

Higher terms:
   100. 33223
   200. 223337
   500. 723337
  1000. 3273527
  2000. 22332337
  5000. 55373333
 10000. 273322727
 20000. 727535273
 50000. 3725522753
100000. 23325232253

Julia[edit]

The prime single digits are 2, 3, 5, and 7. Except for 2 and 5, any number ending in 2 or 5 is not prime. So we start with [2, 3, 5, 7] and then add numbers that end in 3 or 7 and that only contain 2, 3, 5, and 7. This can be done via permutations of combinations with repetition.

 
using Combinatorics, Primes
 
combodigits(len) = sort!(unique(map(y -> join(y, ""), with_replacement_combinations("2357", len))))
 
function getprimes(N, maxdigits=9)
ret = [2, 3, 5, 7]
perms = Int[]
for i in 1:maxdigits-1, combo in combodigits(i), perm in permutations(combo)
n = parse(Int64, String(perm)) * 10
push!(perms, n + 3, n + 7)
end
for perm in sort!(perms)
if isprime(perm) && !(perm in ret)
push!(ret, perm)
if length(ret) >= N
return ret
end
end
end
end
 
const v = getprimes(10000)
println("The first 25 Smarandache primes are: ", v[1:25])
println("The 100th Smarandache prime is: ", v[100])
println("The 10000th Smarandache prime is: ", v[10000])
 
Output:
The first 25 Smarandache primes are: [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]
The 100th Smarandache prime is: 33223
The 10000th Smarandache prime is: 273322727

Perl 6[edit]

use Lingua::EN::Numbers; # Version 2.4.0 or higher
 
# Implemented as a lazy, extendable list
my $spds = flat 2,3,5,7, (1..*).map: { grep { .is-prime }, [X~] |((2,3,5,7) xx $_), (3,7) };
 
say 'Smarandache prime-digitals:';
printf "%15s: %s\n", ordinal(1+$_).tclc, comma $spds[$_] for flat ^25, 99, 999, 9999;
Output:
Smarandache prime-digitals:
          First: 2
         Second: 3
          Third: 5
         Fourth: 7
          Fifth: 23
          Sixth: 37
        Seventh: 53
         Eighth: 73
          Ninth: 223
          Tenth: 227
       Eleventh: 233
        Twelfth: 257
     Thirteenth: 277
     Fourteenth: 337
      Fifteenth: 353
      Sixteenth: 373
    Seventeenth: 523
     Eighteenth: 557
     Nineteenth: 577
      Twentieth: 727
   Twenty-first: 733
  Twenty-second: 757
   Twenty-third: 773
  Twenty-fourth: 2,237
   Twenty-fifth: 2,273
  One hundredth: 33,223
 One thousandth: 3,273,527
 Ten thousandth: 273,322,727

REXX[edit]

The prime number generator has been simplified and very little optimization was included.

/*REXX program lists a  sequence of  SPDS  (Smarandache prime-digital sequence)  primes.*/
parse arg n q /*get optional number of primes to find*/
if n=='' | n=="," then n= 25 /*Not specified? Then use the default.*/
if q='' then q= 100 /* " " " " " " */
say '═══listing the first' n "SPDS primes═══"
call spds n
do i=1 for words(q)+1; y=word(q, i); if y=='' | y=="," then iterate
say
say '═══listing the last of ' y "SPDS primes═══"
call spds -y
end /*i*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
spds: parse arg x 1 ox; x= abs(x) /*obtain the limit to be used for list.*/
c= 0 /*C number of SPDS primes found so far*/
#= 0 /*# number of primes found so far*/
do j=1 by 2 while c<x; z= j /*start: 1st even prime, then use odd. */
if z==1 then z= 2 /*handle the even prime (special case) */
/* [↓] divide by the primes. ___ */
do k=2 to # while k*k<=z /*divide Z with all primes ≤ √ Z */
if z//@.k==0 then iterate j /*÷ by prev. prime? ¬prime ___ */
end /*j*/ /* [↑] only divide up to √ Z */
#= # + 1; @.#= z /*bump the prime count; assign prime #*/
if verify(z, 2357)>0 then iterate j /*Digits ¬prime? Then skip this prime.*/
c= c + 1 /*bump the number of SPDS primes found.*/
if ox<0 then iterate /*don't display it, display the last #.*/
say right(z, 21) /*maybe display this prime ──► terminal*/
end /*j*/ /* [↑] only display N number of primes*/
if ox<0 then say right(z, 21) /*display one (the last) SPDS prime. */
return
output   when using the default inputs:
═══listing the first 25 SPDS primes═══
                    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

═══listing the last of  100 SPDS primes═══
                33223

═══listing the last of  1000 SPDS primes═══
              3273527

Ring[edit]

 
# Project: Calmo primes
load "stdlib.ring"
limit = 25
max = 300000
num = 0
see "working..." + nl
see "wait for done..." + nl
see "First 25 Calmo primes are:" + nl
for n = 1 to max
if isprime(n)
res = calmo(n)
if res = 1
num = num + 1
if num < limit + 1
see "" + num + ". " + n + nl
ok
if num = 100
see "The hundredth Calmo prime is:" + nl
see "" + num + ". " + n + nl
exit
ok
ok
ok
next
see "done..." + nl
 
func calmo(p)
sp = string(p)
for n = 1 to len(sp)
if not isprime(sp[n])
return 0
ok
next
return 1
 
Output:
working...
wait for done...
First 25 Calmo primes are:
1. 2
2. 3
3. 5
4. 7
5. 23
6. 37
7. 53
8. 73
9. 223
10. 227
11. 233
12. 257
13. 277
14. 337
15. 353
16. 373
17. 523
18. 557
19. 577
20. 727
21. 733
22. 757
23. 773
24. 2237
25. 2273
The hundredth Calmo prime is:
100. 33223
done...

Sidef[edit]

func is_prime_digital(n) {
n.is_prime && n.digits.all { .is_prime }
}
 
say is_prime_digital.first(25).join(',')
say is_prime_digital.nth(100)
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
33223

zkl[edit]

Library: GMP
GNU Multiple Precision Arithmetic Library

Using GMP ( probabilistic primes), because it is easy and fast to generate primes.

Extensible prime generator#zkl could be used instead.

var [const] BI=Import("zklBigNum");  // libGMP
 
spds:=Walker.zero().tweak(fcn(ps){
var [const] nps=T(0,0,1,1,0,1,0,1,0,0); // 2,3,5,7
p:=ps.nextPrime().toInt();
if(p.split().filter( fcn(n){ 0==nps[n] }) ) return(Void.Skip);
p // 733 --> (7,3,3) --> () --> good, 29 --> (2,9) --> (9) --> bad
}.fp(BI(1)));

Or

spds:=Walker.zero().tweak(fcn(ps){
var [const] nps="014689".inCommon;
p:=ps.nextPrime().toInt();
if(nps(p.toString())) return(Void.Skip);
p // 733 --> "" --> good, 29 --> "9" --> bad
}.fp(BI(1)));
println("The first 25 terms of the Smarandache prime-digital sequence are:");
spds.walk(25).concat(",").println();
 
println("The hundredth term of the sequence is: ",spds.drop(100-25).value);
println("1000th item of this sequence is : ",spds.drop(1_000-spds.n).value);
Output:
The first 25 terms of the Smarandache prime-digital sequence are:
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
The hundredth term of the sequence is: 33223
1000th item of this sequence is : 3273527