Smarandache prime-digital sequence
You are encouraged to solve this task according to the task description, using any language you may know.
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
ALGOL 68
Uses a sieve to find primes. Requires --heap 256m for Algol 68G.
Uses the optimisations of the Factor, Phix, etc. samples.
<lang algol68># find elements of the Smarandache prime-digital sequence - primes whose #
- digits are all primes #
- Uses the observations that the final digit of 2 or more digit Smarandache #
- primes must be 3 or 7 and the only prime digits are 2, 3, 5 and 7 #
- Needs --heap 256m for Algol 68G #
BEGIN
# construct a sieve of primes up to 10 000 000 # INT prime max = 10 000 000; [ prime max ]BOOL prime; FOR i TO UPB prime DO prime[ i ] := TRUE OD; FOR s FROM 2 TO ENTIER sqrt( prime max ) DO IF prime[ s ] THEN FOR p FROM s * s BY s TO prime max DO prime[ p ] := FALSE OD FI OD; # consruct the Smarandache primes up to 10 000 000 # [ prime max ]BOOL smarandache; FOR i TO UPB prime DO smarandache[ i ] := FALSE OD; [ ]INT prime digits = ( 2, 3, 5, 7 ); [ 7 ]INT digits := ( 0, 0, 0, 0, 0, 0, 0 ); # tests whether the current digits form a Smarandache prime # PROC try smarandache = VOID: BEGIN INT possible prime := 0; FOR i TO UPB digits DO possible prime *:= 10 +:= digits[ i ] OD; smarandache[ possible prime ] := prime[ possible prime ] END # try smarandache # ; # tests whether the current digits plus 3 or 7 form a Smarandache prime # PROC try smarandache 3 or 7 = VOID: BEGIN digits[ UPB digits ] := 3; try smarandache; digits[ UPB digits ] := 7; try smarandache END # try smarandache 3 or 7 # ; # the 1 digit primes are all Smarandache primes # FOR d7 TO UPB prime digits DO smarandache[ prime digits[ d7 ] ] := TRUE OD; # try the possible 2, 3, etc. digit numbers composed of prime digits # FOR d6 TO UPB prime digits DO digits[ 6 ] := prime digits[ d6 ]; try smarandache 3 or 7; FOR d5 TO UPB prime digits DO digits[ 5 ] := prime digits[ d5 ]; try smarandache 3 or 7; FOR d4 TO UPB prime digits DO digits[ 4 ] := prime digits[ d4 ]; try smarandache 3 or 7; FOR d3 TO UPB prime digits DO digits[ 3 ] := prime digits[ d3 ]; try smarandache 3 or 7; FOR d2 TO UPB prime digits DO digits[ 2 ] := prime digits[ d2 ]; try smarandache 3 or 7; FOR d1 TO UPB prime digits DO digits[ 1 ] := prime digits[ d1 ]; try smarandache 3 or 7 OD; digits[ 1 ] := 0 OD; digits[ 2 ] := 0 OD; digits[ 3 ] := 0 OD; digits[ 4 ] := 0 OD; digits[ 5 ] := 0 OD; # print some Smarandache primes # INT count := 0; INT s100 := 0; INT s1000 := 0; INT s last := 0; INT p last := 0; print( ( "First 25 Smarandache primes:", newline ) ); FOR i TO UPB smarandache DO IF smarandache[ i ] THEN count +:= 1; s last := i; p last := count; IF count <= 25 THEN print( ( " ", whole( i, 0 ) ) ) ELIF count = 100 THEN s100 := i ELIF count = 1000 THEN s1000 := i FI FI OD; print( ( newline ) ); print( ( "100th Smarandache prime: ", whole( s100, 0 ), newline ) ); print( ( "1000th Smarandache prime: ", whole( s1000, 0 ), newline ) ); print( ( "Largest Smarandache prime under " , whole( prime max, 0 ) , ": " , whole( s last, 0 ) , " (Smarandache prime " , whole( p last, 0 ) , ")" , newline ) )
END</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 Largest Smarandache prime under 10000000: 7777753 (Smarandache prime 1903)
AWK
<lang AWK>
- syntax: GAWK -f SMARANDACHE_PRIME-DIGITAL_SEQUENCE.AWK
BEGIN {
limit = 25 printf("1-%d:",limit) while (1) { if (is_prime(++n)) { if (all_digits_prime(n) == 1) { if (++count <= limit) { printf(" %d",n) } if (count == 100) { printf("\n%d: %d\n",count,n) break } } } } exit(0)
} function all_digits_prime(n, i) {
for (i=1; i<=length(n); i++) { if (!is_prime(substr(n,i,1))) { return(0) } } return(1)
} 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-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 100: 33223
C
<lang c>#include <locale.h>
- include <stdbool.h>
- include <stdint.h>
- include <stdio.h>
typedef uint32_t integer;
integer next_prime_digit_number(integer 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(integer n) {
if (n < 2) return false; if (n % 2 == 0) return n == 2; if (n % 3 == 0) return n == 3; if (n % 5 == 0) return n == 5; static const integer wheel[] = { 4,2,4,2,4,6,2,6 }; integer p = 7; for (;;) { for (int i = 0; i < 8; ++i) { if (p * p > n) return true; if (n % p == 0) return false; p += wheel[i]; } }
}
int main() {
setlocale(LC_ALL, ""); const integer limit = 1000000000; integer n = 0, max = 0; printf("First 25 SPDS primes:\n"); for (int i = 0; n < limit; ) { n = next_prime_digit_number(n); if (!is_prime(n)) continue; if (i < 25) { if (i > 0) printf(" "); printf("%'u", n); } else if (i == 25) printf("\n"); ++i; if (i == 100) printf("Hundredth SPDS prime: %'u\n", n); else if (i == 1000) printf("Thousandth SPDS prime: %'u\n", n); else if (i == 10000) printf("Ten thousandth SPDS prime: %'u\n", n); max = n; } printf("Largest SPDS prime less than %'u: %'u\n", limit, max); return 0;
}</lang>
- Output:
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 2,237 2,273 Hundredth SPDS prime: 33,223 Thousandth SPDS prime: 3,273,527 Ten thousandth SPDS prime: 273,322,727 Largest SPDS prime less than 1,000,000,000: 777,777,773
C++
<lang cpp>#include <iostream>
- include <cstdint>
using integer = uint32_t;
integer next_prime_digit_number(integer 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(integer n) {
if (n < 2) return false; if (n % 2 == 0) return n == 2; if (n % 3 == 0) return n == 3; if (n % 5 == 0) return n == 5; constexpr integer wheel[] = { 4,2,4,2,4,6,2,6 }; integer p = 7; for (;;) { for (integer w : wheel) { if (p * p > n) return true; if (n % p == 0) return false; p += w; } }
}
int main() {
std::cout.imbue(std::locale("")); const integer limit = 1000000000; integer n = 0, max = 0; std::cout << "First 25 SPDS primes:\n"; for (int i = 0; n < limit; ) { n = next_prime_digit_number(n); if (!is_prime(n)) continue; if (i < 25) { if (i > 0) std::cout << ' '; std::cout << n; } else if (i == 25) std::cout << '\n'; ++i; if (i == 100) std::cout << "Hundredth SPDS prime: " << n << '\n'; else if (i == 1000) std::cout << "Thousandth SPDS prime: " << n << '\n'; else if (i == 10000) std::cout << "Ten thousandth SPDS prime: " << n << '\n'; max = n; } std::cout << "Largest SPDS prime less than " << limit << ": " << max << '\n'; return 0;
}</lang>
- Output:
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 2,237 2,273 Hundredth SPDS prime: 33,223 Thousandth SPDS prime: 3,273,527 Ten thousandth SPDS prime: 273,322,727 Largest SPDS prime less than 1,000,000,000: 777,777,773
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 members of the Smarandache prime-digital sequence:" print 25 smarandache ltake list>array . "100th member: " write smarandache 99 [ cdr ] times car . ;
MAIN: smarandache-demo</lang>
- 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
<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. ! * 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</lang>
- 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
Basic
<lang go>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) }
}</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 Higher terms: 100. 33223 200. 223337 500. 723337 1000. 3273527 2000. 22332337 5000. 55373333 10000. 273322727 20000. 727535273 50000. 3725522753 100000. 23325232253
Optimized
This version is inspired by the optimizations used in the Factor and Phix entries which are expressed here as a kind of base-4 arithmetic using a digits set of {2, 3, 5, 7} where leading '2's are significant.
This is more than 30 times faster than the above version (runs in about 12.5 seconds on my Celeron @1.6GHx) and could be quickened up further (to around 4 seconds) by using a wrapper for GMP rather than Go's native big.Int type. <lang go>package main
import (
"fmt" "math/big"
)
type B2357 []byte
var bi = new(big.Int)
func isSPDSPrime(b B2357) bool {
bi.SetString(string(b), 10) return bi.ProbablyPrime(0) // 100% accurate up to 2 ^ 64
}
func listSPDSPrimes(startFrom B2357, countFrom, countTo uint64, printOne bool) B2357 {
count := countFrom n := startFrom for { if isSPDSPrime(n) { count++ if !printOne { fmt.Printf("%2d. %s\n", count, string(n)) } if count == countTo { if printOne { fmt.Println(string(n)) } return n } } if printOne { n = n.AddTwo() } else { n = n.AddOne() } }
}
func incDigit(digit byte) byte {
switch digit { case '2': return '3' case '3': return '5' case '5': return '7' default: return '9' // say }
}
func (b B2357) AddOne() B2357 {
le := len(b) b[le-1] = incDigit(b[le-1]) for i := le - 1; i >= 0; i-- { if b[i] < '9' { break } else if i > 0 { b[i] = '2' b[i-1] = incDigit(b[i-1]) } else { b[0] = '2' nb := make(B2357, le+1) copy(nb[1:], b) nb[0] = '2' return nb } } return b
}
func (b B2357) AddTwo() B2357 {
return b.AddOne().AddOne()
}
func main() {
fmt.Println("The first 25 terms of the Smarandache prime-digital sequence are:") n := listSPDSPrimes(B2357{'2'}, 0, 4, false) n = listSPDSPrimes(n.AddOne(), 4, 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.AddTwo(), indices[i-1], indices[i], true) }
}</lang>
- Output:
Same as before.
Haskell
Using the optimized approach of generated numbers from prime digits and testing for primality. <lang haskell>{-# LANGUAGE NumericUnderscores #-} import Control.Monad (guard) import Math.NumberTheory.Primes.Testing (isPrime) import Data.List.Split (chunksOf) import Data.List (intercalate) import Text.Printf (printf)
smarandache :: [Integer] smarandache = [2,3,5,7] <> s [2,3,5,7] >>= \x -> guard (isPrime x) >> [x]
where s xs = r <> s r where r = xs >>= \x -> [x*10+2, x*10+3, x*10+5, x*10+7]
nextSPDSTerms :: [Int] -> [(String, String)] nextSPDSTerms = go 1 smarandache
where go _ _ [] = [] go c (x:xs) terms | c `elem` terms = (commas c, commas x) : go nextCount xs (tail terms) | otherwise = go nextCount xs terms where nextCount = succ c
commas :: Show a => a -> String commas = reverse . intercalate "," . chunksOf 3 . reverse . show
main :: IO () main = do
printf "The first 25 SPDS:\n%s\n\n" $ f smarandache mapM_ (uncurry (printf "The %9sth SPDS: %15s\n")) $ nextSPDSTerms [100, 1_000, 10_000, 100_000, 1_000_000] where f = show . take 25</lang>
- Output:
The first 25 SPDS: [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 SPDS: 33,223 The 1,000th SPDS: 3,273,527 The 10,000th SPDS: 273,322,727 The 100,000th SPDS: 23,325,232,253 The 1,000,000th SPDS: 753,373,253,723 ./smarandache_optimized 15.25s user 0.45s system 98% cpu 15.938 total
J
Prime numbers have a built-in verb p: . It's easy and quick to get a list of prime numbers and determine which are composed entirely of the appropriate digits.
Filter=: (#~`)(`:6) NB. given a prime y, smarandache y is 1 iff it's a smarandache prime smarandache=: [: -. (0 e. (p:i.4) e.~ 10 #.inv ])&> SP=: smarandache Filter p: i. 1000000 SP {~ i. 25 NB. 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 99 _1 { SP NB. 100th and largest Smarandache prime of the first million primes 33223 7777753 # SP NB. Tally of Smarandache primes in the first million primes 1903
Graph by index of Smarandache primes in index of primes through two millionth prime. The graph shows jumps where, I suppose, the most significant digit is 8, 9, then 1. https://imgur.com/a/hvbhf2S
Java
Generate next in sequence directly from previous, inspired by previous solutions. <lang java> public class SmarandachePrimeDigitalSequence {
public static void main(String[] args) { long s = getNextSmarandache(7); System.out.printf("First 25 Smarandache prime-digital sequence numbers:%n2 3 5 7 "); for ( int count = 1 ; count <= 21 ; s = getNextSmarandache(s) ) { if ( isPrime(s) ) { System.out.printf("%d ", s); count++; } } System.out.printf("%n%n"); for (int i = 2 ; i <=5 ; i++ ) { long n = (long) Math.pow(10, i); System.out.printf("%,dth Smarandache prime-digital sequence number = %d%n", n, getSmarandachePrime(n)); } } private static final long getSmarandachePrime(long n) { if ( n < 10 ) { switch ((int) n) { case 1: return 2; case 2: return 3; case 3: return 5; case 4: return 7; } } long s = getNextSmarandache(7); long result = 0; for ( int count = 1 ; count <= n-4 ; s = getNextSmarandache(s) ) { if ( isPrime(s) ) { count++; result = s; } } return result; } private static final boolean isPrime(long test) { if ( test % 2 == 0 ) return false; for ( long i = 3 ; i <= Math.sqrt(test) ; i += 2 ) { if ( test % i == 0 ) { return false; } } return true; }
private static long getNextSmarandache(long n) { // If 3, next is 7 if ( n % 10 == 3 ) { return n+4; } long retVal = n-4; // Last digit 7. k = largest position from right where we have a 7. int k = 0; while ( n % 10 == 7 ) { k++; n /= 10; } // Determine first digit from right where digit != 7. long digit = n % 10;
// Digit is 2, 3, or 5. 3-2 = 1, 5-3 = 2, 7-5 = 2, so digit = 2, coefficient = 1, otherwise 2. long coeff = (digit == 2 ? 1 : 2); // Compute next value retVal += coeff * Math.pow(10, k); // Subtract values for digit = 7. while ( k > 1 ) { retVal -= 5 * Math.pow(10, k-1); k--; } // Even works for 777..777 --> 2222...223 return retVal; }
} </lang>
- Output:
First 25 Smarandache prime-digital sequence numbers: 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-digital sequence number = 33223 1,000th Smarandache prime-digital sequence number = 3273527 10,000th Smarandache prime-digital sequence number = 273322727 100,000th Smarandache prime-digital sequence number = 23325232253
Julia
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. <lang julia> 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])
</lang>
- 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
Lua
<lang lua>-- FUNCS: local function T(t) return setmetatable(t, {__index=table}) end table.firstn = function(t,n) local s=T{} n=n>#t and #t or n for i = 1,n do s[i]=t[i] end return s end
-- SIEVE: local sieve, S = {}, 50000 for i = 2,S do sieve[i]=true end for i = 2,S do if sieve[i] then for j=i*i,S,i do sieve[j]=nil end end end
-- TASKS: local digs, cans, spds, N = {2,3,5,7}, T{0}, T{}, 100 while #spds < N do
local c = cans:remove(1) for _,d in ipairs(digs) do cans:insert(c*10+d) end if sieve[c] then spds:insert(c) end
end print("1-25 : " .. spds:firstn(25):concat(" ")) print("100th: " .. spds[100])</lang>
- Output:
1-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
Pascal
uses [[1]]
Simple Brute force.Testing for prime takes most of the time.
<lang pascal>program Smarandache;
uses
sysutils,primsieve;// http://rosettacode.org/wiki/Extensible_prime_generator#Pascal
const
Digits : array[0..3] of Uint32 = (2,3,5,7);
var
i,j,pot10,DgtLimit,n,DgtCnt,v,cnt,LastPrime,Limit : NativeUint;
procedure Check(n:NativeUint); var
p : NativeUint;
Begin
p := LastPrime; while p< n do p := nextprime; if p = n then begin inc(cnt); IF (cnt <= 25) then Begin IF cnt = 25 then Begin writeln(n); Limit := 100; end else Write(n,','); end else IF cnt = Limit then Begin Writeln(cnt:9,n:16); Limit *=10; if Limit > 10000 then HALT; end; end; LastPrime := p;
end;
Begin
Limit := 25; LastPrime:=1;
//Creating the numbers not the best way but all upto 11 digits take 0.05s //here only 9 digits
i := 0; pot10 := 1; DgtLimit := 1; v := 4; repeat repeat j := i; DgtCnt := 0; pot10 := 1; n := 0; repeat n += pot10*Digits[j MOD 4]; j := j DIV 4; pot10 *=10; inc(DgtCnt); until DgtCnt = DgtLimit; Check(n); inc(i); until i=v; //one more digit v *=4; i :=0; inc(DgtLimit); until DgtLimit= 12;
end.</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 100 33223 1000 3273527 10000 273322727 real 0m0,171s
Perl
<lang perl>use strict; use warnings; use feature 'say'; use feature 'state'; use ntheory qw<is_prime>; use Lingua::EN::Numbers qw(num2en_ordinal);
my @prime_digits = <2 3 5 7>; my @spds = grep { is_prime($_) && /^[@{[join ,@prime_digits]}]+$/ } 1..100; my @p = map { $_+3, $_+7 } map { 10*$_ } @prime_digits;
while ($#spds < 100_000) {
state $o++; my $oom = 10**(1+$o); my @q; for my $l (@prime_digits) { push @q, map { $l*$oom + $_ } @p; } push @spds, grep { is_prime($_) } @p = @q;
}
say 'Smarandache prime-digitals:'; printf "%22s: %s\n", ucfirst(num2en_ordinal($_)), $spds[$_-1] for 1..25, 100, 1000, 10_000, 100_000;</lang>
- Output:
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: 2237 Twenty-fifth: 2273 One hundredth: 33223 One thousandth: 3273527 Ten thousandth: 273322727 One hundred thousandth: 23325232253
Phix
Optimised. As noted on the Factor entry, candidates>10 must end in 3 or 7 (since they would not be prime if they ended in 2 or 5), which we efficiently achieve by alternately adding {4,-4}. Digits to the left of that must all be 2/3/5/7, so we add {1,2,2,-5}*10^k to cycle round those digits. Otherwise it is exactly like counting by adding 1 to each digit and carrying 1 left when we do a 9->0.
I had planned to effectively merge a list of potential candidates with a list of all prime numbers, but because of the massive gaps (eg between 777,777,777 and 2,222,222,223) it proved much faster to test each candidate for primality individually. Timings below show just how much this improves things. <lang Phix>atom t0 = time() sequence spds = {2,3,5,7} atom nxt_candidate = 23 sequence adj = {{4,-4},sq_mul({1,2,2,-5},10)},
adjn = {1,1}
include mpfr.e mpz zprime = mpz_init() randstate state = gmp_randinit_mt()
procedure populate_spds(integer n)
while length(spds)<n do mpz_set_d(zprime,nxt_candidate) if mpz_probable_prime_p(zprime,state) then spds &= nxt_candidate end if for i=1 to length(adjn) do sequence adjs = adj[i] integer adx = adjn[i] nxt_candidate += adjs[adx] adx += 1 if adx<=length(adjs) then adjn[i] = adx exit end if adjn[i] = 1 if i=length(adjn) then -- (this is eg 777, by now 223 carry 1, -> 2223) adj = append(adj,sq_mul(adj[$],10)) adjn = append(adjn, 1) nxt_candidate += adj[$][2] exit end if end for end while
end procedure
populate_spds(25) printf(1,"spds[1..25]:%v\n",{spds[1..25]}) for n=2 to 5 do
integer p = power(10,n) populate_spds(p) printf(1,"spds[%d]:%d\n",{p,spds[p]})
end for for n=7 to 10 do
atom p = power(10,n), dx = abs(binary_search(p,spds))-1 printf(1,"largest spds prime less than %,15d:%,14d\n",{p,spds[dx]})
end for ?elapsed(time()-t0)</lang>
- Output:
spds[1..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} spds[100]:33,223 spds[1,000]:3,273,527 spds[10,000]:273,322,727 spds[100,000]:23,325,232,253 largest spds prime less than 10,000,000: 7,777,753 largest spds prime less than 100,000,000: 77,777,377 largest spds prime less than 1,000,000,000: 777,777,773 largest spds prime less than 10,000,000,000: 7,777,777,577 "3.6s"
For comparison, on the same machine:
Factor (as optimised) took 45s to calculate the 100,000th number.
Go took 1 min 50 secs to calculate the 100,000th number - the optimised version got that down to 5.6s
Julia crashed when the limit was changed to 100,000, however it took 11s just to calculate the 10,000th number anyway.
The original Raku version was by far the slowest of all I tried, taking 1 min 15s just to calculate the 10,000th number, however it has since been replaced (I cannot actually run the latest Raku version, but I assume it is similar to the Perl one) and that completes near-instantly. Adding two 0 to limit in the C entry above gets a matching 777777773 on tio/clang in 27s, not directly comparable, and obviously you cannot add a 3rd 0 without changing those uint32.
Python
<lang Python> def divisors(n):
divs = [1] for ii in range(2, int(n ** 0.5) + 3): if n % ii == 0: divs.append(ii) divs.append(int(n / ii)) divs.append(n) return list(set(divs))
def is_prime(n):
return len(divisors(n)) == 2
def digit_check(n):
if len(str(n))<2: return True else: for digit in str(n): if not is_prime(int(digit)): return False return True
def sequence(max_n=None):
ii = 0 n = 0 while True: ii += 1 if is_prime(ii): if max_n is not None: if n>max_n: break if digit_check(ii): n += 1 yield ii
if __name__ == '__main__':
generator = sequence(100) for index, item in zip(range(1, 16), generator): print(index, item) for index, item in zip(range(16, 100), generator): pass print(100, generator.__next__())
</lang>
Output <lang Python> 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 100 33223 </lang>
Raku
(formerly Perl 6)
<lang perl6>use Lingua::EN::Numbers; use ntheory:from<Perl5> <:all>;
- Implemented as a lazy, extendable list
my $spds = grep { .&is_prime }, flat [2,3,5,7], [23,27,33,37,53,57,73,77], -> $p
{ state $o++; my $oom = 10**(1+$o); [ flat (2,3,5,7).map: -> $l { (|$p).map: $l*$oom+* } ] } … *;
say 'Smarandache prime-digitals:'; printf "%22s: %s\n", ordinal(1+$_).tclc, comma $spds[$_] for flat ^25, 99, 999, 9999, 99999;</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 One hundred thousandth: 23,325,232,253
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 1000 /* " " " " " " */ 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...
Rust
<lang rust>fn is_prime(n: u32) -> bool {
if n < 2 { return false; } if n % 2 == 0 { return n == 2; } if n % 3 == 0 { return n == 3; } if n % 5 == 0 { return n == 5; } let mut p = 7; const WHEEL: [u32; 8] = [4, 2, 4, 2, 4, 6, 2, 6]; loop { for w in &WHEEL { if p * p > n { return true; } if n % p == 0 { return false; } p += w; } }
}
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 smarandache_prime_digital_sequence() -> impl std::iter::Iterator<Item = u32> {
let mut n = 0; std::iter::from_fn(move || { loop { n = next_prime_digit_number(n); if is_prime(n) { break; } } Some(n) })
}
fn main() {
let limit = 1000000000; let mut seq = smarandache_prime_digital_sequence().take_while(|x| *x < limit); println!("First 25 SPDS primes:"); for i in seq.by_ref().take(25) { print!("{} ", i); } println!(); if let Some(p) = seq.by_ref().nth(99 - 25) { println!("100th SPDS prime: {}", p); } if let Some(p) = seq.by_ref().nth(999 - 100) { println!("1000th SPDS prime: {}", p); } if let Some(p) = seq.by_ref().nth(9999 - 1000) { println!("10,000th SPDS prime: {}", p); } if let Some(p) = seq.last() { println!("Largest SPDS prime less than {}: {}", limit, p); }
}</lang>
- Output:
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 100th SPDS prime: 33223 1000th SPDS prime: 3273527 10,000th SPDS prime: 273322727 Largest SPDS prime less than 1000000000: 777777773
Ruby
Attaching 3 and 7 to permutations of 2,3,5 and 7 <lang ruby>require "prime"
smarandache = Enumerator.new do|y|
prime_digits = [2,3,5,7] prime_digits.each{|pr| y << pr} # yield the below-tens (1..).each do |n| prime_digits.repeated_permutation(n).each do |perm| c = perm.join.to_i * 10 y << c + 3 if (c+3).prime? y << c + 7 if (c+7).prime? end end
end
seq = smarandache.take(100) p seq.first(25) p seq.last </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] 33223
Calculating the 10,000th Smarandache number takes about 1.2 seconds.
Sidef
<lang ruby>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)</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 33223
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