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 #
INT max prime = 499; # sieve the primes to max prime # [ 1 : max prime ]BOOL prime; prime[ 1 ] := FALSE; prime[ 2 ] := TRUE; FOR i FROM 3 BY 2 TO UPB prime DO prime[ i ] := TRUE OD; FOR i FROM 4 BY 2 TO UPB prime DO prime[ i ] := FALSE OD; FOR i FROM 3 BY 2 TO ENTIER sqrt( max prime ) DO IF prime[ i ] THEN FOR s FROM i * i BY i + i TO UPB prime DO prime[ s ] := FALSE OD FI OD; # 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 max 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
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" }
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.
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
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 palindromic primes in base 16 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.*/ x= d2x(j); if x\==reverse(x) then iterate /*Hex value not palindromic? " " */ 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; s.#= @.# **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 divisible by 5? (right dig)*/ if j// 3==0 then iterate /*" " " 3? */ if j// 7==0 then iterate /*" " " 7? */ /* [↑] the above 3 lines saves time.*/ do k=5 while s.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; s.#= 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...
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
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.