Smarandache prime-digital sequence
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
- OEIS A019546: Primes whose digits are primes.
- https://www.scribd.com/document/214851583/On-the-Smarandache-prime-digital-subsequence-sequences
F#
This task uses Extensible Prime Generator (F#) <lang fsharp> // 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) </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 100th item of this sequence is 33223 1000th item of this sequence is 3273527
Factor
Naive
<lang factor>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:" print 25 smarandache ltake list>array . "100th: " write smarandache 99 [ cdr ] times car . ;</lang>
- Output:
First 25: { 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: 33223
Optimized
<lang factor>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. ! * 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 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 smarandache primes:" print first25 nl { 100 1000 10000 100000 } [ dup pprint "th smarandache prime: " write nth-smarandache ] each ;</lang>
- Output:
First 25 smarandache 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 100th smarandache prime: 33223 1000th smarandache prime: 3273527 10000th smarandache prime: 273322727 100000th smarandache prime: 23325232253
Go
As this task doesn't involve large numbers, a simple prime test routine is adequate. <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 isSPDSPrime(n int) bool {
if !isPrime(n) { return false } for n > 0 { r := n % 10 if r != 2 && r != 3 && r != 5 && r != 7 { return false } n /= 10 } return true
}
func listSPDSPrimes(startFrom, countFrom, countTo int, printOne bool) int {
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.Printf("%2d. %d\n", count, 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("\nThe hundredth term of the sequence is:") listSPDSPrimes(n+2, 25, 100, true)
}</lang>
- 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 The hundredth term of the sequence is: 100. 33223
Perl 6
<lang perl6>use Lingua::EN::Numbers::Cardinal; sub comma { $^i.flip.comb(3).join(',').flip }
- 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;</lang>
- 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
The prime number generator has been simplified and very little optimization was included. <lang rexx>/*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</lang>
- 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
<lang ring>
- 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
</lang>
- 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...
zkl
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. <lang zkl>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)));</lang> Or <lang zkl>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)));</lang> <lang zkl>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);</lang>
- 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