Palindromic primes in base 16
- Task
Find palindromic primes n in base 16, where n < 50010
ALGOL 68
<lang algol68>BEGIN # find primes that are palendromic in base 16 #
# sieve the primes to 499 #
PR read "primes.incl.a68" PR
[]BOOL prime = PRIMESIEVE 499;
# returns an array of the digits of n in the specified base #
PRIO DIGITS = 9;
OP DIGITS = ( INT n, INT base )[]INT:
IF INT v := ABS n;
v < base
THEN v # single dogit #
ELSE # multiple digits #
[ 1 : 10 ]INT result;
INT d pos := UPB result + 1;
INT v := ABS n;
WHILE v > 0 DO
result[ d pos -:= 1 ] := v MOD base;
v OVERAB base
OD;
result[ d pos : UPB result ]
FI # DIGITS # ;
# returns TRUE if the digits in d form a palindrome, FALSE otherwise #
OP PALINDROMIC = ( []INT d )BOOL:
BEGIN
INT left := LWB d, right := UPB d;
BOOL is palindromic := TRUE;
WHILE left < right AND is palindromic DO
is palindromic := d[ left ] = d[ right ];
left +:= 1;
right -:= 1
OD;
is palindromic
END;
# print the palendromic primes in the base 16 #
STRING base digits = "0123456789ABCDEF";
FOR n TO UPB prime DO
IF prime[ n ] THEN
# have a prime #
IF []INT d = n DIGITS 16;
PALINDROMIC d
THEN
# the prime is palindromic in base 16 #
print( ( " " ) );
FOR c FROM LWB d TO UPB d DO print( ( base digits[ d[ c ] + 1 ] ) ) OD
FI
FI
OD
END</lang>
- Output:
2 3 5 7 B D 11 101 151 161 191 1B1 1C1
AWK
<lang AWK>
- syntax: GAWK -f PALINDROMIC_PRIMES_IN_BASE_16.AWK
BEGIN {
start = 1
stop = 499
for (i=start; i<=stop; i++) {
hex = sprintf("%X",i)
if (is_prime(i) && hex == reverse(hex)) {
printf("%4s%1s",hex,++count%10?"":"\n")
}
}
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)
} </lang>
- Output:
2 3 5 7 B D 11 101 151 161 191 1B1 1C1 Palindromic primes 1-499: 13
F#
This task uses Extensible Prime Generator (F#) <lang fsharp> let rec fN g=[yield g%16; if g>15 then yield! fN(g/16)] primes32()|>Seq.takeWhile((>)500)|>Seq.filter(fun g->let g=fN g in List.rev g=g)|>Seq.iter(printf "%0x "); printfn "" </lang>
- Output:
2 3 5 7 b d 11 101 151 161 191 1b1 1c1
Factor
<lang factor>USING: kernel math.parser math.primes prettyprint sequences sequences.extras ;
500 primes-upto [ >hex ] [ dup reverse = ] map-filter .</lang>
- Output:
V{
"2"
"3"
"5"
"7"
"b"
"d"
"11"
"101"
"151"
"161"
"191"
"1b1"
"1c1"
}
FreeBASIC
<lang freebasic> Function isprime(num As Ulongint) As Boolean
For i As Integer = 2 To Sqr(num)
If (num Mod i = 0) Then Return False
Next i
Return True
End Function
Function reverse(Byval text As String) As String
Dim As String text2 = text
Dim As Integer x, lt = Len(text)
For x = 0 To lt Shr 1 - 1
Swap text2[x], text2[lt - x - 1]
Next x
Return text2
End Function
Dim As Integer inicio = 2, final = 499, cont = 0
For i As Integer = inicio To final
Dim As String hexi = Str(Hex(i))
If isprime(i) = True And hexi = reverse(hexi) Then
cont += 1
Print Hex(i); " ";
End If
Next i
Print !"\n\nEncontrados"; cont; " primos palindrómicos entre " & inicio & " y " & final Sleep </lang>
- Output:
2 3 5 7 B D 11 101 151 161 191 1B1 1C1 Encontrados 13 primos palindrómicos entre 2 y 499
Go
<lang go>package main
import (
"fmt" "rcu" "strconv" "strings"
)
func reverse(s string) string {
chars := []rune(s)
for i, j := 0, len(chars)-1; i < j; i, j = i+1, j-1 {
chars[i], chars[j] = chars[j], chars[i]
}
return string(chars)
}
func main() {
fmt.Println("Primes < 500 which are palindromic in base 16:")
primes := rcu.Primes(500)
count := 0
for _, p := range primes {
hp := strconv.FormatInt(int64(p), 16)
if hp == reverse(hp) {
fmt.Printf("%3s ", strings.ToUpper(hp))
count++
if count%5 == 0 {
fmt.Println()
}
}
}
fmt.Println("\n\nFound", count, "such primes.")
}</lang>
- Output:
Primes < 500 which are palindromic in base 16: 2 3 5 7 B D 11 101 151 161 191 1B1 1C1 Found 13 such primes.
jq
Works with gojq, the Go implementation of jq
This entry uses a generator that produces an unbounded stream of arrays of the form [dec, hex], where `dec` is the palindromic prime as a JSON number, and `hex` is the JSON string corresponding to its hexadecimal representation.
For a suitable implementation of `is_prime`, see e.g. Erdős-primes#jq. <lang jq>
- Preliminaries
def emit_until(cond; stream): label $out | stream | if cond then break $out else . end;
- decimal number to exploded hex array
def exploded_hex:
def stream: recurse(if . > 0 then ./16|floor else empty end) | . % 16 ; if . == 0 then [48] else [stream] | reverse | .[1:] | map(if . < 10 then 48 + . else . + 87 end) end;
</lang> The Task <lang jq># Output: a stream of [decimal, hexadecimal] values def palindromic_primes_in_base_16:
(2, (range(3; infinite; 2) | select(is_prime))) | exploded_hex as $hex |select( $hex | (. == reverse)) | [., ($hex|implode)] ;
emit_until(.[0] >= 500; palindromic_primes_in_base_16)</lang>
- Output:
[2,"2"] [3,"3"] [5,"5"] [7,"7"] [11,"b"] [13,"d"] [17,"11"] [257,"101"] [337,"151"] [353,"161"] [401,"191"] [433,"1b1"] [449,"1c1"]
Julia
<lang julia>using Primes
ispal(n, base) = begin dig = digits(n, base=base); dig == reverse(dig) end
palprimes(N, base=16) = [string(i, base=16) for i in primes(N) if ispal(i, base)]
foreach(s -> print(s, " "), palprimes(500, 16)) # 2 3 5 7 b d 11 101 151 161 191 1b1 1c1 </lang>
Mathematica/Wolfram Language
Giving the base 10 numbers and the base 16 numbers: <lang Mathematica>Select[Range[499], PrimeQ[#] \[And] PalindromeQ[IntegerDigits[#, 16]] &] BaseForm[%, 16]</lang>
- Output:
{2, 3, 5, 7, 11, 13, 17, 257, 337, 353, 401, 433, 449}
{Subscript[2, 16],Subscript[3, 16],Subscript[5, 16],Subscript[7, 16],Subscript[b, 16],Subscript[d, 16],Subscript[11, 16],Subscript[101, 16],Subscript[151, 16],Subscript[161, 16],Subscript[191, 16],Subscript[1b1, 16],Subscript[1c1, 16]}
Nim
<lang Nim>import strformat, strutils
func isPalindromic(s: string): bool =
for i in 1..s.len: if s[i-1] != s[^i]: return false result = true
func isPrime(n: Natural): bool =
if n < 2: return false if n mod 2 == 0: return n == 2 if n mod 3 == 0: return n == 3 var d = 5 while d * d <= n: if n mod d == 0: return false inc d, 2 if n mod d == 0: return false inc d, 4 return true
var list: seq[string]
for n in 0..<500:
let h = &"{n:x}"
if h.isPalindromic and n.isPrime: list.add h
echo "Found ", list.len, " palindromic primes in base 16:" echo list.join(" ")</lang>
- Output:
Found 13 palindromic primes in base 16: 2 3 5 7 b d 11 101 151 161 191 1b1 1c1
Perl
<lang perl> (1 x $_ ) !~ /^(11+)\1+$/ # test if prime and $h = sprintf "%x", $_ # convert to hex and $h eq reverse $h # palindromic? and print "$h " # much rejoicing
for 1..500;</lang>
- Output:
1 2 3 5 7 b d 11 101 151 161 191 1b1 1c1
Phix
with javascript_semantics function palindrome(string s) return s=reverse(s) end function sequence res = filter(apply(true,sprintf,{{"%x"},get_primes_le(500)}),palindrome) printf(1,"found %d: %s\n",{length(res),join(res)})
- Output:
found 13: 2 3 5 7 B D 11 101 151 161 191 1B1 1C1
Quackery
See Palindromic primes#Quackery for rest of code. This is a trivial modification.
<lang Quackery>16 base put 500 times
[ i^ isprime if
[ i^ digits palindromic if
[ i^ echo sp ] ] ]
base release</lang>
- Output:
2 3 5 7 B D 11 101 151 161 191 1B1 1C1
Raku
Trivial modification of Palindromic primes task. <lang perl6>say "{+$_} matching numbers:\n{.batch(10)».fmt('%3X').join: "\n"}"
given (^500).grep: { .is-prime and .base(16) eq .base(16).flip };</lang>
- Output:
13 matching numbers: 2 3 5 7 B D 11 101 151 161 191 1B1 1C1
REXX
<lang rexx>/*REXX program finds and displays hexadecimal palindromic primes for all N < 500. */ parse arg hi cols . /*obtain optional argument from the CL.*/ if hi== | hi=="," then hi= 500 /*Not specified? Then use the default.*/ if cols== | cols=="," then cols= 10 /* " " " " " " */ call genP /*build array of semaphores for primes.*/ w= 8 /*max width of a number in any column. */ title= ' palindromic primes in base 16 that are < ' 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.*/ $= /*hex palindromic primes list (so far).*/
do j=1 for hi; if \!.j then iterate /*J (decimal) not prime? Then skip.*/ /* ◄■■■■■■■■ a filter. */ x= d2x(j); if x\==reverse(x) then iterate /*Hex value not palindromic? " " */ /* ◄■■■■■■■■ a filter. */ finds= finds + 1 /*bump the number of palindromic primes*/ if cols<0 then iterate /*Build the list (to be shown later)? */ $= $ right( lowerHex(x), w) /*use a lowercase version of the hex #.*/ if finds//cols\==0 then iterate /*have we populated a line of output? */ say center(idx, 7)'│' substr($, 2); $= /*display what we have so far (cols). */ idx= idx + cols /*bump the index count for the output*/ end /*j*/
if $\== then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/ if cols>0 then say '───────┴'center("" , 1 + cols*(w+1), '─') say say 'Found ' finds title exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ lowerHex: return translate( arg(1), 'abcdef', "ABCDEF") /*convert hex chars──►lowercase.*/ /*──────────────────────────────────────────────────────────────────────────────────────*/ 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</lang>
- output when using the default inputs:
index │ palindromic primes in base 16 that are < 500 ───────┼─────────────────────────────────────────────────────────────────────────────────────────── 1 │ 2 3 5 7 b d 11 101 151 161 11 │ 191 1b1 1c1 ───────┴─────────────────────────────────────────────────────────────────────────────────────────── Found 13 palindromic primes in base 16 that are < 500
Ring
<lang ring> load "stdlib.ring" see "working..." + nl see "Palindromic primes in base 16:" + nl row = 0 limit = 500
for n = 1 to limit
hex = hex(n)
if ispalindrome(hex) and isprime(n)
see "" + upper(hex) + " "
row = row + 1
if row%5 = 0
see nl
ok
ok
next
see nl + "Found " + row + " palindromic primes in base 16" + nl see "done..." + nl </lang>
- Output:
working... Palindromic primes in base 16: 2 3 5 7 B D 11 101 151 161 191 1B1 1C1 Found 13 palindromic primes in base 16 done...
Rust
See Rust solution for task 'Palindromic Primes'.
Seed7
<lang seed7>$ include "seed7_05.s7i";
const func boolean: isPrime (in integer: number) is func
result
var boolean: prime is FALSE;
local
var integer: upTo is 0;
var integer: testNum is 3;
begin
if number = 2 then
prime := TRUE;
elsif odd(number) and number > 2 then
upTo := sqrt(number);
while number rem testNum <> 0 and testNum <= upTo do
testNum +:= 2;
end while;
prime := testNum > upTo;
end if;
end func;
const proc: main is func
local
var integer: n is 0;
var string: hex is "";
begin
for n range 2 to 499 do
if isPrime(n) then
hex := n radix 16;
if hex = reverse(hex) then
write(hex <& " ");
end if;
end if;
end for;
end func;</lang>
- Output:
2 3 5 7 b d 11 101 151 161 191 1b1 1c1
Sidef
<lang ruby>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
}
var list = palindromic_primes(500, 16)
list.each {|p|
say "#{'%3s' % p}_10 = #{'%3s' % p.base(16)}_16"
}</lang>
- Output:
2_10 = 2_16 3_10 = 3_16 5_10 = 5_16 7_10 = 7_16 11_10 = b_16 13_10 = d_16 17_10 = 11_16 257_10 = 101_16 337_10 = 151_16 353_10 = 161_16 401_10 = 191_16 433_10 = 1b1_16 449_10 = 1c1_16
Wren
<lang ecmascript>import "/math" for Int import "/fmt" for Conv, Fmt
System.print("Primes < 500 which are palindromic in base 16:") var primes = Int.primeSieve(500) var count = 0 for (p in primes) {
var hp = Conv.Itoa(p, 16)
if (hp == hp[-1..0]) {
Fmt.write("$3s ", hp)
count = count + 1
if (count % 5 == 0) System.print()
}
} System.print("\n\nFound %(count) such primes.")</lang>
- Output:
Primes < 500 which are palindromic in base 16: 2 3 5 7 B D 11 101 151 161 191 1B1 1C1 Found 13 such primes.
XPL0
<lang 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, Base); \Reverse order of digits in N for given Base int N, Base, M; [M:= 0; repeat N:= N/Base;
M:= M*Base + rem(0);
until N=0; return M; ];
int Count, N; [SetHexDigits(1); Count:= 0; for N:= 0 to 500-1 do
if IsPrime(N) & N=Reverse(N, 16) then
[HexOut(0, N);
Count:= Count+1;
if rem(Count/10) = 0 then CrLf(0) else ChOut(0, 9\tab\);
];
CrLf(0); IntOut(0, Count); Text(0, " such numbers found. "); ]</lang>
- Output:
2 3 5 7 B D 11 101 151 161 191 1B1 1C1 13 such numbers found.