Find palindromic numbers in both binary and ternary bases: Difference between revisions
Find palindromic numbers in both binary and ternary bases (view source)
Revision as of 21:14, 15 April 2024
, 1 month ago→{{header|EasyLang}}
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
| (13 intermediate revisions by 5 users not shown) | |||
Line 519:
Ternary: 22122022220102222022122
Binary: 1010100001100000100010000011000010101
</pre>
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <algorithm>
#include <cstdint>
#include <iostream>
// Convert the given decimal number to the given number base
// and return it converted to a string
std::string to_base_string(const uint64_t& number, const uint32_t& base) {
uint64_t n = number;
if ( n == 0 ) {
return "0";
}
std::string result;
while ( n > 0 ) {
result += std::to_string(n % base);
n /= base;
}
std::reverse(result.begin(), result.end());
return result;
}
void display(const uint64_t& number) {
std::cout << "Decimal: " << number << std::endl;
std::cout << "Binary : " << to_base_string(number, 2) << std::endl;
std::cout << "Ternary: " << to_base_string(number, 3) << std::endl << std::endl;
}
bool is_palindromic(const std::string& number) {
std::string copy = number;
std::reverse(copy.begin(), copy.end());
return number == copy;
}
// Create a ternary palindrome whose left part is the ternary equivalent of the given number
// and return it converted to a decimal
uint64_t create_ternary_palindrome(const uint64_t& number) {
std::string ternary = to_base_string(number, 3);
uint64_t power_of_3 = 1;
uint64_t result = 0;
for ( uint64_t i = 0; i < ternary.length(); ++i ) { // Right part of palindrome is the mirror image of left part
if ( ternary[i] > '0' ) {
result += ( ternary[i] - '0' ) * power_of_3;
}
power_of_3 *= 3;
}
result += power_of_3; // Middle digit must be 1
power_of_3 *= 3;
result += number * power_of_3; // Left part is the given number multiplied by the appropriate power of 3
return result;
}
int main() {
std::cout << "The first 6 numbers which are palindromic in both binary and ternary are:" << std::endl;
display(0); // 0 is a palindrome in all 3 bases
display(1); // 1 is a palindrome in all 3 bases
uint64_t number = 1;
uint32_t count = 2;
do {
uint64_t ternary = create_ternary_palindrome(number);
if ( ternary % 2 == 1 ) { // Cannot be an even number since its binary equivalent would end in zero
std::string binary = to_base_string(ternary, 2);
if ( binary.length() % 2 == 1 ) { // Binary palindrome must have an odd number of digits
if ( is_palindromic(binary) ) {
display(ternary);
count++;
}
}
}
number++;
}
while ( count < 6 );
}
</syntaxhighlight>
{{ out }}
<pre>
The first 6 numbers which are palindromic in both binary and ternary are:
Decimal: 0
Binary : 0
Ternary: 0
Decimal: 1
Binary : 1
Ternary: 1
Decimal: 6643
Binary : 1100111110011
Ternary: 100010001
Decimal: 1422773
Binary : 101011011010110110101
Ternary: 2200021200022
Decimal: 5415589
Binary : 10100101010001010100101
Ternary: 101012010210101
Decimal: 90396755477
Binary : 1010100001100000100010000011000010101
Ternary: 22122022220102222022122
</pre>
Line 612 ⟶ 717:
5415589 101012010210101(3) 10100101010001010100101(2)
90396755477 22122022220102222022122(3) 1010100001100000100010000011000010101(2)</pre>
=={{header|EasyLang}}==
<syntaxhighlight>
fastfunc ispalin2 n .
m = n
while m > 0
x = x * 2 + m mod 2
m = m div 2
.
if n = x
return 1
.
.
fastfunc reverse3 n .
while n > 0
r = r * 3 + n mod 3
n = n div 3
.
return r
.
func$ itoa n b .
if n > 0
return itoa (n div b) b & n mod b
.
.
proc main . .
print "0 0(2) 0(3)"
print "1 1(2) 1(3)"
pow3 = 3
while 1 = 1
for i = pow3 / 3 to pow3 - 1
# assumption that the middle digit must be 1
n = (i * 3 + 1) * pow3 + reverse3 i
if ispalin2 n = 1
print n & " " & itoa n 2 & "(2) " & itoa n 3 & "(3)"
cnt += 1
if cnt = 6 - 2
return
.
.
.
pow3 *= 3
.
.
main
</syntaxhighlight>
{{out}}
<pre>
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)
</pre>
=={{header|Elixir}}==
Line 1,126 ⟶ 1,286:
5415589, 10100101010001010100101, 101012010210101
90396755477, 1010100001100000100010000011000010101, 22122022220102222022122</pre>
Alternatively, using a simple and efficient algorithm, the first six number are found in less than a second.
<syntaxhighlight lang="java">
public final class FindPalindromicNumbersBases23 {
public static void main(String[] aArgs) {
System.out.println("The first 7 numbers which are palindromic in both binary and ternary are:");
display(0); // 0 is a palindrome in all 3 bases
display(1); // 1 is a palindrome in all 3 bases
long number = 1;
int count = 2;
do {
long ternary = createTernaryPalindrome(number);
if ( ternary % 2 == 1 ) { // Cannot be an even number since its binary equivalent would end in zero
String binary = toBinaryString(ternary);
if ( binary.length() % 2 == 1 ) { // Binary palindrome must have an odd number of digits
if ( isPalindromic(binary) ) {
display(ternary);
count++;
}
}
}
number++;
}
while ( count < 7 );
}
// Create a ternary palindrome whose left part is the ternary equivalent of the given number
// and return its decimal equivalent
private static long createTernaryPalindrome(long aNumber) {
String ternary = toTernaryString(aNumber);
long powerOf3 = 1;
long sum = 0;
for ( int i = 0; i < ternary.length(); i++ ) { // Right part of a palindrome is the mirror image of left part
if ( ternary.charAt(i) > '0' ) {
sum += ( ternary.charAt(i) - '0' ) * powerOf3;
}
powerOf3 *= 3;
}
sum += powerOf3; // Middle digit must be 1
powerOf3 *= 3;
sum += aNumber * powerOf3; // Left part is the given number multiplied by the appropriate power of 3
return sum;
}
private static boolean isPalindromic(String aNumber) {
return aNumber.equals( new StringBuilder(aNumber).reverse().toString() );
}
private static String toTernaryString(long aNumber) {
if ( aNumber == 0 ) {
return "0";
}
StringBuilder result = new StringBuilder();
while ( aNumber > 0 ) {
result.append(aNumber % 3);
aNumber /= 3;
}
return result.reverse().toString();
}
private static String toBinaryString(long aNumber) {
return Long.toBinaryString(aNumber);
}
private static void display(long aNumber) {
System.out.println("Decimal: " + aNumber);
System.out.println("Binary : " + toBinaryString(aNumber));
System.out.println("Ternary: " + toTernaryString(aNumber));
System.out.println();
}
}
</syntaxhighlight>
{{ out }}
<pre>
The first 7 numbers which are palindromic in both binary and ternary are:
Decimal: 0
Binary : 0
Ternary: 0
Decimal: 1
Binary : 1
Ternary: 1
Decimal: 6643
Binary : 1100111110011
Ternary: 100010001
Decimal: 1422773
Binary : 101011011010110110101
Ternary: 2200021200022
Decimal: 5415589
Binary : 10100101010001010100101
Ternary: 101012010210101
Decimal: 90396755477
Binary : 1010100001100000100010000011000010101
Ternary: 22122022220102222022122
Decimal: 381920985378904469
Binary : 10101001100110110110001110011011001110001101101100110010101
Ternary: 2112200222001222121212221002220022112
</pre>
=={{header|JavaScript}}==
Line 1,263 ⟶ 1,530:
5415589 101012010210101 10100101010001010100101
90396755477 22122022220102222022122 1010100001100000100010000011000010101 </pre>
=={{header|jq}}==
'''Adapted from [[#Wren|Wren]]'''
The C (jq) and Go (gojq) implementations of jq produce correct results for the first 6 numbers,
as shown below.
jq's "number" type lacks the integer arithmetic precision required to compute the next number
in the sequence, and gojq's memory management is not up to the task even on a generously endowed machine.
'''Generic Utilities'''
<syntaxhighlight lang=jq>
# Convert the input integer to a string in the specified base (2 to 36 inclusive)
def convert(base):
def stream:
recurse(if . >= base then ./base|floor else empty end) | . % base ;
[stream] | reverse
| if base < 10 then map(tostring) | join("")
elif base <= 36 then map(if . < 10 then 48 + . else . + 87 end) | implode
else error("base too large")
end;
# integer division using integer operations only
def idivide($i; $j):
($i % $j) as $mod
| ($i - $mod) / $j ;
def idivide($j):
idivide(.; $j);
# If cond then show the result of update before recursing
def iterate(cond; update):
def i: select(cond) | update | (., i);
i;
</syntaxhighlight>
'''The Task'''
<syntaxhighlight lang=jq>
def isPalindrome2:
if (. % 2 == 0) then . == 0
else {x:0, n: .}
| until(.x >= .n;
.x = .x*2 + (.n % 2)
| .n |= idivide(2) )
| .n == .x or .n == (.x|idivide(2))
end;
def reverse3:
{n: ., x: 0}
| until (.n == 0;
.x = .x*3 + (.n % 3)
| .n |= idivide(3) )
| .x;
def show:
"Decimal : \(.)",
"Binary : \(convert(2))",
"Ternary : \(convert(3))",
"";
def task($count):
"The first \($count) numbers which are palindromic in both binary and ternary are:",
(0|show),
({cnt:1, lo:0, hi:1, pow2:1, pow3:1}
| iterate( .cnt < $count;
.emit = null
| .i = .lo
| until (.i >= .hi or .emit;
((.i*3+1)*.pow3 + (.i|reverse3)) as $n
| if $n|isPalindrome2
then .emit = [$n|show]
| .cnt += 1
else .
end
| .i += 1 )
| if .cnt == $count then . # all done
else if .i == .pow3
then .pow3 *= 3
else .pow2 *= 4
end
| .break = false
| until( .break;
until(.pow2 > .pow3; .pow2 *= 4)
| .lo2 = idivide( idivide(.pow2;.pow3) - 1; 3)
| .hi2 = (idivide(idivide(.pow2*2;.pow3)-1;3) + 1)
| .lo3 = (.pow3|idivide(3))
| .hi3 = .pow3
| if .lo2 >= .hi3 then .pow3 *= 3
elif .lo3 >= .hi2 then .pow2 *= 4
else .lo = ([.lo2, .lo3]|max)
| .hi = ([.hi2, .hi3]|min)
| .break = true
end )
end)
| select(.emit).emit[] );
task(6)
</syntaxhighlight>
<pre>
The first 6 numbers which are palindromic in both binary and ternary are:
Decimal : 0
Binary : 0
Ternary : 0
Decimal : 1
Binary : 1
Ternary : 1
Decimal : 6643
Binary : 1100111110011
Ternary : 100010001
Decimal : 1422773
Binary : 101011011010110110101
Ternary : 2200021200022
Decimal : 5415589
Binary : 10100101010001010100101
Ternary : 101012010210101
Decimal : 90396755477
Binary : 1010100001100000100010000011000010101
Ternary : 22122022220102222022122
</pre>
=={{header|Julia}}==
Line 1,814 ⟶ 2,203:
<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: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">base</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">2</span> <span style="color: #008080;">and</span> <span style="color: #000000;">base</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">9</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (>9 as below)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
Line 1,823 ⟶ 2,213:
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">q</span><span style="color: #0000FF;">,</span><span style="color: #000000;">base</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">+</span><span style="color: #008000;">'0'</span> <span style="color: #000080;font-style:italic;">-- +(r>9)*('A'-'9'-1)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000080;font-style:italic;">-- res = reverse(res) -- (if not palindromic!)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">A</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"0"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"6643"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1422773"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"5415589"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"90396755477"</span><span style="color: #0000FF;">,</span>
Line 1,850 ⟶ 2,233:
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">A</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #
<span style="color: #
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre style="font-size: 11px">
0
0
Line 1,891 ⟶ 2,274:
2202021211210100110100002202101000110000220121210220000110001012022000010110010121121202022
</pre>
=={{header|Picat}}==
<syntaxhighlight lang="picat">
Line 3,105 ⟶ 3,489:
{{libheader|Wren-fmt}}
Just the first 6 palindromes as the 7th is too large for Wren to process without resorting to BigInts.
<syntaxhighlight lang="
var isPalindrome2 = Fn.new { |n|
| |||