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

{{trans|Python}}

 

 

F baseN(=num, b)

 

L(pal23) pal_23(6)

 

{{out}}

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

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

{{trans|C}}

prin3online(n) = println(lpad(n, 15), lpad(string(n, base=2), 40), lpad(string(n, base=3), 30))

reversebase3(n) = (x = 0; while n != 0 x = 3x + (n %3); n = div(n, 3); end; x)

 

printpalindromes(6)

<pre>

Number Base 2 Base 3

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

=={{header|Nim}}==

{{trans|Ada}}

 

#---------------------------------------------------------------------------------------------------

let t0 = cpuTime()

findPal23()

 

{{out}}

 

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

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"

=={{header|Python}}==

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

 

yield ibt

while True:

ibt = until(isBoth)(psucc)(psucc(ibt))

 

 

s = showBase3(d)

pal = s + '1' + s[::-1]

 

 

 

 

def main():

 

xs = take(6)(palinBoth())

 

 

 

# compose (<<<) :: (b -> c) -> (a -> b) -> a -> c

or xs itself if n > length xs.

'''

 

 

The initial seed value is x.

'''

 

 

 

# label :: Method String -> (String, Int)

s, w = sw

return getattr(s, k)(w, ' ') + ' '

 

 

# 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

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.

 

my $pal = $p.base(3);

my $n = :3($pal ~ '1' ~ $pal.flip);

}

 

{{out}}

<pre>0, 0, 0

::* &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

 

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

{{trans|C}}

 

 

func isPalin2(n: Int) -> Bool {

}

}

 

{{out}}

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

{{libheader|Wren-fmt}}

Just the first 6 palindromes as the 7th is too large for Wren to process without resorting to BigInts.

 

var isPalindrome2 = Fn.new { |n|

}

}

 

{{out}}

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