Find palindromic numbers in both binary and ternary bases: Difference between revisions
(→{{header|Tcl}}: flagged the output section as incorrect: didn't display zero.) |
m (→{{header|Tcl}}: clarified comment for the flagging.) |
||
| Line 573: | Line 573: | ||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
{{incorrect|Tcl| <br> <br> The '''output''' section doesn't list the first number: 0 (zero). <br> <br> }} |
{{incorrect|Tcl| <br> <br> The (first) '''output''' section doesn't list the first number: 0 (zero). <br> <br> }} |
||
We can use <tt>[format %b]</tt> to format a number as binary, but ternary requires a custom proc: |
We can use <tt>[format %b]</tt> to format a number as binary, but ternary requires a custom proc: |
||
Revision as of 20:36, 22 February 2016
- 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.
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>
- 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) 90396755477 1010100001100000100010000011000010101(2) 22122022220102222022122(3) 381920985378904469 10101001100110110110001110011011001110001101101100110010101(2) 2112200222001222121212221002220022112(3)
D
<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)
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
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 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. Getting the 6th number requires about 4 cpu minutes on an i7.
<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 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 /*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 /*i*/
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 $ /* [↓] convert decimal # ──► ternary.*/
do j=p while !.j<=x; end /*find upper limit of power of three. */
q= /*set holder of ternary result to null.*/ 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
[2] 1 (decimal), ternary= 1
binary= 1
[3] 6643 (decimal), ternary= 100010001
binary= 1100111110011
[4] 1422773 (decimal), ternary= 2200021200022
binary= 101011011010110110101
[5] 5415589 (decimal), ternary= 101012010210101
binary= 10100101010001010100101
[6] 90396755477 (decimal), ternary= 22122022220102222022122
binary= 1010100001100000100010000011000010101
[7] 381920985378904469 (decimal), ternary= 2112200222001222121212221002220022112
binary= 10101001100110110110001110011011001110001101101100110010101
[Output note: the 6th number (above) took about ten 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 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 /*the number of palindromes (so far). */ call show 0,0,0; call show 1,1,1 /*show the first two palindromes (fiat)*/
- .=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 /*i*/
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 $ /* [↓] convert decimal # ──► ternary.*/
do j=p while !.j<=x; end /*find upper limit of power of three. */
q= /*set holder of ternary result to null.*/ 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)
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 digit under the number of the palindromic doesn't become zero.
- As for the N numbering-system, at the time of the multiple of N, 1 digit below becomes zero.
- Palindromic by the even-number digit binary system is 3 multiples.
- Palindromic by the even-number digit ternary-system is 4 multiples.
- 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
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 {
while {$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: 1 (1) (1) Palindrome: 6643 (1100111110011) (100010001) Palindrome: 1422773 (101011011010110110101) (2200021200022) Palindrome: 5415589 (10100101010001010100101) (101012010210101) 25960381 microseconds per iteration
26 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