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.

On my machine, this gets the first five results practically instantaneously and the sixth about eight seconds later.

 

script o

property digits : {int mod base as integer}

end task

 

 

{{output}}

0 0 0

1 1 1

1422773 101011011010110110101 2200021200022

5415589 10100101010001010100101 101012010210101

 

=={{header|Arturo}}==

{{trans|Ada}}

digs2: digits.base:2 n

return digs2 = reverse digs2

]

 

 

{{out}}

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

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

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

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

import Data.List (transpose, unwords)

import Numeric (readInt, showIntAtBase)

 

showBase :: Integer -> Integer -> String

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

===ES6===

{{Trans|Haskell}}

'use strict';

 

)))

.map(unwords));

{{Out}}

<pre>Decimal Ternary Binary

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

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

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.

 

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #000080;font-style:italic;">-- widths and limits for 32/64 bit running (see output below):</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>

<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>

{{out}}

32 bit:

=== much simpler version ===

(slightly but not alot faster)

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">to_base</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">base</span><span style="color: #0000FF;">)</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>

<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>

{{out}}

<pre>

=== much faster version ===

Inspired by Scala 😏

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">to_base</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">base</span><span style="color: #0000FF;">)</span>

<span style="color: #000000;">center</span><span style="color: #0000FF;">(</span><span style="color: #000000;">to_base</span><span style="color: #0000FF;">(</span><span style="color: #000000;">A</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">3</span><span style="color: #0000FF;">),</span><span style="color: #000000;">145</span><span style="color: #0000FF;">)</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

{{out}}

<pre>

</pre>

=={{header|Picat}}==

import sat.

to_num(List, Base, Num) =>

printf("%w %s %s%n", Y, to_radix_string(Y,2), to_radix_string(Y,3))

end.

Output:

<pre>0 0 0

 

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

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