Find palindromic numbers in both binary and ternary bases: Difference between revisions

From Rosetta Code
Content added Content deleted
No edit summary
Line 62: Line 62:


To speed this up, we directly generate palindromes to the base 3 and then check if these are also
To speed this up, we directly generate palindromes to the base 3 and then check if these are also
palindromes to the base 2. We use the fact that these palindromes (to the base 3) must have and odd number of digits (to the base 2 and 3) and that the number in the middle is a 1 (to the base 3).
palindromes to the base 2.
<lang Ada>with Ada.Text_IO, Base_Conversion;


<lang Ada>with Ada.Text_IO;use Ada.Text_IO;
procedure Clever is

procedure Palindromic is
type Long is range 0 .. 2**63-1;
type Int is mod 2**64; -- the values we will test don't exceed 64 bits
package BC is new Base_Conversion(Long);
function Palindrome (S : String) return Boolean is
function Reverse_Number (k : Int) return Int is --returns the symmetric representation of k (base-3)
(if S'Length < 2 then True
n : Int := 0;
p : Int := k;
elsif S(S'First) /= S(S'Last) then False
else Palindrome(S(S'First+1 .. S'Last-1)));
function Palindrome(N: Long; Base: Natural) return Boolean is
(Palindrome(BC.Image(N, Base =>Base)));
function Palindromize(S: String; Odd: Boolean) return String is
-- concatenates S and the reverse of S;
-- if Odd then the last character of S is not doubled
(if S'Length=1 then (if Odd then S else S & S) -- if not odd then double
else S(S'First) & Palindromize(S(S'First+1 .. S'Last), Odd) & S(S'First));
procedure Print(N: Long) is
package IIO is new Ada.Text_IO.Integer_IO(Long);
Bin: String := BC.Image(N, Base => 2);
Ter: String := BC.Image(N, Base => 3);
begin
begin
while p>0 loop
IIO.Put(N, Width => 12); -- prints N (Base 10)
Ada.Text_IO.Put_Line(": " & Bin & "(2)" & ", " & Ter & "(3)");
n := n * 3 + p mod 3;
p := p / 3;
end loop;
return n;
end reverse_number;
function Is_Pal2 (k : Int) return boolean is
new_k : Int := 0;
new_p : Int := k;
begin
while new_k < new_p loop
new_k := new_k * 2 + new_p mod 2;
new_p := new_p / 2;
end loop;
return new_p in new_k | new_k/2;
end Is_Pal2;
package BC is new Ada.Text_IO.Modular_IO (Int); -- allows us to express a variable of modular type in a given base
p3, n, bound, count_pal : int := 1;
procedure Print (n : Int) is
begin
BC.Put (n, Base=>2, Width=>65); BC.Put (n, Base=>3, Width=>45); New_Line;
end Print;
end Print;
begin
begin
Print (0); -- because 0 is the special case asked to be treated
for Half in Long(0) .. 10**6 loop
Process_Each_Power_Of_4 : for p in 1..31 loop -- 4^p musn't exceed 2^64
declare
while (3*p3+1)*p3 < 2**(2*p) loop p3 := 3*p3; end loop; -- adjust the power of the number to test so that the palindrom built with it has an odd number of digits in base-2
H: String := BC.Image(Half, Base => 3);
bound := 2**(2*p)/(3*p3);
Odd_Pal: String := Palindromize(H, Odd => True);
for k in Int range Int'max(p3/3, bound-1) .. Int'min (2*bound,p3-1) loop
Even_Pal: String := Palindromize(H, Odd => False);
n := (3*k+1)*p3 + Reverse_Number (k);
-- now Even_Pal and Odd_Pal are 3-palindromes
if Is_Pal2 (n) then
-- with Length(Even_Pal)=2*Length(H) and Length(Odd_Pal)=2*Length(H)-1
Print (n);
N, M: Long;
count_pal := count_pal + 1;
begin
if count_pal = 7 then
N := BC.Value(Odd_Pal, Base => 3); -- turn Odd_Pal into a number N
exit Process_Each_Power_Of_4;
if Palindrome(N, Base => 2) then -- check if N is als a 2-palindrome
Print(N); -- if yes, print N
end if;
end if;
end if;
end loop;
M := BC.Value(Even_Pal, Base => 3); -- same for Even_Pal and number M
end loop Process_Each_Power_Of_4;
if M /= N and then Palindrome(M, Base => 2) then
end Palindromic;</lang>
Print(M); -- If Half=0 then M=N=0; don't print 0 a second time!
end if;
end;
end loop;
end Clever;</lang>


{{out}}
{{out}}
On a modern machine, (core i5 for example), this code takes 6 seconds to give the seven first palindromes smaller than 2^64.
Even though this does not use any of the other tricks in some of the code from other languages, it generates the following solutions almost instantly.
<pre>

2#0# 3#0#
<pre> 0: 0(2), 0(3)
2#1# 3#1#
1: 1(2), 1(3)
2#1100111110011# 3#100010001#
6643: 1100111110011(2), 100010001(3)
2#101011011010110110101# 3#2200021200022#
1422773: 101011011010110110101(2), 2200021200022(3)
2#10100101010001010100101# 3#101012010210101#
5415589: 10100101010001010100101(2), 101012010210101(3)
2#1010100001100000100010000011000010101# 3#22122022220102222022122#
90396755477: 1010100001100000100010000011000010101(2), 22122022220102222022122(3)</pre>
2#10101001100110110110001110011011001110001101101100110010101# 3#2112200222001222121212221002220022112#


===Base Conversion===
===Base Conversion===

Revision as of 15:27, 24 August 2017

Task
Find palindromic numbers in both binary and ternary bases
You are encouraged to solve this task according to the task description, using any language you may know.
The task

Find and show (in decimal) the first six numbers (non-negative integers) that are palindromes in   both   base 2 and base 3.

Use zero (0) as the first number found, even though some other definitions ignore it.

Optionally, show the decimal number found in its binary and ternary form.

It's permissible to assume the first two numbers and simply list them.


See also
  •   Sequence A60792,   numbers that are palindromic in bases 2 and 3 on The On-Line Encyclopedia of Integer Sequences.



Ada

Simple Technique (Brute Force)

<lang Ada>with Ada.Text_IO, Base_Conversion;

procedure Brute is 

  type Long is range 0 .. 2**63-1; 
  package BC is new Base_Conversion(Long);
  
  function Palindrome (S : String) return Boolean is
     (if S'Length < 2 then True 
     elsif S(S'First) /= S(S'Last) then False 
     else Palindrome(S(S'First+1 .. S'Last-1)));
     
  function Palindrome(N: Long; Base: Natural) return Boolean is
     (Palindrome(BC.Image(N, Base =>Base)));

 package IIO is new Ada.Text_IO.Integer_IO(Long);

begin 

  for I in Long(1) .. 10**8 loop 
     if Palindrome(I, 3) and then Palindrome(I, 2) then

IIO.Put(I, Width => 12); -- prints I (Base 10) Ada.Text_IO.Put_Line(": " & BC.Image(I, Base => 2) & "(2)" & ", " & BC.Image(I, Base => 3) & "(3)"); -- prints I (Base 2 and Base 3) 

     end if;
     end loop;

end Brute;</lang>

Output:
           0: 0(2), 0(3)
           1: 1(2), 1(3)
        6643: 1100111110011(2), 100010001(3)
     1422773: 101011011010110110101(2), 2200021200022(3)
     5415589: 10100101010001010100101(2), 101012010210101(3)

For larger numbers, this is a bit slow.

Advanced Technique

To speed this up, we directly generate palindromes to the base 3 and then check if these are also palindromes to the base 2. We use the fact that these palindromes (to the base 3) must have and odd number of digits (to the base 2 and 3) and that the number in the middle is a 1 (to the base 3).

<lang Ada>with Ada.Text_IO;use Ada.Text_IO;

procedure Palindromic is 

 type Int is mod 2**64; -- the values we will test don't exceed 64 bits 
 
 function Reverse_Number (k : Int) return Int is --returns the symmetric representation of k (base-3)
   n : Int := 0;
   p : Int := k;
 begin
   while p>0 loop
     n := n * 3 + p mod 3;
     p := p / 3;
   end loop;
   return n;
 end reverse_number;
 
 function Is_Pal2 (k : Int) return boolean is
   new_k : Int := 0;
   new_p : Int := k;
 begin
   while new_k < new_p loop
     new_k := new_k * 2 + new_p mod 2;
     new_p := new_p / 2;
   end loop;
   return new_p in new_k | new_k/2;
 end Is_Pal2;
 
 package BC is new Ada.Text_IO.Modular_IO (Int); -- allows us to express a variable of modular type in a given base
 p3, n, bound, count_pal : int := 1;
 procedure Print (n : Int) is 
 begin
    BC.Put (n, Base=>2, Width=>65); BC.Put (n, Base=>3, Width=>45); New_Line;
 end Print;

begin 

 Print (0); -- because 0 is the special case asked to be treated
 Process_Each_Power_Of_4 : for p in 1..31 loop -- 4^p musn't exceed 2^64
   while (3*p3+1)*p3 < 2**(2*p) loop p3 := 3*p3; end loop;  -- adjust the power of the number to test so that the palindrom built with it has an odd number of digits in base-2
   bound := 2**(2*p)/(3*p3); 
   for k in Int range Int'max(p3/3, bound-1) .. Int'min (2*bound,p3-1) loop
     n := (3*k+1)*p3 + Reverse_Number (k);
     if Is_Pal2 (n) then
       Print (n);
       count_pal := count_pal + 1;
       if count_pal = 7 then 
         exit Process_Each_Power_Of_4;
       end if;
     end if;
   end loop;
 end loop Process_Each_Power_Of_4;

end Palindromic;</lang>

Output:

On a modern machine, (core i5 for example), this code takes 6 seconds to give the seven first palindromes smaller than 2^64. 

                                                             2#0#                                         3#0#
                                                             2#1#                                         3#1#
                                                 2#1100111110011#                                 3#100010001#
                                         2#101011011010110110101#                             3#2200021200022#
                                       2#10100101010001010100101#                           3#101012010210101#
                         2#1010100001100000100010000011000010101#                   3#22122022220102222022122#
   2#10101001100110110110001110011011001110001101101100110010101#     3#2112200222001222121212221002220022112#

===Base Conversion===

Both the brute force and the clever solution employ a generic package for base conversion. The function Image turns a number into a string, written as a base-something number (for something in 2 .. 16). The function Value performs the reverse operation. The same package is also used for the Ada solution of [Binary Digits [https://rosettacode.org/wiki/Binary_digits#Ada]].

<lang Ada>with Ada.Text_IO;

generic
   type Int is range <>;
package Base_Conversion is
   
   subtype Number_Base is Ada.Text_IO.Number_Base; -- integer range 2..16
   
   function Image(Num: Int; Base: Number_Base := 10) return String;
   -- returns a numeric representation of Num in the given Base;
   -- no leading zeroes, no spaces, no other symbols
   -- example: To_Sting(10, 2) returns "1010"
   
   function Value(Str: String; Base: Number_Base := 10) return Int;
   -- turns a string representation into an Int;
   
end Base_Conversion;</lang>

Finally, here is the implementation of the package.

<lang Ada>with Ada.Text_IO;

package body Base_Conversion is
   
   function Image(Num: Int; Base: Number_Base := 10) return String is
      S: String(1 .. 70); -- works for all bases and Num < 2**67
      Left:  Positive := S'First;
      Right: Positive := S'Last;
      package IIO is new Ada.Text_IO.Integer_IO(Int);

   begin
      IIO.Put(To => S, Item => Num, Base => Base); -- The conversion!
      -- Now S is a String with some spaces and "B#...#" somewhere,
      -- with B being the Base in decimal. We only need the "..." part.
      while S(Left) /= '#' loop
	 Left := Left + 1;
      end loop;
      while S(Right) /= '#' loop
	 Right := Right - 1;
      end loop;
      return S(Left+1 .. Right-1);
   end Image;
   
   function Value(Str: String; Base: Number_Base := 10) return Int is
      (Int'Value(Number_Base'Image(Base) & "#" & Str & "#"));
      
      
end Base_Conversion;</lang>

=={{header|C}}==
Per the observations made by the Ruby code (which are correct), the numbers must have odd number of digits in base 3 with a 1 at the middle, and must have odd number of digits in base 2.
<lang c>#include <stdio.h>
typedef unsigned long long xint;

int is_palin2(xint n)
{
	xint x = 0;
	if (!(n&1)) return !n;
	while (x < n) x = x<<1 | (n&1), n >>= 1;
	return n == x || n == x>>1;
}

xint reverse3(xint n)
{
	xint x = 0;
	while (n) x = x*3 + (n%3), n /= 3;
	return x;
}

void print(xint n, xint base)
{
	putchar(' ');
	// printing digits backwards, but hey, it's a palindrome
	do { putchar('0' + (n%base)), n /= base; } while(n);
	printf("(%lld)", base);
}

void show(xint n)
{
	printf("%llu", n);
	print(n, 2);
	print(n, 3);
	putchar('\n');
}

xint min(xint a, xint b) { return a < b ? a : b; }
xint max(xint a, xint b) { return a > b ? a : b; }

int main(void)
{
	xint lo, hi, lo2, hi2, lo3, hi3, pow2, pow3, i, n;
	int cnt;

	show(0);
	cnt = 1;

	lo = 0;
	hi = pow2 = pow3 = 1;

	while (1) {
		for (i = lo; i < hi; i++) {
			n = (i * 3 + 1) * pow3 + reverse3(i);
			if (!is_palin2(n)) continue;
			show(n);
			if (++cnt >= 7) return 0;
		}

		if (i == pow3)
			pow3 *= 3;
		else
			pow2 *= 4;

		while (1) {
			while (pow2 <= pow3) pow2 *= 4;

			lo2 = (pow2 / pow3 - 1) / 3;
			hi2 = (pow2 * 2 / pow3 - 1) / 3 + 1;
			lo3 = pow3 / 3;
			hi3 = pow3;

			if (lo2 >= hi3)
				pow3 *= 3;
			else if (lo3 >= hi2)
				pow2 *= 4;
			else {
				lo = max(lo2, lo3);
				hi = min(hi2, hi3);
				break;
			}
		}
	}
	return 0;
}</lang>
{{out}}
<pre>
0 0(2) 0(3)
1 1(2) 1(3)
6643 1100111110011(2) 100010001(3)
1422773 101011011010110110101(2) 2200021200022(3)
5415589 10100101010001010100101(2) 101012010210101(3)
90396755477 1010100001100000100010000011000010101(2) 22122022220102222022122(3)
381920985378904469 10101001100110110110001110011011001110001101101100110010101(2) 2112200222001222121212221002220022112(3)

Common Lisp

Unoptimized version <lang lisp>(defun palindromep (str) 

 (string-equal str (reverse str)) )

(loop 

 for i from 0
 with results = 0
 until (>= results 6)
 do
   (when (and (palindromep (format nil "~B" i))
              (palindromep (format nil "~3R" i)) )
     (format t "n:~a~:*  [2]:~B~:*  [3]:~3R~%" i)
     (incf results) ))

</lang>

Output:
n:0  [2]:0  [3]:0
n:1  [2]:1  [3]:1
n:6643  [2]:1100111110011  [3]:100010001
n:1422773  [2]:101011011010110110101  [3]:2200021200022
n:5415589  [2]:10100101010001010100101  [3]:101012010210101
n:90396755477 [2]:1010100001100000100010000011000010101 [3]:22122022220102222022122
n:381920985378904469 [2]:10101001100110110110001110011011001110001101101100110010101 [3]:2112200222001222121212221002220022112


D

Translation of: C

<lang d>import core.stdc.stdio, std.ascii;

bool isPalindrome2(ulong n) pure nothrow @nogc @safe { 

   ulong x = 0;
   if (!(n & 1))
       return !n;
   while (x < n) {
       x = (x << 1) | (n & 1);
       n >>= 1;
   }
   return n == x || n == (x >> 1);

}

ulong reverse3(ulong n) pure nothrow @nogc @safe { 

   ulong x = 0;
   while (n) {
       x = x * 3 + (n % 3);
       n /= 3;
   }
   return x;

}

void printReversed(ubyte base)(ulong n) nothrow @nogc { 

   ' '.putchar;
   do {
       digits[n % base].putchar;
       n /= base;
   } while(n);

   printf("(%d)", base);

}

void main() nothrow @nogc { 

   ulong top = 1, mul = 1, even = 0;
   uint count = 0;

   for (ulong i = 0; true; i++) {
       if (i == top) {
           if (even ^= 1)
               top *= 3;
           else {
               i = mul;
               mul = top;
           }
       }

       immutable n = i * mul + reverse3(even ? i / 3 : i);

       if (isPalindrome2(n)) {
           printf("%llu", n);
           printReversed!3(n);
           printReversed!2(n);
           '\n'.putchar;

           if (++count >= 6) // Print first 6.
               break;
       }
   }

}</lang>

Output:
0 0(3) 0(2)
1 1(3) 1(2)
6643 100010001(3) 1100111110011(2)
1422773 2200021200022(3) 101011011010110110101(2)
5415589 101012010210101(3) 10100101010001010100101(2)
90396755477 22122022220102222022122(3) 1010100001100000100010000011000010101(2)

Elixir

Translation of: Ruby
Works with: Elixir version 1.3

<lang elixir>defmodule Palindromic do 

 import Integer, only: [is_odd: 1]
 
 def number23 do
   Stream.concat([0,1], Stream.unfold(1, &number23/1))
 end
 def number23(i) do
   n3 = Integer.to_string(i,3)
   n = (n3 <> "1" <> String.reverse(n3)) |> String.to_integer(3)
   n2 = Integer.to_string(n,2)
   if is_odd(String.length(n2)) and n2 == String.reverse(n2),
     do:   {n, i+1},
     else: number23(i+1)
 end
 
 def task do
   IO.puts "     decimal          ternary                          binary"
   number23()
   |> Enum.take(6)
   |> Enum.each(fn n ->
     n3 = Integer.to_charlist(n,3) |> :string.centre(25)
     n2 = Integer.to_charlist(n,2) |> :string.centre(39)
     :io.format "~12w ~s ~s~n", [n, n3, n2]
   end)
 end

end

Palindromic.task</lang>

Output:
     decimal          ternary                          binary
           0             0                                0                   
           1             1                                1                   
        6643         100010001                      1100111110011             
     1422773       2200021200022                101011011010110110101         
     5415589      101012010210101              10100101010001010100101        
 90396755477  22122022220102222022122   1010100001100000100010000011000010101

FreeBASIC

As using a brute force approach will be too slow for this task we instead create ternary palindromes and check if they are also binary palindromes using the optimizations which have been noted in some of the other language solutions : <lang freebasic>' FB 1.05.0 Win64

'converts decimal "n" to its ternary equivalent Function Ter(n As UInteger) As String 

 If n = 0 Then Return "0"
 Dim result As String = ""
 While n > 0
   result = (n Mod 3) & result
   n \= 3
 Wend
 Return result

End Function

' check if a binary or ternary numeric string "s" is palindromic Function isPalindromic(s As String) As Boolean 

 ' we can assume "s" will have an odd number of digits, so can ignore the middle digit
 Dim As UInteger length = Len(s) 
 For i As UInteger = 0 To length \ 2 - 1
   If s[i] <> s[length - 1 - i] Then Return False
 Next
 Return True

End Function

' print a number which is both a binary and ternary palindrome in all three bases Sub printPalindrome(n As UInteger) 

 Print "Decimal : "; Str(n)
 Print "Binary  : "; bin(n)
 Print "Ternary : "; ter(n)
 Print

End Sub

' create a ternary palindrome whose left part is the ternary equivalent of "n" and return its decimal equivalent Function createPalindrome3(n As UInteger) As UInteger 

 Dim As String ternary = Ter(n)
 Dim As UInteger power3 = 1, sum = 0, length = Len(ternary)
 For i As Integer = 0 To Length - 1 right part of palindrome is mirror image of left part
   If ternary[i] > 48 Then   i.e. non-zero
     sum += (ternary[i] - 48) * power3
   End If
   power3 *= 3
 Next
 sum += power3  middle digit must be 1
 power3 *= 3
 sum += n * power3   value of left part is simply "n" multiplied by appropriate power of 3 
 Return sum

End Function

Dim t As Double = timer Dim As UInteger i = 1, p3, count = 2 Dim As String binStr Print "The first 6 numbers which are palindromic in both binary and ternary are :" Print ' we can assume the first two palindromic numbers as per the task description printPalindrome(0) 0 is a palindrome in all 3 bases printPalindrome(1) 1 is a palindrome in all 3 bases Do 

 p3 = createPalindrome3(i)
 If p3 Mod 2 > 0 Then ' cannot be even as binary equivalent would end in zero
   binStr = Bin(p3)   Bin function is built into FB
   If Len(binStr) Mod 2 = 1 Then   binary palindrome must have an odd number of digits
     If isPalindromic(binStr) Then
       printPalindrome(p3)
       count += 1
     End If
   End If 
 End If
 i += 1

Loop Until count = 6 Print "Took "; Print Using "#.###"; timer - t; Print " seconds on i3 @ 2.13 GHz" Print "Press any key to quit" Sleep</lang>

Output:
The first 6 numbers which are palindromic in both binary and ternary are :

Decimal : 0
Binary  : 0
Ternary : 0

Decimal : 1
Binary  : 1
Ternary : 1

Decimal : 6643
Binary  : 1100111110011
Ternary : 100010001

Decimal : 1422773
Binary  : 101011011010110110101
Ternary : 2200021200022

Decimal : 5415589
Binary  : 10100101010001010100101
Ternary : 101012010210101

Decimal : 90396755477
Binary  : 1010100001100000100010000011000010101
Ternary : 22122022220102222022122

Took 0.761 seconds on i3 @ 2.13 GHz

Haskell

<lang haskell>import Numeric (showIntAtBase, readInt) import Data.List (transpose, unwords) import Data.Char (intToDigit, isDigit, digitToInt)

-- Member of ternary palindrome series. base3Palindrome :: Integer -> String base3Palindrome n = 

 let s = showBase 3 n
 in s ++ ('1' : reverse s)

-- Test for binary palindrome. isBinPal :: Integer -> Bool isBinPal n = 

 let s = showIntAtBase 2 intToDigit n []
     (q, r) = quotRem (length s) 2
 in (r == 1) && drop (succ q) s == reverse (take q s)

-- Integer value of ternary string. readBase3 :: String -> Integer readBase3 s = 

 let [(n, _)] = readInt 3 isDigit digitToInt s
 in n

showBase :: Integer -> Integer -> String showBase base n = showIntAtBase base intToDigit n []

solutions :: [Integer] solutions = 

 [0, 1] ++ take 4 (filter isBinPal ((readBase3 . base3Palindrome) <$> [1 ..]))

main :: IO () main = 

 mapM_
   putStrLn
   (unwords <$>
    transpose
      (((<$>) =<< flip justifyLeft ' ' . succ . maximum . (length <$>)) <$>
       transpose
         (["Decimal", "Ternary", "Binary"] :
          ((([show, showBase 3, showBase 2] <*>) . pure) <$> solutions))))
 where
   justifyLeft n c s = take n (s ++ replicate n c)</lang>
Output:
Decimal      Ternary                  Binary                                
0            0                        0                                     
1            1                        1                                     
6643         100010001                1100111110011                         
1422773      2200021200022            101011011010110110101                 
5415589      101012010210101          10100101010001010100101               
90396755477  22122022220102222022122  1010100001100000100010000011000010101

J

Solution: <lang j>isPalin=: -: |. NB. check if palindrome toBase=: #.inv"0 NB. convert to base(s) in left arg filterPalinBase=: ] #~ isPalin@toBase/ NB. palindromes for base(s) find23Palindromes=: 3 filterPalinBase 2 filterPalinBase ] NB. palindromes in both base 2 and base 3

showBases=: [: ;:inv@|: <@({&'0123456789ABCDEFGH')@toBase/ NB. display numbers in bases

NB.*getfirst a Adverb to get first y items returned by verb u getfirst=: adverb define 

 100000x u getfirst y

 res=. 0$0
 start=. 0
 blk=. i.x
 whilst. y > #res do.
   tmp=. u start + blk
   start=. start + x
   res=. res, tmp
 end.
 y{.res

)</lang> Usage: <lang j> find23Palindromes i. 2e6 NB. binary & ternary palindromes less than 2,000,000 0 1 6643 1422773 

  10 2 3 showBases find23Palindromes getfirst 6  NB. first 6 binary & ternary palindomes

0 0 0 1 1 1 6643 1100111110011 100010001 1422773 101011011010110110101 2200021200022 5415589 10100101010001010100101 101012010210101 90396755477 1010100001100000100010000011000010101 22122022220102222022122 </lang>

Java

This takes a while to get to the 6th one (I didn't time it precisely, but it was less than 2 hours on an i7) <lang java>public class Pali23 { public static boolean isPali(String x){ return x.equals(new StringBuilder(x).reverse().toString()); }

public static void main(String[] args){

for(long i = 0, count = 0; count < 6;i++){ if((i & 1) == 0 && (i != 0)) continue; //skip non-zero evens, nothing that ends in 0 in binary can be in this sequence //maybe speed things up through short-circuit evaluation by putting toString in the if //testing up to 10M, base 2 has slightly fewer palindromes so do that one first if(isPali(Long.toBinaryString(i)) && isPali(Long.toString(i, 3))){ System.out.println(i + ", " + Long.toBinaryString(i) + ", " + Long.toString(i, 3)); count++; } } } }</lang>

Output:
0, 0, 0
1, 1, 1
6643, 1100111110011, 100010001
1422773, 101011011010110110101, 2200021200022
5415589, 10100101010001010100101, 101012010210101
90396755477, 1010100001100000100010000011000010101, 22122022220102222022122

JavaScript

ES6

Translation of: Haskell

<lang JavaScript>(() => { 

   'use strict';

   // GENERIC FUNCTIONS

   // range :: Int -> Int -> [Int]
   const range = (m, n) =>
       Array.from({
           length: Math.floor(n - m) + 1
       }, (_, i) => m + i);

   // compose :: (b -> c) -> (a -> b) -> (a -> c)
   const compose = (f, g) => x => f(g(x));

   // listApply :: [(a -> b)] -> [a] -> [b]
   const listApply = (fs, xs) =>
       [].concat.apply([], fs.map(f =>
       [].concat.apply([], xs.map(x => [f(x)]))));

   // pure :: a -> [a]
   const pure = x => [x];

   // curry :: Function -> Function
   const curry = (f, ...args) => {
       const go = xs => xs.length >= f.length ? (f.apply(null, xs)) :
           function () {
               return go(xs.concat([].slice.apply(arguments)));
           };
       return go([].slice.call(args, 1));
   };

   // transpose :: a -> a
   const transpose = xs =>
       xs[0].map((_, iCol) => xs.map(row => row[iCol]));

   // reverse :: [a] -> [a]
   const reverse = xs =>
       typeof xs === 'string' ? (
           xs.split()
           .reverse()
           .join()
       ) : xs.slice(0)
       .reverse();

   // take :: Int -> [a] -> [a]
   const take = (n, xs) => xs.slice(0, n);

   // drop :: Int -> [a] -> [a]
   const drop = (n, xs) => xs.slice(n);

   // maximum :: [a] -> a
   const maximum = xs =>
       xs.reduce((a, x) => (x > a || a === undefined ? x : a), undefined);

   // quotRem :: Integral a => a -> a -> (a, a)
   const quotRem = (m, n) => [Math.floor(m / n), m % n];

   // length :: [a] -> Int
   const length = xs => xs.length;

   // justifyLeft :: Int -> Char -> Text -> Text
   const justifyLeft = (n, cFiller, strText) =>
       n > strText.length ? (
           (strText + cFiller.repeat(n))
           .substr(0, n)
       ) : strText;

   // unwords :: [String] -> String
   const unwords = xs => xs.join(' ');

   // unlines :: [String] -> String
   const unlines = xs => xs.join('\n');



   // BASES AND PALINDROMES

   // show, showBinary, showTernary :: Int -> String
   const show = n => n.toString(10);
   const showBinary = n => n.toString(2);
   const showTernary = n => n.toString(3);

   // readBase3 :: String -> Int
   const readBase3 = s => parseInt(s, 3);

   // base3Palindrome :: Int -> String
   const base3Palindrome = n => {
       const s = showTernary(n);
       return s + '1' + reverse(s);
   };

   // isBinPal :: Int -> Bool
   const isBinPal = n => {
       const
           s = showBinary(n),
           [q, r] = quotRem(s.length, 2);
       return (r !== 0) && drop(q + 1, s) === reverse(take(q, s));
   };

   // solutions :: [Int]
   const solutions = [0, 1].concat(range(1, 10E5)
       .map(compose(readBase3, base3Palindrome))
       .filter(isBinPal));

   // TABULATION

   // cols :: Int
   const cols = transpose(
       [
           ['Decimal', 'Ternary', 'Binary']
       ].concat(
           solutions.map(
               compose(
                   xs => listApply([show, showTernary, showBinary], xs),
                   pure
               )
           )
       )
   );

   return unlines(
       transpose(cols.map(col => col.map(
           curry(justifyLeft)(maximum(col.map(length)) + 1, ' ')
       )))
       .map(unwords));

})();</lang>

Output:
Decimal      Ternary                  Binary                                
0            0                        0                                     
1            1                        1                                     
6643         100010001                1100111110011                         
1422773      2200021200022            101011011010110110101                 
5415589      101012010210101          10100101010001010100101               
90396755477  22122022220102222022122  1010100001100000100010000011000010101

Julia

<lang julia> function ispalindrome(a::String) 

  rst = true
  i = 0
  while rst && i < div(length(a), 2)
     i += 1
     rst = a[i] == a[end + 1 - i]
  end
  return rst

end

function ispalinbase23(n::Integer) 

  base2 = base(2, n)
  base3 = base(3, n)
  return ispalindrome(base2) && ispalindrome(base3)

end

i = n = 0 while i < 6 

  if ispalinbase23(n)
     println(n)
     i += 1
  end
  n += 1

end </lang>

Kotlin

Translation of: FreeBASIC

<lang scala>// version 1.0.5-2

/** converts decimal 'n' to its ternary equivalent */ fun Long.toTernaryString(): String = when { 

   this < 0L  -> throw IllegalArgumentException("negative numbers not allowed")  
   this == 0L -> "0"
   else   -> {
       var result = ""
       var n = this
       while (n > 0) {
           result += n % 3
           n /= 3
       }
       result.reversed()
   }

}

/** wraps java.lang.Long.toBinaryString in a Kotlin extension function */ fun Long.toBinaryString(): String = java.lang.Long.toBinaryString(this)

/** check if a binary or ternary numeric string 's' is palindromic */ fun isPalindromic(s: String): Boolean = (s == s.reversed())

/** print a number which is both a binary and ternary palindrome in all three bases */ fun printPalindrome(n: Long) { 

   println("Decimal : $n")
   println("Binary  : ${n.toBinaryString()}")
   println("Ternary : ${n.toTernaryString()}")
   println()

}

/** create a ternary palindrome whose left part is the ternary equivalent of 'n' and return its decimal equivalent */ fun createPalindrome3(n: Long): Long { 

   val ternary = n.toTernaryString()
   var power3 = 1L
   var sum = 0L
   val length = ternary.length
   for (i in 0 until length) {  // right part of palindrome is mirror image of left part
       if (ternary[i] > '0') sum += (ternary[i].toInt() - 48) * power3
       power3 *= 3L
   }
   sum += power3 // middle digit must be 1
   power3 *= 3L
   sum += n * power3  // value of left part is simply 'n' multiplied by appropriate power of 3 
   return sum

}

fun main(args: Array<String>) { 

   var i = 1L
   var p3: Long
   var count = 2
   var binStr: String
   println("The first 6 numbers which are palindromic in both binary and ternary are:\n")
   // we can assume the first two palindromic numbers as per the task description
   printPalindrome(0L)  // 0 is a palindrome in all 3 bases
   printPalindrome(1L)  // 1 is a palindrome in all 3 bases
  
   do {
       p3 = createPalindrome3(i)
       if (p3 % 2 > 0L)  { // cannot be even as binary equivalent would end in zero
           binStr = p3.toBinaryString()            
           if (binStr.length % 2 == 1) { // binary palindrome must have an odd number of digits
               if (isPalindromic(binStr)) {
                   printPalindrome(p3)
                   count++
               }
           }      
       } 
       i++      
   } 
   while (count < 6)

}</lang>

Output:
The first 6 numbers which are palindromic in both binary and ternary are:

Decimal : 0
Binary  : 0
Ternary : 0

Decimal : 1
Binary  : 1
Ternary : 1

Decimal : 6643
Binary  : 1100111110011
Ternary : 100010001

Decimal : 1422773
Binary  : 101011011010110110101
Ternary : 2200021200022

Decimal : 5415589
Binary  : 10100101010001010100101
Ternary : 101012010210101

Decimal : 90396755477
Binary  : 1010100001100000100010000011000010101
Ternary : 22122022220102222022122

Mathematica

<lang Mathematica>palindromify3[n_] := 

   Block[{digits},
     If[Divisible[n, 3], {},
        digits = IntegerDigits[n, 3];
        FromDigits[#, 3] & /@ 
           {Join[Reverse[digits], digits], Join[Reverse[Rest[digits]], {First[digits]}, Rest[digits]]}
     ]
   ];

base2PalindromeQ[n_] := IntegerDigits[n, 2] === Reverse[IntegerDigits[n, 2]];

Select[Flatten[palindromify3 /@ Range[1000000]], base2PalindromeQ]

Output:
{1, 6643, 1422773, 5415589, 90396755477}</lang>

PARI/GP

<lang parigp>check(n)={ \\ Check for 2n+1-digit palindromes in base 3 

 my(N=3^n);
 forstep(i=N+1,2*N,[1,2],
   my(base2,base3=digits(i,3),k);
   base3=concat(Vecrev(base3[2..n+1]), base3);
   k=subst(Pol(base3),'x,3);
   base2=binary(k);
   if(base2==Vecrev(base2), print1(", "k))
 )

}; print1("0, 1"); for(i=1,11,check(i))</lang>

Output:
0, 1, 6643, 1422773, 5415589, 90396755477

Perl

<lang perl>use ntheory qw/fromdigits todigitstring/;

print "0 0 0\n"; # Hard code the 0 result for (0..2e5) { 

 # Generate middle-1-palindrome in base 3.
 my $pal = todigitstring($_, 3);
 my $b3 = $pal . "1" . reverse($pal);
 # Convert base 3 number to base 2
 my $b2 = todigitstring(fromdigits($b3, 3), 2);
 # Print results (including base 10) if base-2 palindrome
 print fromdigits($b2,2),"  $b3  $b2\n"   if $b2 eq reverse($b2);

}</lang>

Output:
0  0  0
1  1  1
6643  100010001  1100111110011
1422773  2200021200022  101011011010110110101
5415589  101012010210101  10100101010001010100101
90396755477  22122022220102222022122  1010100001100000100010000011000010101

Perl 6

Instead of searching for numbers that are palindromes in one base then checking the other, generate palindromic trinary numbers directly, then check to see if they are also binary palindromes (with additional simplifying constraints as noted in other entries). Outputs the list in decimal, binary and trinary.

<lang perl6>constant palindromes = 0, 1, |gather for 1 .. * -> $p { 

   my $pal = $p.base(3);
   my $n = :3($pal ~ '1' ~ $pal.flip);
   next if $n %% 2;
   my $b2 = $n.base(2);
   next if $b2.chars %% 2;
   next unless $b2 eq $b2.flip;
   take $n;

}

printf "%d, %s, %s\n", $_, .base(2), .base(3) for palindromes[^6];</lang>

Output:
0, 0, 0
1, 1, 1
6643, 1100111110011, 100010001
1422773, 101011011010110110101, 2200021200022
5415589, 10100101010001010100101, 101012010210101
90396755477, 1010100001100000100010000011000010101, 22122022220102222022122

Python

<lang python>from itertools import islice

digits = "0123456789abcdefghijklmnopqrstuvwxyz"

def baseN(num,b): 

 if num == 0: return "0"
 result = ""
 while num != 0:
   num, d = divmod(num, b)
   result += digits[d]
 return result[::-1] # reverse

def pal2(num): 

   if num == 0 or num == 1: return True
   based = bin(num)[2:]
   return based == based[::-1]

def pal_23(): 

   yield 0
   yield 1
   n = 1
   while True:
       n += 1
       b = baseN(n, 3)
       revb = b[::-1]
       #if len(b) > 12: break
       for trial in ('{0}{1}'.format(b, revb), '{0}0{1}'.format(b, revb),
                     '{0}1{1}'.format(b, revb), '{0}2{1}'.format(b, revb)):
           t = int(trial, 3)
           if pal2(t):
               yield t

for pal23 in islice(pal_23(), 6): 

   print(pal23, baseN(pal23, 3), baseN(pal23, 2))</lang>
Output:
0 0 0
1 1 1
6643 100010001 1100111110011
1422773 2200021200022 101011011010110110101
5415589 101012010210101 10100101010001010100101
90396755477 22122022220102222022122 1010100001100000100010000011000010101

Racket

<lang racket>#lang racket (require racket/generator)

(define (digital-reverse/base base N) 

 (define (inr n r)
   (if (zero? n) r (inr (quotient n base) (+ (* r base) (modulo n base)))))
 (inr N 0))

(define (palindrome?/base base N) 

 (define (inr? n m)
   (if (= n 0)
       (= m N)
       (inr? (quotient n base) (+ (* m base) (modulo n base)))))
 (inr? N 0))

(define (palindrome?/3 n) 

 (palindrome?/base 3 n))

(define (b-palindromes-generator b) 

 (generator
  ()
  ;; it's a bit involved getting the initial palindroms, so we do them manually
  (for ((p (in-range b))) (yield p))
  (let loop ((rhs 1) (mx-rhs b) (mid #f) (mx-rhs*b (* b b)))
    (cond
      [(= rhs mx-rhs)
       (cond
         [(not mid) (loop (quotient mx-rhs b) mx-rhs 0 mx-rhs*b)]
         [(zero? mid) (loop mx-rhs mx-rhs*b #f (* mx-rhs*b b))])]
      [else
       (define shr (digital-reverse/base b rhs))
       (cond
         [(not mid)
          (yield (+ (* rhs mx-rhs) shr))
          (loop (add1 rhs) mx-rhs #f mx-rhs*b)]
         [(= mid (- b 1))
          (yield (+ (* rhs mx-rhs*b) (* mid mx-rhs) shr))
          (loop (+ 1 rhs) mx-rhs 0 mx-rhs*b)]
         [else
          (yield (+ (* rhs mx-rhs*b) (* mid mx-rhs) shr))
          (loop rhs mx-rhs (add1 mid) mx-rhs*b)])]))))

(define (number->string/base n b) 

 (define (inr acc n)
   (if (zero? n) acc
       (let-values (((q r) (quotient/remainder n b)))
         (inr (cons (number->string r) acc) q))))
 (if (zero? n) "0" (apply string-append (inr null n))))

(module+ main 

 (for ((n (sequence-filter palindrome?/3 (in-producer (b-palindromes-generator 2))))
       (i (in-naturals))
       #:final (= i 5))
   (printf "~a: ~a_10 ~a_3 ~a_2~%"
           (~a #:align 'right #:min-width  3 (add1 i))
           (~a #:align 'right #:min-width 11 n)
           (~a #:align 'right #:min-width 23 (number->string/base n 3))
           (~a #:align 'right #:min-width 37 (number->string/base n 2)))))

(module+ test 

 (require rackunit)
 (check-true  (palindrome?/base 2 #b0))
 (check-true  (palindrome?/base 2 #b10101))
 (check-false (palindrome?/base 2 #b1010))
 (define from-oeis:A060792
   (list 0 1 6643 1422773 5415589 90396755477 381920985378904469
         1922624336133018996235 2004595370006815987563563
         8022581057533823761829436662099))
 (check-match from-oeis:A060792
              (list (? (curry palindrome?/base 2)
                       (? (curry palindrome?/base 3))) ...))
 
 (check-eq? (digital-reverse/base 2 #b0)        #b0)
 (check-eq? (digital-reverse/base 2 #b1)        #b1)
 (check-eq? (digital-reverse/base 2 #b10)      #b01)
 (check-eq? (digital-reverse/base 2 #b1010)  #b0101)
 
 (check-eq? (digital-reverse/base 10 #d0)       #d0)
 (check-eq? (digital-reverse/base 10 #d1)       #d1)
 (check-eq? (digital-reverse/base 10 #d10)     #d01)
 (check-eq? (digital-reverse/base 10 #d1010) #d0101)
 
 (define pg ((b-palindromes-generator 2)))
 (check-match
  (map (curryr number->string 2) (for/list ((i 16) (p (in-producer (b-palindromes-generator 2)))) p))
  (list "0" "1" "11" "101" "111" "1001" "1111" "10001" "10101" "11011"
        "11111" "100001" "101101" "110011" "111111" "1000001")))</lang>
Output:
  1:           0_10                       0_3                                     0_2
  2:           1_10                       1_3                                     1_2
  3:        6643_10               100010001_3                         1100111110011_2
  4:     1422773_10           2200021200022_3                 101011011010110110101_2
  5:     5415589_10         101012010210101_3               10100101010001010100101_2
  6: 90396755477_10 22122022220102222022122_3 1010100001100000100010000011000010101_2

REXX

version 1

Programming note:   This version is quite a bit faster than the previous REXX program entered.

For this REXX program, a few deterministic assumptions were made:

  •   for the requirement of binary palindromes, the number of binary digits have to be odd.
  •   for the requirement of ternary palindromes, the numbers can't end in zero (in base 3).


The method used is to   (not find, but)   construct   a binary palindrome by:

  •   using the binary version of a number (abcdef),   which may end in binary zeroes,
  •   flipping the binary digits (fedcba)       [note that   a   is always   1   (one)],
  •   constructing two binary palindromes:
  •   abcdef   ||   0   ||   fedcba           and
  •   abcdef   ||   1   ||   fedcba
  •   (the above two concatenation (  ||  ) steps ensures an odd number of binary digits),
  •   ensure the decimal versions are not evenly divisible by 3,
  •   convert the decimal numbers to base 3,
  •   ensure that the numbers in base 3 are palindromic.

<lang rexx>/*REXX program finds numbers that are palindromic in both binary and ternary. */ digs=50; numeric digits digs /*biggest known B2B3 palindrome: 44 dig*/ parse arg maxHits .; if maxHits== then maxHits=6 /*use six as a limit.*/ hits=0; #= 'fiat' /*the number of palindromes (so far). */ call show 0,0,0; call show 1,1,1 /*show the first two palindromes (fiat)*/ !.= /* [↓] build list of powers of three. */ 

    do i=1  until !.i>10**digs;  !.i=3**i;  end /*compute powers of  three  for radix3.*/

p=1 /* [↓] primary search: bin palindromes*/ 

    do #=digs                                   /*use all numbers, however, DEC is odd.*/
    binH=strip( x2b( d2x(#)), 'L', 0)           /*convert some decimal number to binary*/
    binL=reverse(binH)                          /*reverse the binary digits  (or bits).*/
    dec=x2d( b2x( binH'0'binL) );   if dec//3\==0  then call radix3
    dec=x2d( b2x( binH'1'binL) );   if dec//3\==0  then call radix3
    end   /*#*/                                 /* [↑]  crunch 'til found 'nuff numbers*/

/*──────────────────────────────────────────────────────────────────────────────────────*/ radix3: parse var dec x 1 $,q /* [↓] convert decimal # ──► ternary.*/ 

                do j=p  while !.j<=x;   end     /*find upper limit of power of three.  */
       p=j-1                                    /*use this power of three for next time*/
                do k=p  by -1  for p;   _=!.k;   d=x%_;   q=q || d;   x=x//_;   end /*k*/
       t=q || x                                 /*handle residual of ternary conversion*/
       if t\==reverse(t)  then return           /*is T ternary number not palindromic? */
       call show $, t, strip(x2b(d2x($)), , 0)  /*show number: decimal, ternary, binary*/
       return                                   /* [↑]   RADIX3 subroutine is sluggish.*/

/*──────────────────────────────────────────────────────────────────────────────────────*/ show: hits=hits+1; say /*bump the number of palindromes found.*/ 

     say right('['hits"]", 5)   right( arg(1), digs)   '(decimal),   ternary='  arg(2)
     say right(, 5+1+ digs)                          '             binary='   arg(3)
     say '                                        #='  #
     if hits>2  then  if hits//2  then #=#'0'
     if hits<maxHits  then return               /*Not enough palindromes?  Keep looking*/
     exit                                       /*stick a fork in it,  we're all done. */</lang>

output when using the input of:   7 

  [1]                                                  0 (decimal),   ternary= 0
                                                                      binary= 0
                                        #= fiat

  [2]                                                  1 (decimal),   ternary= 1
                                                                      binary= 1
                                        #= fiat
  [3]                                               6643 (decimal),   ternary= 100010001
                                                                      binary= 1100111110011
                                        #= 51

  [4]                                            1422773 (decimal),   ternary= 2200021200022
                                                                      binary= 101011011010110110101
                                        #= 694
 
  [5]                                            5415589 (decimal),   ternary= 101012010210101
                                                                      binary= 10100101010001010100101
                                        #= 1322
  [6]                                        90396755477 (decimal),   ternary= 22122022220102222022122
                                                                      binary= 1010100001100000100010000011000010101
                                        #= 172418

[Output note:   the   6th   number (above) took a couple of seconds to compute.]

version 2

This REXX version takes advantage that the palindromic numbers (in both binary and ternary bases)   seem   to only have a modulus nine residue of   1, 5, 7, or 8.   With this assumption, the following REXX program is about 25% faster. <lang rexx>/*REXX program finds numbers that are palindromic in both binary and ternary. */ digs=50; numeric digits digs /*biggest known B2B3 palindrome: 44 dig*/ parse arg maxHits .; if maxHits== then maxHits=6 /*use six as a limit.*/ hits=0; #= 'fiat' /*the number of palindromes (so far). */ call show 0,0,0; call show 1,1,1 /*show the first two palindromes (fiat)*/

  1. .=0; #.1=1; #.5=1; #.7=1; #.8=1 /*modulus nine results that are OK. */

!.= /* [↓] build list of powers of three. */ 

    do i=1  until !.i>10**digs;  !.i=3**i;  end /*compute powers of  three  for radix3.*/

p=1 /* [↓] primary search: bin palindromes*/ 

    do #=digs                                   /*use all numbers, however, DEC is odd.*/
    binH=strip( x2b( d2x(#)), 'L', 0)           /*convert some decimal number to binary*/
    binL=reverse(binH)                          /*reverse the binary digits  (or bits).*/
    dec=x2d( b2x( binH'0'binL) ); _=dec//9;  if #._  then if dec//3\==0  then call radix3
    dec=x2d( b2x( binH'1'binL) ); _=dec//9;  if #._  then if dec//3\==0  then call radix3
    end   /*#*/                                 /* [↑]  crunch 'til found 'nuff numbers*/

/*──────────────────────────────────────────────────────────────────────────────────────*/ radix3: parse var dec x 1 $,q /* [↓] convert decimal # ──► ternary.*/ 

                do j=p  while !.j<=x;   end     /*find upper limit of power of three.  */
       p=j-1                                    /*use this power of three for next time*/
                do k=p  by -1  for p;   _=!.k;   d=x%_;   q=q || d;   x=x//_;   end /*k*/
       t=q || x                                 /*handle residual of ternary conversion*/
       if t\==reverse(t)  then return           /*is T ternary number not palindromic? */
       call show $, t, strip(x2b(d2x($)), , 0)  /*show number: decimal, ternary, binary*/
       return                                   /* [↑]   RADIX3 subroutine is sluggish.*/

/*──────────────────────────────────────────────────────────────────────────────────────*/ show: hits=hits+1; say /*bump the number of palindromes found.*/ 

     say right('['hits"]", 5)   right( arg(1), digs)   '(decimal),   ternary='  arg(2)
     say right(, 5+1+ digs)                          '             binary='   arg(3)
     say '                                        #='  #
     if hits>2  then  if hits//2  then #=#'0'
     if hits<maxHits  then return               /*Not enough palindromes?  Keep looking*/
     exit                                       /*stick a fork in it,  we're all done. */</lang>

output   is identical to the 1st REXX version.

Ruby

This program is based on the fact that the double palindromic numbers in base 3 all have a "1" right in the middle. Also, both base 2 and base 3 representations have an odd number of digits.

  1. 1 digit under the number of the palindromic doesn't become zero.
  2. As for the N numbering-system, at the time of the multiple of N, 1 digit below becomes zero.
  3. Palindromic by the even-number digit binary system is 3 multiples.
  4. Palindromic by the even-number digit ternary-system is 4 multiples.
  5. In palindromic by the ternary-system of the odd digit, the value of the center position is an even number in case of "0" or "2".

This program constructs base 3 palindromes using the above "rules" and checks if they happen to be binary palindromes.

<lang ruby>pal23 = Enumerator.new do |y| 

 y << 0
 y << 1
 for i in 1 .. 1.0/0.0                 # 1.step do |i|  (Ruby 2.1+)
   n3 = i.to_s(3)
   n = (n3 + "1" + n3.reverse).to_i(3)
   n2 = n.to_s(2)
   y << n  if n2.size.odd? and n2 == n2.reverse
 end

end

puts " decimal ternary binary" 6.times do |i| 

 n = pal23.next
 puts "%2d: %12d %s %s" % [i, n, n.to_s(3).center(25), n.to_s(2).center(39)]

end</lang>

Output:
         decimal          ternary                          binary
 0:            0             0                                0                   
 1:            1             1                                1                   
 2:         6643         100010001                      1100111110011             
 3:      1422773       2200021200022                101011011010110110101         
 4:      5415589      101012010210101              10100101010001010100101        
 5:  90396755477  22122022220102222022122   1010100001100000100010000011000010101

Scheme

<lang scheme> (import (scheme base) 

       (scheme write)
       (srfi 1 lists)) ; use 'fold' from SRFI 1
convert number to a list of digits, in desired base

(define (r-number->list n base) 

 (let loop ((res '())
            (num n))
   (if (< num base) 
     (cons num res)
     (loop (cons (remainder num base) res)
           (quotient num base)))))
convert number to string, in desired base

(define (r-number->string n base) 

 (apply string-append 
        (map number->string 
             (r-number->list n base))))
test if a list of digits is a palindrome

(define (palindrome? lst) 

 (equal? lst (reverse lst)))
based on Perl/Ruby's insight
-- construct the ternary palindromes in order
using fact that their central number is always a 1
-- convert into binary, and test if result is a palindrome too

(define (get-series size) 

 (let loop ((results '(1 0))
            (i 1))
   (if (= size (length results))
     (reverse results)
     (let* ((n3 (r-number->list i 3))
            (n3-list (append n3 (list 1) (reverse n3)))
            (n10 (fold (lambda (d t) (+ d (* 3 t))) 0 n3-list))
            (n2 (r-number->list n10 2)))
       (loop (if (palindrome? n2)
               (cons n10 results)
               results)
             (+ 1 i))))))
display final results, in bases 10, 2 and 3.

(for-each 

 (lambda (n) 
   (display 
     (string-append (number->string n)
                    " in base 2: "
                    (r-number->string n 2)
                    " in base 3: "
                    (r-number->string n 3)))
   (newline))
 (get-series 6))

</lang>

Output:
0 in base 2: 0 in base 3: 0
1 in base 2: 1 in base 3: 1
6643 in base 2: 1100111110011 in base 3: 100010001
1422773 in base 2: 101011011010110110101 in base 3: 2200021200022
5415589 in base 2: 10100101010001010100101 in base 3: 101012010210101
90396755477 in base 2: 1010100001100000100010000011000010101 in base 3: 22122022220102222022122

Sidef

Translation of: Perl

<lang ruby>var format = "%11s %24s %38s\n" format.printf("decimal", "ternary", "binary") format.printf(0, 0, 0)

for n in (0 .. 2e5) { 

   var pal = n.base(3)||
   var b3 = (pal + '1' + pal.flip)
   var b2 = Num(b3, 3).base(2)
   if (b2 == b2.flip) {
       format.printf(Num(b2, 2), b3, b2)
   }

}</lang>

Output:
    decimal                  ternary                                 binary
          0                        0                                      0
          1                        1                                      1
       6643                100010001                          1100111110011
    1422773            2200021200022                  101011011010110110101
    5415589          101012010210101                10100101010001010100101
90396755477  22122022220102222022122  1010100001100000100010000011000010101

Tcl

We can use [format %b] to format a number as binary, but ternary requires a custom proc: <lang Tcl>proc format_%t {n} { 

   while {$n} {
       append r [expr {$n % 3}]
       set n [expr {$n / 3}]
   }
   if {![info exists r]} {set r 0}
   string reverse $r

}</lang>

Identifying palindromes is simple. This form is O(n) with a large constant factor, but good enough:

<lang Tcl>proc pal? {s} {expr {$s eq [string reverse $s]}}</lang>

The naive approach turns out to be very slow: <lang Tcl>proc task Template:Find 6 { 

   for {set i 0} {$find} {incr i} {
       set b [format %b $i]
       set t [format_%t $i]
       if {[pal? $b] && [pal? $t]} {
           puts "Palindrome: $i ($b) ($t)"
           incr find -1
       }
   }

}

puts [time {task 4}]</lang>

Output:
Palindrome: 0 (0) (0)
Palindrome: 1 (1) (1)
Palindrome: 6643 (1100111110011) (100010001)
Palindrome: 1422773 (101011011010110110101) (2200021200022)
21944474 microseconds per iteration

22 seconds for only the first four elements .. not good enough! We can do much better than that by naively iterating the binary palindromes. This is nice to do in a coroutine:

<lang Tcl>package require Tcl 8.5 ;# for coroutines

proc 2pals {} { 

   yield 0
   yield 1
   while 1 {
       incr i
       set a [format %b $i]
       set b [string reverse $a]
       yield ${a}$b
       yield ${a}0$b
       yield ${a}1$b
   }

}</lang>

The binary strings emitted by this generator are not in increasing order, but for this particular task, that turns out to be unimportant.

Our main loop needs only minor changes:

<lang Tcl>proc task Template:Find 6 { 

   coroutine gen apply {{} {yield; 2pals}}
   while {$find} {
       set b [gen]
       set i [scan $b %b]
       set t [format_%t $i]
       if {[pal? $t]} {
           puts "Palindrome: $i ($b) ($t)"
           incr find -1
       }
   }
   rename gen {}

}

puts [time task]</lang>

This version finds the first 6 in under 4 seconds, which is good enough for the task at hand:

Output:
Palindrome: 0 (0) (0)
Palindrome: 1 (1) (1)
Palindrome: 6643 (1100111110011) (100010001)
Palindrome: 1422773 (101011011010110110101) (2200021200022)
Palindrome: 5415589 (10100101010001010100101) (101012010210101)
Palindrome: 90396755477 (1010100001100000100010000011000010101) (22122022220102222022122)
3643152 microseconds per iteration

Plenty more optimisations are possible! Exploiting the observations in Ruby's implementation should make the 7th element reachable in reasonable time ...

zkl

Brute force, hits the wall hard after a(5) <lang zkl>fcn twoThreeP(n){ 

  n2s:=n.toString(2); n3s:=n.toString(3); 
  (n2s==n2s.reverse() and n3s==n3s.reverse())

} [0..].filter(5,twoThreeP) .apply2(fcn(n){println(n,"==",n.toString(3),"==",n.toString(2))}) </lang>

Output:
0==0==0
1==1==1
6643==100010001==1100111110011
1422773==2200021200022==101011011010110110101
5415589==101012010210101==10100101010001010100101
Retrieved from "https://rosettacode.org/wiki/Find_palindromic_numbers_in_both_binary_and_ternary_bases?oldid=244301"