Jump to content

Palindromic primes in base 16

From Rosetta Code
Palindromic primes in base 16 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 palindromic primes   n   in base 16,   where   n   <   50010

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) 500
   V h = hex(n)
   I h == reversed(h) & is_prime(n)
      print(h, end' ‘ ’)
print()
Output:
2 3 5 7 B D 11 101 151 161 191 1B1 1C1 

Action!

INCLUDE "H6:SIEVE.ACT"

BYTE FUNC Palindrome(CHAR ARRAY s)
  BYTE l,r

  l=1 r=s(0)
  WHILE l<r
  DO
    IF s(l)#s(r) THEN RETURN (0) FI
    l==+1 r==-1
  OD
RETURN (1)

PROC IntToHex(INT i CHAR ARRAY hex)
  CHAR ARRAY digits="0123456789ABCDEF"
  BYTE d

  hex(0)=0
  WHILE i#0
  DO
    d=i MOD 16
    hex(0)==+1
    hex(hex(0))=digits(d+1)
    i==/16
  OD
RETURN

BYTE Func IsPalindromicPrime(INT i CHAR ARRAY hex
  BYTE ARRAY primes)

  BYTE d
  INT rev,tmp

  IF primes(i)=0 THEN
    RETURN (0)
  FI

  IntToHex(i,hex)
  IF Palindrome(hex) THEN
    RETURN (1)
  FI
RETURN (0)

PROC Main()
  DEFINE MAX="499"
  BYTE ARRAY primes(MAX+1)
  INT i,count=[0]
  CHAR ARRAY hex(5)

  Put(125) PutE() ;clear the screen
  Sieve(primes,MAX+1)
  FOR i=2 TO MAX
  DO
    IF IsPalindromicPrime(i,hex,primes) THEN
      Print(hex) Put(32)
      count==+1
    FI
  OD
  PrintF("%EThere are %I palindromic primes",count)
RETURN
Output:

Screenshot from Atari 8-bit computer

2 3 5 7 B D 11 101 151 161 191 1B1 1C1

There are 13 palindromic primes

ALGOL 68

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
Output:
 2 3 5 7 B D 11 101 151 161 191 1B1 1C1

AppleScript

on isPrime(n)
    if ((n < 4) or (n is 5)) then return (n > 1)
    if ((n mod 2 = 0) or (n mod 3 = 0) or (n mod 5 = 0)) then return false
    repeat with i from 7 to (n ^ 0.5) div 1 by 30
        if ((n mod i = 0) or (n mod (i + 4) = 0) or (n mod (i + 6) = 0) or ¬
            (n mod (i + 10) = 0) or (n mod (i + 12) = 0) or (n mod (i + 16) = 0) or ¬
            (n mod (i + 22) = 0) or (n mod (i + 24) = 0)) then return false
    end repeat
    
    return true
end isPrime

on task()
    set digits to "0123456789ABCDEF"'s characters
    set output to {"2"} -- Take "2" as read.
    repeat with n from 3 to 499 by 2 -- All other primes are odd.
        if (isPrime(n)) then
            -- Only the number's hex digit /values/ are needed for testing.
            set vals to {}
            repeat until (n = 0)
                set vals's beginning to n mod 16
                set n to n div 16
            end repeat
            -- If they're palindromic, build a text representation and append this to the output.
            if (vals = vals's reverse) then
                set hex to digits's item ((vals's beginning) + 1)
                repeat with i from 2 to (count vals)
                    set hex to hex & digits's item ((vals's item i) + 1)
                end repeat
                set output's end to hex
            end if
        end if
    end repeat
    
    return output
end task

task()
Output:
{"2", "3", "5", "7", "B", "D", "11", "101", "151", "161", "191", "1B1", "1C1"}

Arturo

palindrome?: function [a][
    and? -> prime? a
         -> equal? digits.base:16 a reverse digits.base:16 a
]

print map select 1..500 => palindrome? 'x -> upper as.hex x
Output:
2 3 5 7 B D 11 101 151 161 191 1B1 1C1

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)
}
Output:
   2    3    5    7    B    D   11  101  151  161
 191  1B1  1C1
Palindromic primes 1-499: 13

C++

See C++ solution for task 'Palindromic Primes'.

Delphi

Works with: Delphi version 6.0


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 ShowPalindromePrimes16(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,16) then
	begin
	Inc(Cnt);
	S:=S+Format('%4X',[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   B
   D  11 101 151 161
 191 1B1 1C1 313 373
 3B3
Count=16
Elapsed Time: 2.116 ms.


EasyLang

fastfunc isprim num .
   i = 2
   while i <= sqrt num
      if num mod i = 0
         return 0
      .
      i += 1
   .
   return 1
.
func reverse s .
   while s > 0
      e = e * 16 + s mod 16
      s = s div 16
   .
   return e
.
digs$[] = strchars "0123456789abcdef"
func$ hex n .
   if n = 0
      return ""
   .
   return hex (n div 16) & digs$[n mod 16 + 1]
.
for i = 2 to 499
   if isprim i = 1
      if reverse i = i
         write hex i & " "
      .
   .
.
Output:
2 3 5 7 b d 11 101 151 161 191 1b1 1c1 

F#

This task uses Extensible Prime Generator (F#)

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 ""
Output:
2 3 5 7 b d 11 101 151 161 191 1b1 1c1

Factor

USING: kernel math.parser math.primes prettyprint sequences
sequences.extras ;

500 primes-upto [ >hex ] [ dup reverse = ] map-filter .
Output:
V{
    "2"
    "3"
    "5"
    "7"
    "b"
    "d"
    "11"
    "101"
    "151"
    "161"
    "191"
    "1b1"
    "1c1"
}


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
Output:
2  3  5  7  B  D  11  101  151  161  191  1B1  1C1

Encontrados 13 primos palindrómicos entre 2 y 499


Go

Library: Go-rcu
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.")
}
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.


J

   palindromic16=: (-: |.)@hfd@>
   hfd@> (#~ palindromic16) p: i. p:inv 500
2  
3  
5  
7  
b  
d  
11 
101
151
161
191
1b1
1c1

jq

Works with: 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.

# '''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;

The Task

# 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)
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

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

Mathematica /Wolfram Language

Giving the base 10 numbers and the base 16 numbers:

Select[Range[499], PrimeQ[#] \[And] PalindromeQ[IntegerDigits[#, 16]] &]
BaseForm[%, 16]
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

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(" ")
Output:
Found 13 palindromic primes in base 16:
2 3 5 7 b d 11 101 151 161 191 1b1 1c1

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;
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.

16 base put 
500 times
  [ i^ isprime if 
    [ i^ digits palindromic if 
      [ i^ echo sp ] ] ] 
base release
Output:
2 3 5 7 B D 11 101 151 161 191 1B1 1C1


Raku

Trivial modification of Palindromic primes task.

say "{+$_} matching numbers:\n{.batch(10)».fmt('%3X').join: "\n"}"
    given (^500).grep: { .is-prime and .base(16) eq .base(16).flip };
Output:
13 matching numbers:
  2   3   5   7   B   D  11 101 151 161
191 1B1 1C1

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
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

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
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...

Ruby

res = Prime.each(500).filter_map do |pr|
  str = pr.to_s(16)
  str if str == str.reverse
end
puts res.join(", ")
Output:
2, 3, 5, 7, b, d, 11, 101, 151, 161, 191, 1b1, 1c1

Rust

See Rust solution for task 'Palindromic Primes'.

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;
Output:
2 3 5 7 b d 11 101 151 161 191 1b1 1c1

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
}

var list = palindromic_primes(500, 16)

list.each {|p|
    say "#{'%3s' % p}_10 = #{'%3s' % p.base(16)}_16"
}
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

Library: Wren-math
Library: Wren-fmt
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.")
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

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.
");
]
Output:
2       3       5       7       B       D       11      101     151     161
191     1B1     1C1     
13 such numbers found.
Cookies help us deliver our services. By using our services, you agree to our use of cookies.