Palindromic primes
Palindromic primes 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.
- Task
Find and show all palindromic primes n, where n < 1000
11l
F is_prime(a)
I a == 2
R 1B
I a < 2 | a % 2 == 0
R 0B
L(i) (3 .. Int(sqrt(a))).step(2)
I a % i == 0
R 0B
R 1B
L(n) 1000
I is_prime(n)
V s = String(n)
I s == reversed(s)
print(n, end' ‘ ’)
print()- Output:
2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929
Action!
INCLUDE "H6:SIEVE.ACT"
BYTE Func IsPalindromicPrime(INT i BYTE ARRAY primes)
BYTE d
INT rev,tmp
IF primes(i)=0 THEN
RETURN (0)
FI
rev=0 tmp=i
WHILE tmp#0
DO
d=tmp MOD 10
rev==*10
rev==+d
tmp==/10
OD
IF rev#i THEN
RETURN (0)
FI
RETURN (1)
PROC Main()
DEFINE MAX="999"
BYTE ARRAY primes(MAX+1)
INT i,count=[0]
Put(125) PutE() ;clear the screen
Sieve(primes,MAX+1)
FOR i=2 TO MAX
DO
IF IsPalindromicPrime(i,primes) THEN
PrintI(i) Put(32)
count==+1
FI
OD
PrintF("%E%EThere are %I palindromic primes",count)
RETURN- Output:
Screenshot from Atari 8-bit computer
2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929 There are 20 palindromic primes
ALGOL 68
Generates the palindrmic 3 digit numbers and uses the observations that all 1 digit primes are palindromic and that for 2 digit numbers, only multiples of 11 are palindromic and hence 11 is the only two digit palindromic prime.
BEGIN # find primes that are palendromic in base 10 #
INT max prime = 999;
# sieve the primes to max prime #
PR read "primes.incl.a68" PR
[]BOOL prime = PRIMESIEVE max prime;
# print the palendromic primes in the base 10 #
# all 1 digit primes are palindromic #
# the only palindromic 2 digit numbers are multiples of 11 #
# so 11 is the only possible 2 digit palindromic prime #
FOR n TO 11 DO IF prime[ n ] THEN print( ( " ", whole( n, 0 ) ) ) FI OD;
# three digit numbers, the first and last digits must be odd #
# and cannot be 5 (as the number would be divisible by 5) #
FOR fl BY 2 TO 9 DO
IF fl /= 5 THEN
FOR m FROM 0 TO 9 DO
INT n = ( ( ( fl * 10 ) + m ) * 10 ) + fl;
IF prime[ n ] THEN
# have a palindromic prime #
print( ( " ", whole( n, 0 ) ) )
FI
OD
FI
OD;
print( ( newline ) )
END- Output:
2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929
Arturo
loop split.every: 10 select 2..1000 'x [
and? prime? x
x = to :integer reverse to :string x
] 'a -> print map a => [pad to :string & 4]
- Output:
2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929
AWK
# syntax: GAWK -f PALINDROMIC_PRIMES.AWK
BEGIN {
start = 1
stop = 999
for (i=start; i<=stop; i++) {
if (is_prime(i) && reverse(i) == i) {
printf("%d ",i)
count++
}
}
printf("\nPalindromic primes %d-%d: %d\n",start,stop,count)
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)
}
function reverse(str, i,rts) {
for (i=length(str); i>=1; i--) {
rts = rts substr(str,i,1)
}
return(rts)
}
- Output:
2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929 Palindromic primes 1-999: 20
C++
This includes a solution for the similar task Palindromic primes in base 16.
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <string>
unsigned int reverse(unsigned int base, unsigned int n) {
unsigned int rev = 0;
for (; n > 0; n /= base)
rev = rev * base + (n % base);
return rev;
}
class palindrome_generator {
public:
explicit palindrome_generator(unsigned int base)
: base_(base), upper_(base) {}
unsigned int next_palindrome();
private:
unsigned int base_;
unsigned int lower_ = 1;
unsigned int upper_;
unsigned int next_ = 0;
bool even_ = false;
};
unsigned int palindrome_generator::next_palindrome() {
++next_;
if (next_ == upper_) {
if (even_) {
lower_ = upper_;
upper_ *= base_;
}
next_ = lower_;
even_ = !even_;
}
return even_ ? next_ * upper_ + reverse(base_, next_)
: next_ * lower_ + reverse(base_, next_ / base_);
}
bool is_prime(unsigned int n) {
if (n < 2)
return false;
if (n % 2 == 0)
return n == 2;
if (n % 3 == 0)
return n == 3;
for (unsigned int p = 5; p * p <= n; p += 4) {
if (n % p == 0)
return false;
p += 2;
if (n % p == 0)
return false;
}
return true;
}
std::string to_string(unsigned int base, unsigned int n) {
assert(base <= 36);
static constexpr char digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
std::string str;
for (; n != 0; n /= base)
str += digits[n % base];
std::reverse(str.begin(), str.end());
return str;
}
void print_palindromic_primes(unsigned int base, unsigned int limit) {
auto width =
static_cast<unsigned int>(std::ceil(std::log(limit) / std::log(base)));
unsigned int count = 0;
auto columns = 80 / (width + 1);
std::cout << "Base " << base << " palindromic primes less than " << limit
<< ":\n";
palindrome_generator pgen(base);
unsigned int palindrome;
while ((palindrome = pgen.next_palindrome()) < limit) {
if (is_prime(palindrome)) {
++count;
std::cout << std::setw(width) << to_string(base, palindrome)
<< (count % columns == 0 ? '\n' : ' ');
}
}
if (count % columns != 0)
std::cout << '\n';
std::cout << "Count: " << count << '\n';
}
void count_palindromic_primes(unsigned int base, unsigned int limit) {
unsigned int count = 0;
palindrome_generator pgen(base);
unsigned int palindrome;
while ((palindrome = pgen.next_palindrome()) < limit)
if (is_prime(palindrome))
++count;
std::cout << "Number of base " << base << " palindromic primes less than "
<< limit << ": " << count << '\n';
}
int main() {
print_palindromic_primes(10, 1000);
std::cout << '\n';
print_palindromic_primes(10, 100000);
std::cout << '\n';
count_palindromic_primes(10, 1000000000);
std::cout << '\n';
print_palindromic_primes(16, 500);
}
- Output:
Base 10 palindromic primes less than 1000:
2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929
Count: 20
Base 10 palindromic primes less than 100000:
2 3 5 7 11 101 131 151 181 191 313 353 373
383 727 757 787 797 919 929 10301 10501 10601 11311 11411 12421
12721 12821 13331 13831 13931 14341 14741 15451 15551 16061 16361 16561 16661
17471 17971 18181 18481 19391 19891 19991 30103 30203 30403 30703 30803 31013
31513 32323 32423 33533 34543 34843 35053 35153 35353 35753 36263 36563 37273
37573 38083 38183 38783 39293 70207 70507 70607 71317 71917 72227 72727 73037
73237 73637 74047 74747 75557 76367 76667 77377 77477 77977 78487 78787 78887
79397 79697 79997 90709 91019 93139 93239 93739 94049 94349 94649 94849 94949
95959 96269 96469 96769 97379 97579 97879 98389 98689
Count: 113
Number of base 10 palindromic primes less than 1000000000: 5953
Base 16 palindromic primes less than 500:
2 3 5 7 B D 11 101 151 161 191 1B1 1C1
Count: 13
Delphi
function IsPrime(N: int64): boolean;
{Fast, optimised prime test}
var I,Stop: int64;
begin
if (N = 2) or (N=3) then Result:=true
else if (n <= 1) or ((n mod 2) = 0) or ((n mod 3) = 0) then Result:= false
else
begin
I:=5;
Stop:=Trunc(sqrt(N+0.0));
Result:=False;
while I<=Stop do
begin
if ((N mod I) = 0) or ((N mod (I + 2)) = 0) then exit;
Inc(I,6);
end;
Result:=True;
end;
end;
function IsPalindrome(N, Base: integer): boolean;
{Test if number is the same forward or backward}
{For a specific Radix}
var S1,S2: string;
begin
S1:=GetRadixString(N,Base);
S2:=ReverseString(S1);
Result:=S1=S2;
end;
procedure ShowPalindromePrimes(Memo: TMemo);
var I: integer;
var Cnt: integer;
var S: string;
begin
Cnt:=0;
for I:=1 to 1000-1 do
if IsPrime(I) then
if IsPalindrome(I,10) then
begin
Inc(Cnt);
S:=S+Format('%4D',[I]);
If (Cnt mod 5)=0 then S:=S+CRLF;
end;
Memo.Lines.Add(S);
Memo.Lines.Add('Count='+IntToStr(Cnt));
end;
- Output:
2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929 Count=20 Elapsed Time: 2.117 ms.
Factor
Simple
A simple solution that suffices for the task:
USING: kernel math.primes present prettyprint sequences ;
1000 primes-upto [ present dup reverse = ] filter stack.
- Output:
2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929
Fast
A much more efficient solution that generates palindromic numbers directly and filters primes from them:
USING: io kernel lists lists.lazy math math.functions
math.primes math.ranges prettyprint sequences
tools.memory.private ;
! Create a palindrome from its base natural number.
: create-palindrome ( n odd? -- m )
dupd [ 10 /i ] when swap [ over 0 > ]
[ 10 * [ 10 /mod ] [ + ] bi* ] while nip ;
! Create an ordered infinite lazy list of palindromic numbers.
: lpalindromes ( -- l )
0 lfrom [
10 swap ^ dup 10 * [a,b)
[ [ t create-palindrome ] map ]
[ [ f create-palindrome ] map ] bi
[ sequence>list ] bi@ lappend
] lmap-lazy lconcat ;
: lpalindrome-primes ( -- list )
lpalindromes [ prime? ] lfilter ;
"10,000th palindromic prime:" print
9999 lpalindrome-primes lnth commas print nl
"Palindromic primes less than 1,000:" print
lpalindrome-primes [ 1000 < ] lwhile [ . ] leach
- Output:
10,000th palindromic prime: 13,649,694,631 Palindromic primes less than 1,000: 2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929
FreeBASIC
#include "isprime.bas"
function is_pal( s as string ) as boolean
dim as integer i, n = len(s)
for i = 1 to n\2
if mid(s,i,1)<>mid(s,n-i+1,1) then return false
next i
return true
end function
for i as uinteger = 2 to 999
if is_pal( str(i) ) andalso isprime(i) then print i;" ";
next i : print- Output:
2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929
Go
package main
import (
"fmt"
"rcu"
)
func reversed(n int) int {
rev := 0
for n > 0 {
rev = rev*10 + n%10
n /= 10
}
return rev
}
func main() {
primes := rcu.Primes(99999)
var pals []int
for _, p := range primes {
if p == reversed(p) {
pals = append(pals, p)
}
}
fmt.Println("Palindromic primes under 1,000:")
var smallPals, bigPals []int
for _, p := range pals {
if p < 1000 {
smallPals = append(smallPals, p)
} else {
bigPals = append(bigPals, p)
}
}
rcu.PrintTable(smallPals, 10, 3, false)
fmt.Println()
fmt.Println(len(smallPals), "such primes found.")
fmt.Println("\nAdditional palindromic primes under 100,000:")
rcu.PrintTable(bigPals, 10, 6, true)
fmt.Println()
fmt.Println(len(bigPals), "such primes found,", len(pals), "in all.")
}
- Output:
Same as Wren entry.
Haskell
import Data.Numbers.Primes
palindromicPrimes :: [Integer]
palindromicPrimes =
filter (((==) <*> reverse) . show) primes
main :: IO ()
main =
mapM_ print $
takeWhile
(1000 >)
palindromicPrimes
- Output:
2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929
J
palindromic=: (-: |.)@":@>
(#~ palindromic) p: i. p:inv 1000
2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929
jq
Works with gojq, the Go implementation of jq
In this entry, we define both a naive generate-and-test generator of the palindromic primes, and a more sophisticated one that is well-suited for generating very large numbers of such primes, as illustrated by counting the number less than 10^10.
For a suitable implementation of `is_prime` as used here, see Erdős-primes#jq.
Preliminaries
def count(s): reduce s as $x (null; .+1);
def emit_until(cond; stream): label $out | stream | if cond then break $out else . end;Naive version
def primes:
2, (range(3;infinite;2) | select(is_prime));
def palindromic_primes_slowly:
primes | select( tostring|explode | (. == reverse));Less naive version
# Output: an unbounded stream of palindromic primes
def palindromic_primes:
# Output: a naively constructed stream of palindromic strings of length >= 2
def palindromic_candidates:
def rev: # reverse a string
explode|reverse|implode;
def unconstrained($length):
if $length==1 then range(0;10) | tostring
else (range(0;10)|tostring)
| . + unconstrained($length -1 )
end;
def middle($length): # $length > 0
if $length==1 then range(0;10) | tostring
elif $length % 2 == 1
then (($length -1) / 2) as $len
| unconstrained($len) as $left
| (range(0;10) | tostring) as $mid
| $left + $mid + ($left|rev)
else ($length / 2) as $len
| unconstrained($len) as $left
| $left + ($left|rev)
end;
# palindromes with an even number of digits are divisible by 11
range(1;infinite;2) as $mid
| ("1", "3", "7", "9") as $start
| $start + middle($mid) + $start ;
2, 3, 5, 7, 11,
(palindromic_candidates | tonumber | select(is_prime));Demonstrations
"Palindromic primes < 1000:",
emit_until(. >= 1000; palindromic_primes),
((range(5;11) | pow(10;.)) as $n
| "\nNumber of palindromic primes <= \($n): \(count(emit_until(. >= $n; palindromic_primes)))" )- Output:
Palindromic primes <= 1000: 2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929 Number of palindromic primes <= 100000: 113 Number of palindromic primes <= 1000000: 113 Number of palindromic primes <= 10000000: 781 Number of palindromic primes <= 100000000: 781 Number of palindromic primes <= 1000000000: 5953 Number of palindromic primes <= 10000000000: 5953
Julia
Generator method.
using Primes
parray = [2, 3, 5, 7, 9, 11]
results = vcat(parray, filter(isprime, [100j + 10i + j for i in 0:9, j in 1:9]))
println(results)
- Output:
[2, 3, 5, 7, 9, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929]
Mathematica/Wolfram Language
Select[Range[999], PrimeQ[#] \[And] PalindromeQ[#] &]
- Output:
{2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929}
Nim
import strutils
const N = 999
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
func reversed(n: Positive): int =
var n = n.int
while n != 0:
result = 10 * result + n mod 10
n = n div 10
func isPalindromic(n: Positive): bool =
n == reversed(n)
var result: seq[int]
for n in 2..N:
if n.isPrime and n.isPalindromic:
result.add n
for i, n in result:
stdout.write ($n).align(3)
stdout.write if (i + 1) mod 10 == 0: '\n' else: ' '
- Output:
2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929
PARI/GP
naive
forprime(i = 2, 1000,
if( i == fromdigits( Vecrev( digits( i ) )) ,
print1( i, " " ) ) );- Output:
2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929
faster
p10( n ) = 10^n;
rew( m, c ) = {
local( t, n );
t = 0; n = m;
for(i=1, c,
t = t*10 + n%10;
n \= 10 );
return( t ) }
range( p, w, disp = 0 ) = {
local( w10, mi, mj, z, pal, q ,k = -1);
w10 = p * p10( w ) + p;
mi = p10( w \ 2 + 1 );
mj = p10( w \ 2 );
z = p10( w \ 2 - 1 ) - 1;
for( i = 0, z,
pal = rew( i, w\2 );
q = w10 + i * mi + pal;
for( j = 0, 9,
if( isprime(q + j * mj ),
k++;
if( disp,
if((k % 8)==0,print());
print1( q + j * mj, "\t") ) ) ) );
return( [ k+1, q + 9*mj ]); }
gener( disp=0 ) = {
local( t=[ 1, 3, 7, 9], s=5, x,start );
start = getabstime();
for( w = 1, 8,
for( i = 1, 20 - 2*w, print1(" "));
print1( p10(w*2));
for( i = 1, 4,
print1(".");
x=range(t[i], w*2, disp);
s+=x[1]; );
printf( "\t # %8d %8.3g [sec]\n",
, s, (getabstime()-start)/1000.0) )
}- Output:
100.... # 20 0.e-19 [sec]
10000.... # 113 0.e-19 [sec]
1000000.... # 781 0.e-19 [sec]
100000000.... # 5953 0.0620 [sec]
10000000000.... # 47995 0.718 [sec]
1000000000000.... # 401696 7.72 [sec]
100000000000000.... # 3438339 86.2 [sec]
Perl
#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Palindromic_primes
use warnings;
$_ == reverse and (1 x $_ ) !~ /^(11+)\1+$/ and print "$_ " for 2 .. 1e3;
- Output:
2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929
Phix
filter primes for palindromicness
function palindrome(string s) return s=reverse(s) end function for l=3 to 5 by 2 do integer limit = power(10,l) -- 1000 then 100000 sequence res = get_primes_le(limit) res = apply(true,sprintf,{{"%d"},res}) res = filter(res,palindrome) string s = join(shorten(res,"",5)) printf(1,"found %d < %,d: %s\n",{length(res),limit,s}) end for
- Output:
found 20 < 1,000: 2 3 5 7 11 ... 757 787 797 919 929 found 113 < 100,000: 2 3 5 7 11 ... 97379 97579 97879 98389 98689
filter palindromes for primality
sequence r = {} for l=2 to 3 do for i=1 to power(10,l) do string s = sprintf("%d",i) integer t = to_number(s&reverse(s[1..$-1])), u = to_number(s&reverse(s)) if is_prime(t) then r &= t end if if is_prime(u) then r &= u end if end for r = unique(r) string s = join(shorten(apply(true,sprintf,{{"%d"},r}),"",5)) printf(1,"found %d < %,d: %s\n",{length(r),power(10,l*2-1),s}) end for
Same output. Didn't actually test if this way was any faster, but expect it would be.
Python
A non-finite generator of palindromic primes – one of many approaches to solving this problem in Python.
'''Palindromic primes'''
from itertools import takewhile
# palindromicPrimes :: Generator [Int]
def palindromicPrimes():
'''An infinite stream of palindromic primes'''
def p(n):
s = str(n)
return s == s[::-1]
return (n for n in primes() if p(n))
# ------------------------- TEST -------------------------
def main():
'''Palindromic primes below 1000'''
print('\n'.join(
str(x) for x in takewhile(
lambda n: 1000 > n,
palindromicPrimes()
)
))
# ----------------------- GENERIC ------------------------
# primes :: [Int]
def primes():
''' Non finite sequence of prime numbers.
'''
n = 2
dct = {}
while True:
if n in dct:
for p in dct[n]:
dct.setdefault(n + p, []).append(p)
del dct[n]
else:
yield n
dct[n * n] = [n]
n = 1 + n
# MAIN ---
if __name__ == '__main__':
main()
- Output:
2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929
Quackery
eratosthenes and isprime are defined at Sieve of Eratosthenes#Quackery
[ [] swap
[ base share /mod
rot swap join swap
dup 0 = until ]
drop ] is digits ( n --> [ )
[ dup reverse = ] is palindromic ( [ --> b )
1000 eratosthenes
1000 times
[ i^ isprime if
[ i^ digits palindromic if
[ i^ echo sp ] ] ]- Output:
2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929
Raku
say "{+$_} matching numbers:\n{.batch(10)».fmt('%3d').join: "\n"}"
given (^1000).grep: { .is-prime and $_ eq .flip };
- Output:
20 matching numbers: 2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929
REXX
/*REXX program finds and displays palindromic primes in base ten for all N < 1,000.*/
parse arg hi cols . /*obtain optional argument from the CL.*/
if hi=='' | hi=="," then hi= 1000 /*Not specified? Then use the default.*/
if cols=='' | cols=="," then cols= 10 /* " " " " " " */
call genP /*build array of semaphores for primes.*/
w= max(8, length( commas(hi) ) ) /*max width of a number in any column. */
title= ' palindromic primes in base ten that are < ' commas(hi)
if cols>0 then say ' index │'center(title, 1 + cols*(w+1) )
if cols>0 then say '───────┼'center("", 1 + cols*(w+1), '─')
finds= 0; idx= 1 /*define # of palindromic primes & idx.*/
$= /*a list of palindromic primes (so far)*/
do j=1 for hi; if \!.j then iterate /*Is this number not prime? Then skip.*/ /* ◄■■■■■■■■ a filter. */
if j\==reverse(j) then iterate /*Not a palindromic prime? " " */ /* ◄■■■■■■■■ a filter. */
finds= finds + 1 /*bump the number of palindromic primes*/
if cols<0 then iterate /*Build the list (to be shown later)? */
$= $ right( commas(j), w) /*add a palindromic prime $ list.*/
if finds//cols\==0 then iterate /*have we populated a line of output? */
say center(idx, 7)'|' substr($, 2); $= /*display what we have so for (cols). */
idx= idx + cols /*bump the index count for the output*/
end /*j*/
if $\=='' then say center(idx, 7)'|' substr($, 2) /*possibly display residual output.*/
if cols>0 then say '───────┴'center("", 1 + cols*(w+1), '─')
say
say 'Found ' commas(finds) title
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 ?
/*──────────────────────────────────────────────────────────────────────────────────────*/
genP: !.= 0; hip= max(hi, copies(9,length(hi))) /*placeholders for primes (semaphores).*/
@.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */
!.2=1; !.3=1; !.5=1; !.7=1; !.11=1 /* " " " " flags. */
#=5; sq.#= @.# **2 /*number of primes so far; prime². */
/* [↓] generate more primes ≤ high.*/
do j=@.#+2 by 2 to hip /*find odd primes from here on. */
parse var j '' -1 _; if _==5 then iterate /*J ÷ by 5? (right digit).*/
if j//3==0 then iterate; if j//7==0 then iterate /*" " " 3? J ÷ by 7? */
do k=5 while sq.k<=j /* [↓] divide by the known odd primes.*/
if j // @.k == 0 then iterate j /*Is J ÷ X? Then not prime. ___ */
end /*k*/ /* [↑] only process numbers ≤ √ J */
#= #+1; @.#= j; sq.#= j*j; !.j= 1 /*bump # of Ps; assign next P; P²; P# */
end /*j*/; return
- output when using the default inputs:
index │ palindromic primes in base ten that are < 1,000 ───────┼─────────────────────────────────────────────────────────────────────────────────────────── 1 | 2 3 5 7 11 101 131 151 181 191 11 | 313 353 373 383 727 757 787 797 919 929 ───────┴─────────────────────────────────────────────────────────────────────────────────────────── Found 20 palindromic primes in base ten that are < 1,000
- output when using the input of: 100000
index │ palindromic primes in base ten that are < 100,000 ───────┼─────────────────────────────────────────────────────────────────────────────────────────── 1 | 2 3 5 7 11 101 131 151 181 191 11 | 313 353 373 383 727 757 787 797 919 929 21 | 10,301 10,501 10,601 11,311 11,411 12,421 12,721 12,821 13,331 13,831 31 | 13,931 14,341 14,741 15,451 15,551 16,061 16,361 16,561 16,661 17,471 41 | 17,971 18,181 18,481 19,391 19,891 19,991 30,103 30,203 30,403 30,703 51 | 30,803 31,013 31,513 32,323 32,423 33,533 34,543 34,843 35,053 35,153 61 | 35,353 35,753 36,263 36,563 37,273 37,573 38,083 38,183 38,783 39,293 71 | 70,207 70,507 70,607 71,317 71,917 72,227 72,727 73,037 73,237 73,637 81 | 74,047 74,747 75,557 76,367 76,667 77,377 77,477 77,977 78,487 78,787 91 | 78,887 79,397 79,697 79,997 90,709 91,019 93,139 93,239 93,739 94,049 101 | 94,349 94,649 94,849 94,949 95,959 96,269 96,469 96,769 97,379 97,579 111 | 97,879 98,389 98,689 ───────┴─────────────────────────────────────────────────────────────────────────────────────────── Found 113 palindromic primes in base ten that are < 100,000
Ring
load "stdlib.ring"
see "working..." + nl
see "Palindromic primes are:" + nl
row = 0
limit1 = 1000
limit2 = 100000
palindromicPrimes(limit1)
see "Found " + row + " palindromic primes" + nl + nl
see "palindromic primes that are < 100,000" + nl
palindromicPrimes(limit2)
see nl + "Found " + row + " palindromic primes that are < 100,000" + nl
see "done..." + nl
func palindromicPrimes(limit)
row = 0
for n = 1 to limit
strn = string(n)
if ispalindrome(strn) and isprime(n)
row = row + 1
see "" + n + " "
if row%5 = 0
see nl
ok
ok
next- Output:
working... Palindromic primes are: 2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929 Found 20 palindromic primes palindromic primes that are < 100,000 2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929 10301 10501 10601 11311 11411 12421 12721 12821 13331 13831 13931 14341 14741 15451 15551 16061 16361 16561 16661 17471 17971 18181 18481 19391 19891 19991 30103 30203 30403 30703 30803 31013 31513 32323 32423 33533 34543 34843 35053 35153 35353 35753 36263 36563 37273 37573 38083 38183 38783 39293 70207 70507 70607 71317 71917 72227 72727 73037 73237 73637 74047 74747 75557 76367 76667 77377 77477 77977 78487 78787 78887 79397 79697 79997 90709 91019 93139 93239 93739 94049 94349 94649 94849 94949 95959 96269 96469 96769 97379 97579 97879 98389 98689 Found 113 palindromic primes that are < 100,000 done...
RPL
≪ →STR → n
≪ ""
n SIZE 1 FOR j
n j DUP SUB +
-1 STEP STR→
≫ ≫ 'REVN' STO
≪ { } 2
DO
IF DUP DUP REVN == THEN SWAP OVER + SWAP END
NEXTPRIME
UNTIL DUP 1000 > END
DROP
≫ 'TASK' STO
{{out}
1: {2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929}
Rust
This includes a solution for the similar task Palindromic primes in base 16.
// [dependencies]
// primal = "0.3"
// radix_fmt = "1.0"
fn reverse(base: u64, mut n: u64) -> u64 {
let mut rev = 0;
while n > 0 {
rev = rev * base + n % base;
n /= base;
}
rev
}
fn palindromes(base: u64) -> impl std::iter::Iterator<Item = u64> {
let mut lower = 1;
let mut upper = base;
let mut next = 0;
let mut even = false;
std::iter::from_fn(move || {
next += 1;
if next == upper {
if even {
lower = upper;
upper *= base;
}
next = lower;
even = !even;
}
Some(match even {
true => next * upper + reverse(base, next),
_ => next * lower + reverse(base, next / base),
})
})
}
fn print_palindromic_primes(base: u64, limit: u64) {
let width = (limit as f64).log(base as f64).ceil() as usize;
let mut count = 0;
let columns = 80 / (width + 1);
println!("Base {} palindromic primes less than {}:", base, limit);
for p in palindromes(base)
.take_while(|x| *x < limit)
.filter(|x| primal::is_prime(*x))
{
count += 1;
print!(
"{:>w$}",
radix_fmt::radix(p, base as u8).to_string(),
w = width
);
if count % columns == 0 {
println!();
} else {
print!(" ");
}
}
if count % columns != 0 {
println!();
}
println!("Count: {}", count);
}
fn count_palindromic_primes(base: u64, limit: u64) {
let c = palindromes(base)
.take_while(|x| *x < limit)
.filter(|x| primal::is_prime(*x))
.count();
println!(
"Number of base {} palindromic primes less than {}: {}",
base, limit, c
);
}
fn main() {
print_palindromic_primes(10, 1000);
println!();
print_palindromic_primes(10, 100000);
println!();
count_palindromic_primes(10, 1000000000);
println!();
print_palindromic_primes(16, 500);
}
- Output:
Base 10 palindromic primes less than 1000:
2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929
Count: 20
Base 10 palindromic primes less than 100000:
2 3 5 7 11 101 131 151 181 191 313 353 373
383 727 757 787 797 919 929 10301 10501 10601 11311 11411 12421
12721 12821 13331 13831 13931 14341 14741 15451 15551 16061 16361 16561 16661
17471 17971 18181 18481 19391 19891 19991 30103 30203 30403 30703 30803 31013
31513 32323 32423 33533 34543 34843 35053 35153 35353 35753 36263 36563 37273
37573 38083 38183 38783 39293 70207 70507 70607 71317 71917 72227 72727 73037
73237 73637 74047 74747 75557 76367 76667 77377 77477 77977 78487 78787 78887
79397 79697 79997 90709 91019 93139 93239 93739 94049 94349 94649 94849 94949
95959 96269 96469 96769 97379 97579 97879 98389 98689
Count: 113
Number of base 10 palindromic primes less than 1000000000: 5953
Base 16 palindromic primes less than 500:
2 3 5 7 b d 11 101 151 161 191 1b1 1c1
Count: 13
Ruby
require 'prime'
p Prime.each(1000).select{|pr| pr.digits == pr.digits.reverse}
- Output:
[2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929]
S-BASIC
$constant FALSE = 0
$constant TRUE = 0FFFFH
rem - return true if n is palindromic, otherwise false
function ispalindrome(n = integer) = integer
var i, j, result = integer
var s = string
s = str$(n)
i = 2 rem - skip over leading sign or space
j = len(s)
while i < j and (mid(s,i,1)) = (mid(s,j,1)) do
begin
i = i + 1
j = j - 1
end
if (mid(s,i,1)) = (mid(s,j,1)) then
result = TRUE
else
result = FALSE
end = result
rem - return n mod m
function mod(n, m = integer) = integer
end = n - m * (n / m)
rem - return true if n is prime, otherwise false
function isprime(n = integer) = integer
var i, limit, result = integer
if n = 2 then
result = TRUE
else if (n < 2) or (mod(n,2) = 0) then
result = FALSE
else
begin
limit = int(sqr(n))
i = 3
while (i <= limit) and (mod(n, i) <> 0) do
i = i + 2
result = not (i <= limit)
end
end = result
rem - main code begins here
var i, count = integer
print "Looking up to 1000 for palindromic primes"
count = 0
for i = 2 to 1000
if isprime(i) then
if ispalindrome(i) then
begin
print using "##### ";i;
count = count + 1
if mod(count, 6) = 0 then print
end
next i
print
print count; " were found"
end
- Output:
Looking up to 1000 for palindromic primes
2 3 5 7 11 101
131 151 181 191 313 353
373 383 727 757 787 797
919 929
20 were found
Sidef
func palindromic_primes(upto, base = 10) {
var list = []
for (var p = 2; p <= upto; p = p.next_palindrome(base)) {
list << p if p.is_prime
}
return list
}
say palindromic_primes(1000)
for n in (1..10) {
var count = palindromic_primes(10**n).len
say "There are #{count} palindromic primes <= 10^#{n}"
}
- Output:
[2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929] There are 4 palindromic primes <= 10^1 There are 5 palindromic primes <= 10^2 There are 20 palindromic primes <= 10^3 There are 20 palindromic primes <= 10^4 There are 113 palindromic primes <= 10^5 There are 113 palindromic primes <= 10^6 There are 781 palindromic primes <= 10^7 There are 781 palindromic primes <= 10^8 There are 5953 palindromic primes <= 10^9 There are 5953 palindromic primes <= 10^10
Wren
import "./math" for Int
import "./fmt" for Fmt
var reversed = Fn.new { |n|
var rev = 0
while (n > 0) {
rev = rev * 10 + n % 10
n = (n/10).floor
}
return rev
}
var primes = Int.primeSieve(99999)
var pals = []
for (p in primes) {
if (p == reversed.call(p)) pals.add(p)
}
System.print("Palindromic primes under 1,000:")
var smallPals = pals.where { |p| p < 1000 }.toList
Fmt.tprint("$3d", smallPals, 10)
System.print("\n%(smallPals.count) such primes found.")
System.print("\nAdditional palindromic primes under 100,000:")
var bigPals = pals.where { |p| p >= 1000 }.toList
Fmt.tprint("$,6d", bigPals, 10)
System.print("\n%(bigPals.count) such primes found, %(pals.count) in all.")
- Output:
Palindromic primes under 1,000: 2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929 20 such primes found. Additional palindromic primes under 100,000: 10,301 10,501 10,601 11,311 11,411 12,421 12,721 12,821 13,331 13,831 13,931 14,341 14,741 15,451 15,551 16,061 16,361 16,561 16,661 17,471 17,971 18,181 18,481 19,391 19,891 19,991 30,103 30,203 30,403 30,703 30,803 31,013 31,513 32,323 32,423 33,533 34,543 34,843 35,053 35,153 35,353 35,753 36,263 36,563 37,273 37,573 38,083 38,183 38,783 39,293 70,207 70,507 70,607 71,317 71,917 72,227 72,727 73,037 73,237 73,637 74,047 74,747 75,557 76,367 76,667 77,377 77,477 77,977 78,487 78,787 78,887 79,397 79,697 79,997 90,709 91,019 93,139 93,239 93,739 94,049 94,349 94,649 94,849 94,949 95,959 96,269 96,469 96,769 97,379 97,579 97,879 98,389 98,689 93 such primes found, 113 in all.
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;
];
func Reverse(N);
int N, M;
[M:= 0;
repeat N:= N/10;
M:= M*10 + rem(0);
until N=0;
return M;
];
int Count, N;
[Count:= 0;
for N:= 1 to 1000-1 do
if N=Reverse(N) & IsPrime(N) then
[IntOut(0, N);
Count:= Count+1;
if rem(Count/10) = 0 then CrLf(0) else ChOut(0, 9\tab\);
];
]- Output:
2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929