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

*   [[oeis:A060792|Sequence A60792]],   numbers that are palindromic in bases 2 and 3 on ''The On-Line Encyclopedia of Integer Sequences''.

<br><br>

 

=={{header|Ada}}==

===Simple Technique (Brute Force)===

 

procedure Brute is

end if;

end loop;

{{out}}

<pre> 0: 0(2), 0(3)

The code is then very fast and also very much readable than if we had done the bit manipulations by hand.

 

procedure Palindromic is

type Int is mod 2**64; -- the size of the unsigned values we will test doesn't exceed 64 bits

end loop;

end loop Process_Each_Power_Of_4;

{{out}}

On a modern machine, (core i5 for example), this code, compiled with the -O3 and -gnatp options, takes less than 5 seconds to give the seven first palindromes smaller than 2^64.

2#1010100001100000100010000011000010101# 3#22122022220102222022122# 90396755477

2#10101001100110110110001110011011001110001101101100110010101# 3#2112200222001222121212221002220022112# 381920985378904469</pre>

 

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

typedef unsigned long long xint;

 

}

return 0;

{{out}}

<pre>0 0(2) 0(3)

381920985378904469 10101001100110110110001110011011001110001101101100110010101(2) 2112200222001222121212221002220022112(3)</pre>

 

{{works with|C sharp|3}}

No strings involved. Ternary numbers (only of odd length and with a 1 in the middle) are generated by permutating powers of 3<br/>

and then checked to see if they are palindromic in binary.<br/>

The first 6 numbers take about 1/10th of a second. The 7th number takes about 3 and a half minutes.

using System.Collections.Generic;

using System.Linq;

}

 

{{out}}

<pre style="height:30ex;overflow:scroll">

Ternary: 22122022220102222022122

Binary: 1010100001100000100010000011000010101

</pre>

 

=={{header|Common Lisp}}==

Unoptimized version

(string-equal str (reverse str)) )

 

(palindromep (format nil "~3R" i)) )

(format t "n:~a~:* [2]:~B~:* [3]:~3R~%" i)

{{out}}

<pre>n:0 [2]:0 [3]:0

=={{header|D}}==

{{trans|C}}

 

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

}

}

{{out}}

<pre>0 0(3) 0(2)

5415589 101012010210101(3) 10100101010001010100101(2)

90396755477 22122022220102222022122(3) 1010100001100000100010000011000010101(2)</pre>

 

=={{header|Elixir}}==

{{trans|Ruby}}

{{works with|Elixir|1.3}}

import Integer, only: [is_odd: 1]

 

end

 

{{out}}

<pre> decimal ternary binary

 

=={{header|F_Sharp|F#}}==

// Find palindromic numbers in both binary and ternary bases. December 19th., 2018

let fG(n,g)=(Seq.unfold(fun(g,e)->if e<1L then None else Some((g%3L)*e,(g/3L,e/3L)))(n,g/3L)|>Seq.sum)+g+n*g*3L

Seq.concat[seq[0L;1L;2L];Seq.unfold(fun(i,e)->Some (fG(i,e),(i+1L,if i=e-1L then e*3L else e)))(1L,3L)]

|>Seq.filter(fun n->let n=System.Convert.ToString(n,2).ToCharArray() in n=Array.rev n)|>Seq.take 6|>Seq.iter (printfn "%d")

{{out}}

Finding 6 takes no time.

Real: 00:23:09.114, CPU: 00:23:26.430, GC gen0: 209577, gen1: 1

</pre>

=={{header|Factor}}==

This implementation uses the methods for reducing the search space discussed in the Ruby example.

lists.lazy literals math math.parser sequences tools.time ;

IN: rosetta-code.2-3-palindromes

] each ;

 

{{out}}

<pre>The first 6 numbers which are palindromic in both binary and ternary:

and check if they are also binary palindromes using the optimizations which have been noted in some

of the other language solutions :

 

'converts decimal "n" to its ternary equivalent

Print " seconds on i3 @ 2.13 GHz"

Print "Press any key to quit"

{{out}}

<pre>The first 6 numbers which are palindromic in both binary and ternary are :

{{trans|C}}

On my modest machine (Intel Celeron @1.6ghz) this takes about 30 seconds to produce the 7th palindrome. Curiously, the C version (GCC 5.4.0, -O3) takes about 55 seconds on the same machine. As it's a faithful translation, I have no idea why.

 

import (

}

}

 

{{out}}

 

=={{header|Haskell}}==

 

base3Palindrome :: Integer -> String

 

isBinPal :: Integer -> Bool

isBinPal n =

 

main :: IO ()

main =

mapM_

putStrLn

where

{{Out}}

<pre>Decimal Ternary Binary

=={{header|J}}==

'''Solution:'''

toBase=: #.inv"0 NB. convert to base(s) in left arg

filterPalinBase=: ] #~ isPalin@toBase/ NB. palindromes for base(s)

end.

y{.res

'''Usage:'''

0 1 6643 1422773

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

1422773 101011011010110110101 2200021200022

5415589 10100101010001010100101 101012010210101

 

=={{header|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)

public static boolean isPali(String x){

return x.equals(new StringBuilder(x).reverse().toString());

}

}

{{out}}

<pre>0, 0, 0

5415589, 10100101010001010100101, 101012010210101

90396755477, 1010100001100000100010000011000010101, 22122022220102222022122</pre>

 

=={{header|JavaScript}}==

===ES6===

{{Trans|Haskell}}

'use strict';

 

)))

.map(unwords));

{{Out}}

<pre>Decimal Ternary Binary

5415589 101012010210101 10100101010001010100101

90396755477 22122022220102222022122 1010100001100000100010000011000010101 </pre>

 

=={{header|Julia}}==

 

 

=={{header|Kotlin}}==

{{trans|FreeBASIC}}

 

/** converts decimal 'n' to its ternary equivalent */

}

while (count < 6)

{{out}}

<pre>The first 6 numbers which are palindromic in both binary and ternary are:

Ternary : 22122022220102222022122</pre>

 

Block[{digits},

If[Divisible[n, 3], {},

];

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

 

{{out}}

<pre>{1, 6643, 1422773, 5415589, 90396755477}</pre>

 

=={{header|PARI/GP}}==

my(N=3^n);

forstep(i=N+1,2*N,[1,2],

)

};

{{out}}

<pre>0, 1, 6643, 1422773, 5415589, 90396755477</pre>

=={{header|Perl}}==

{{libheader|ntheory}}

 

print "0 0 0\n"; # Hard code the 0 result

# Print results (including base 10) if base-2 palindrome

print fromdigits($b2,2)," $b3 $b2\n" if $b2 eq reverse($b2);

{{out}}

<pre>0 0 0

5415589 101012010210101 10100101010001010100101

90396755477 22122022220102222022122 1010100001100000100010000011000010101</pre>

 

=={{header|Phix}}==

that turned out noticeably slower.

 

{{out}}

32 bit:

=== much simpler version ===

(slightly but not alot faster)

{{out}}

<pre>

=== much faster version ===

Inspired by Scala 😏

{{out}}

0

0

2202021211210100110100002202101000110000220121210220000110001012022000010110010121121202022

</pre>

 

=={{header|PicoLisp}}==

(if (=0 N)

(cons N)

(println N (pack B2) (pack B3))

(inc 'I) )

{{out}}

<pre>0 "0" "0"

90396755477 "1010100001100000100010000011000010101" "22122022220102222022122"</pre>

 

===Imperative===

 

digits = "0123456789abcdefghijklmnopqrstuvwxyz"

 

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

{{out}}

<pre>0 0 0

===Functional===

{{Works with|Python|3.7}}

 

from itertools import (islice)

def palinBoth():

'''Non finite stream of dually palindromic integers.'''

while True:

 

 

'''

return b == b[::-1]

 

 

 

 

 

 

def main():

 

xs = take(6)(palinBoth())

 

print(

fTable(

''.join(map(

label('center'),

[('Binary', bw), ('Ternary', tw)]

)) + '\n'

)

 

 

 

# showIntAtBase :: Int -> (Int -> String) -> Int -> String -> String

return lambda toChr: lambda n: lambda rs: (

wrap(toChr, n, rs)

)

 

or xs itself if n > length xs.

'''

 

 

The initial seed value is x.

'''

 

 

 

# fTable :: String -> (a -> String) ->

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre> Decimal Binary Ternary

 

=={{header|Racket}}==

(require racket/generator)

 

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

{{out}}

<pre> 1: 0_10 0_3 0_2

5: 5415589_10 101012010210101_3 10100101010001010100101_2

6: 90396755477_10 22122022220102222022122_3 1010100001100000100010000011000010101_2</pre>

 

=={{header|REXX}}==

::* &nbsp; convert the decimal numbers to base 3,

::* &nbsp; ensure that the numbers in base 3 are palindromic.

digs=50; numeric digits digs /*biggest known B2B3 palindrome: 44 dig*/

parse arg maxHits .; if maxHits=='' then maxHits=6 /*use six as a limit.*/

if hits>2 then if hits//2 then #=#'0'

if hits<maxHits then return /*Not enough palindromes? Keep looking*/

{{out|output|text=&nbsp; when using the default input of: &nbsp; &nbsp; <tt> 7 </tt>}}

<pre> [1] 0 (decimal), ternary= 0

===version 2===

This REXX version takes advantage that the palindromic numbers (in both binary and ternary bases) &nbsp; ''seem'' &nbsp; to only have a modulus nine residue of &nbsp; 1, 5, 7, or 8. &nbsp; With this assumption, the following REXX program is about 25% faster.

digs=50; numeric digits digs /*biggest known B2B3 palindrome: 44 dig*/

parse arg maxHits .; if maxHits=='' then maxHits=6 /*use six as a limit.*/

if hits>2 then if hits//2 then #=#'0'

if hits<maxHits then return /*Not enough palindromes? Keep looking*/

{{out|output|text=&nbsp; is identical to the 1^st REXX version.}}

 

=={{header|Ring}}==

# Project: Find palindromic numbers in both binary and ternary bases

 

return 0

ok

{{out}}

<pre>

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

 

y << 0

y << 1

n = pal23.next

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

{{out}}

<pre> decimal ternary binary

===Functional programmed, (tail) recursive===

{{Out}}Best seen running in your browser either by [https://scalafiddle.io/sf/ZYCqm7p/0 ScalaFiddle (ES aka JavaScript, non JVM)] or [https://scastie.scala-lang.org/WIL3oAwYSRy4Kl918u13CA Scastie (remote JVM)].

import scala.compat.Platform.currentTime

 

println(s"Successfully completed without errors. [total ${currentTime - executionStartTime} ms]")

 

 

===Fastest and high yields (17) solution 😏===

{{Out}}Best seen running in your browser either by [https://scastie.scala-lang.org/en0ZiqDETCuWO6avhTi9YQ Scastie (remote JVM)].

 

object FastPalindrome23 extends App {

println(s"${count} palindromes found.")

 

{{Out}}

<pre>Decimal : 0 , Central binary digit: 0

---

17 palindromes found.</pre>

=={{header|Scheme}}==

(scheme write)

(srfi 1 lists)) ; use 'fold' from SRFI 1

(r-number->string n 3)))

(newline))

 

{{out}}

=={{header|Sidef}}==

{{trans|Perl}}

format.printf("decimal", "ternary", "binary")

format.printf(0, 0, 0)

format.printf(Num(b2, 2), b3, b2)

}

{{out}}

<pre> decimal ternary binary

5415589 101012010210101 10100101010001010100101

90396755477 22122022220102222022122 1010100001100000100010000011000010101</pre>

 

=={{header|Tcl}}==

We can use <tt>[format %b]</tt> to format a number as binary, but ternary requires a custom proc:

while {$n} {

append r [expr {$n % 3}]

if {![info exists r]} {set r 0}

string reverse $r

 

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

 

 

The naive approach turns out to be very slow:

for {set i 0} {$find} {incr i} {

set b [format %b $i]

}

 

{{out}}

<pre>Palindrome: 0 (0) (0)

We can do much better than that by naively iterating the binary palindromes. This is nice to do in a coroutine:

 

 

proc 2pals {} {

yield ${a}1$b

}

 

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:

coroutine gen apply {{} {yield; 2pals}}

while {$find} {

}

 

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

{{out}}

 

=={{header|VBA}}==

'palindromes both in base3 and base2

'using Decimal data type to find number 6 and 7, although slowly

Debug.Print "Completed in"; (Time3 - Time1) / 1000; "seconds"

Application.ScreenUpdating = True

' 0 0 0 0

' 0 1 1 1

' 328601606 381920985378904469 59 10101001100110110110001110011011001110001101101100110010101 37 2112200222001222121212221002220022112

Completed in 5,14 secondsCompleted in 16394,64 seconds

</pre>

 

{{trans|Ruby}}

VERY slow after six but does find it.

Walker.tweak(fcn(ri,r){ // references to loop start and count of palindromes

foreach i in ([ri.value..*]){

}

}.fp(Ref(3),Ref(3))).push(T(1,0),T(2,1)) // seed with first two results

println("%2d: %,d == %.3B(3) == %.2B(2)".fmt(idx,n,n,n))

{{out}}

<pre>