Find palindromic numbers in both binary and ternary bases: Difference between revisions
(→{{header|REXX}}: re-did the algorithm to generate palindromic binary numbers.) |
|||
Line 250: | Line 250: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
Programming note: This version |
Programming note: This version is quite a bit faster than the previous one. |
||
<br>that some powers of two can be bypassed because they have an even number of binary digits. |
|||
For this REXX program, a few deterministic assumptions were made: |
For this REXX program, a few deterministic assumptions were made: |
||
::* for the requirement of binary palindromes, the numbers have to be odd. |
|||
::* for the requirement of binary palindromes, the number of binary digits have to be odd. |
::* 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). |
::* for the requirement of ternary palindromes, the numbers can't end in zero (in base 3). |
||
<lang rexx>/*REXX pgm finds decimal #s that are palindromic in binary and ternary.*/ |
<lang rexx>/*REXX pgm finds decimal #s that are palindromic in binary and ternary.*/ |
||
numeric digits 50 /* |
numeric digits 50 /*biggest known B2B3 pal: 41 dig.*/ |
||
parse arg H .; if H=='' then H=6 /*when H hits are found, stop. */ |
|||
hits=0 /*number of hits (palindromes). */ |
hits=0 /*number of hits (palindromes). */ |
||
say right(0, digits()); hits=hits+1 /*display the 1st pal (in B2&B3).*/ |
say right(0, digits()); hits=hits+1 /*display the 1st pal (in B2&B3).*/ |
||
Line 265: | Line 264: | ||
do i=1 until pos('E',!.i)\==0; !.i=3**i; end /*i*/ |
do i=1 until pos('E',!.i)\==0; !.i=3**i; end /*i*/ |
||
o=1 /* [↓] primary search: bin pals.*/ |
o=1 /* [↓] primary search: bin pals.*/ |
||
do |
do n=1 /*use all #s, however, DEC == odd*/ |
||
bin=strip(x2b(d2x(n)), 'L', 0) /*convert the number to binary. */ |
|||
rev=reverse(bin) /*reverse the binary digits. */ |
|||
dec=x2d(b2x(bin'0'rev)) /*construct a binary palindrom«0»*/ |
|||
if length(b)//2==0 then iterate p /*if bin# has even# digits, skip.*/ |
|||
if dec//3\==0 then call rad3 /*if not divisible by 3, try it. */ |
|||
dec=x2d(b2x(bin'1'rev)) /*construct a binary palindrom«1»*/ |
|||
if dec//3\==0 then call rad3 /*if not divisible by 3, try it. */ |
|||
end /*n*/ /* [↑] run until we find H hits.*/ |
|||
/*──────────────────────────────────RAD3 subroutine─────────────────────*/ |
|||
b=strip(x2b(d2x(n)),'L',0) /*express the number in binary. */ |
|||
⚫ | |||
if b\==reverse(b) then iterate /*is binary number palindromic? */ |
|||
⚫ | |||
do j=o; if !.j>x then leave; end /*find upper limit of pow of 3.*/ |
do j=o; if !.j>x then leave; end /*find upper limit of pow of 3.*/ |
||
q= /*set base 3 result holder to nul*/ |
q= /*set base 3 result holder to nul*/ |
||
o=j-1 /*use this pow of 3 for next time*/ |
o=j-1 /*use this pow of 3 for next time*/ |
||
do k=o to 1 by -1; _=!.k; d=x%_; q=q||d; x=x//_; end /*k*/ |
do k=o to 1 by -1; _=!.k; d=x%_; q=q||d; x=x//_; end /*k*/ |
||
t=q|| |
t=q || x /*handle the conversion residual.*/ |
||
if t\==reverse(t) then |
if t\==reverse(t) then return /*is this ternary # palindromic? */ |
||
say right( |
say right(dec, digits()) /*display a palindrome (in B2&B3)*/ |
||
hits=hits+1 /*bump hit counter (palindromes).*/ |
hits=hits+1 /*bump hit counter (palindromes).*/ |
||
if hits== |
if hits==H then exit /*stick a fork in it, we're done.*/ |
||
return /* [↑] this process is sluggish.*/</lang> |
|||
'''output''' when using the input of: <tt> 7 </tt |
|||
⚫ | |||
/*stick a fork in it, we're done.*/</lang> |
|||
'''output''' |
|||
<pre> |
<pre> |
||
0 |
0 |
||
Line 296: | Line 292: | ||
5415589 |
5415589 |
||
90396755477 |
90396755477 |
||
⚫ | |||
</pre> |
</pre> |
||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
This program is based on the observation 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. (NB I have no mathematical proof of this). |
This program is based on the observation 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. (NB I have no mathematical proof of this). |
Revision as of 19:28, 3 April 2014
- 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 it's 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;
bool isPalindrome2(ulong n) pure nothrow {
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 {
ulong x = 0; while (n) { x = x * 3 + (n % 3); n /= 3; } return x;
}
void printReversed(ubyte base)(ulong n) {
putchar(' '); do { putchar('0' + (n % base)); n /= base; } while(n);
printf("(%d)", base);
}
void main() {
ulong i, cnt, top = 1, mul = 1, even = 0; uint count = 0;
for (i = cnt = 0; cnt < 6; 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); putchar('\n');
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)
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. Outputs the list in decimal, binary and trinary.
Note: finding the first six takes a depressingly long time with this implementation. Seven would be unbearable. :-(
<lang perl6>my @palindromes := 0, 1, gather for 1 .. * -> $n {
my $p = $n.base(3); my $q = $p.flip; for "$p$q", "{$p}0$q", "{$p}1$q", "{$p}2$q" -> $r { my $s = :3($r); next if $s %% 2; $s = $s.base(2); next unless $s eq $s.flip; take :2($s); }
}
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
REXX
Programming note: This version is quite a bit faster than the previous one.
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).
<lang rexx>/*REXX pgm finds decimal #s that are palindromic in binary and ternary.*/ numeric digits 50 /*biggest known B2B3 pal: 41 dig.*/ parse arg H .; if H== then H=6 /*when H hits are found, stop. */ hits=0 /*number of hits (palindromes). */ say right(0, digits()); hits=hits+1 /*display the 1st pal (in B2&B3).*/ say right(1, digits()); hits=hits+1 /*display the 2nd pal (in B2&B3).*/ !.= /* [↓] build list of powers of 3*/
do i=1 until pos('E',!.i)\==0; !.i=3**i; end /*i*/
o=1 /* [↓] primary search: bin pals.*/
do n=1 /*use all #s, however, DEC == odd*/ bin=strip(x2b(d2x(n)), 'L', 0) /*convert the number to binary. */ rev=reverse(bin) /*reverse the binary digits. */ dec=x2d(b2x(bin'0'rev)) /*construct a binary palindrom«0»*/ if dec//3\==0 then call rad3 /*if not divisible by 3, try it. */ dec=x2d(b2x(bin'1'rev)) /*construct a binary palindrom«1»*/ if dec//3\==0 then call rad3 /*if not divisible by 3, try it. */ end /*n*/ /* [↑] run until we find H hits.*/
/*──────────────────────────────────RAD3 subroutine─────────────────────*/ rad3: x=dec /*convert constructed # to base 3*/
do j=o; if !.j>x then leave; end /*find upper limit of pow of 3.*/ q= /*set base 3 result holder to nul*/ o=j-1 /*use this pow of 3 for next time*/ do k=o to 1 by -1; _=!.k; d=x%_; q=q||d; x=x//_; end /*k*/ t=q || x /*handle the conversion residual.*/ if t\==reverse(t) then return /*is this ternary # palindromic? */ say right(dec, digits()) /*display a palindrome (in B2&B3)*/ hits=hits+1 /*bump hit counter (palindromes).*/ if hits==H then exit /*stick a fork in it, we're done.*/
return /* [↑] this process is sluggish.*/</lang> output when using the input of: 7 </tt
0 1 6643 1422773 5415589 90396755477 381920985378904469
Ruby
This program is based on the observation 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. (NB I have no mathematical proof of this). This program constructs palindromes using the above "rules" and checks if they happen to be the same number. The first six took less then one second, 381920985378904469 took around 40 minutes (using one core) and 146 million possible candidates. <lang ruby> base3 = Enumerator.new do |y|
- generates palindromic base 3 numbers of odd length, with 1 in the middle
n = 0 y << 0 # yield 0 y << 1 loop do w = n.to_s(3) r = w.reverse num = ( w << "1" << r).to_i(3) y << num if (Math.log2(num) +1).floor.odd? # don't yield if base2 size is even n += 1 end
end
base2 = Enumerator.new do |y|
- generates palindromic base 2 numbers of odd length, with 0 or 1 in the middle
n = 0 y << 0 y << 1 loop do w = n.to_s(2) r = w.reverse y << "#{w}0#{r}".to_i(2) y << "#{w}1#{r}".to_i(2) n += 1 end
end
b2 = 0 counter = 0 loop do
b3 = base3.next b2 = base2.next until b2 >= b3 p b2 if b2 == b3 counter += 1 puts " #{counter} b2: #{b2} b3: #{b3}" if counter % 1_000_000 == 0
end</lang>
- Output:
0 1 6643 1422773 5415589 90396755477 1000000 b2: 23905993887669 b3: 23905990910359 2000000 b2: 290686519348257 b3: 290686517832919 . . . 146000000 b2: 381113553041095829 b3: 381113552941511621 381920985378904469 147000000 b2: 382275814715933589 b3: 382275814546908221 ^Ctest2.rb:37:in `next': Interrupt