How to resolve the algorithm Find palindromic numbers in both binary and ternary bases step by step in the C++ programming language
Published on 7 June 2024 03:52 AM
How to resolve the algorithm Find palindromic numbers in both binary and ternary bases step by step in the C++ programming language
Table of Contents
Problem Statement
It's permissible to assume the first two numbers and simply list them.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Find palindromic numbers in both binary and ternary bases step by step in the C++ programming language
This C++ program finds the first six numbers that are palindromic in both binary and ternary number systems. Here's a detailed explanation of the code:
-
to_base_string
Function:- This function converts a decimal number (
number
) to a string representing its value in the specifiedbase
. - It iteratively calculates the remainders when dividing the number by the base, converts them to characters, and appends them to a result string.
- Finally, it reverses the result string and returns it.
- This function converts a decimal number (
-
display
Function:- This function displays the decimal representation of a number, its binary representation (base 2), and its ternary representation (base 3) on the console.
-
is_palindromic
Function:- This function checks if a given string (
number
) is a palindrome by comparing it with its reverse.
- This function checks if a given string (
-
create_ternary_palindrome
Function:- This function creates a ternary palindrome whose left part is the ternary equivalent of the given
number
. - It first converts the number to a ternary string.
- Then, it iteratively processes the ternary string from right to left, mirroring the digits to create the right part of the palindrome.
- It adds a '1' as the middle digit and multiplies the given number by the appropriate power of 3 to create the left part.
- Finally, it combines the left and right parts to form the ternary palindrome and returns it.
- This function creates a ternary palindrome whose left part is the ternary equivalent of the given
-
main
Function:- The program starts by displaying the first two numbers (0 and 1) which are palindromic in all three bases (decimal, binary, and ternary).
- It initializes a loop that continues until six numbers have been found that satisfy the conditions.
- Inside the loop:
- It creates a ternary palindrome for the current number (
number
). - It checks if the ternary palindrome is odd (binary palindromes cannot be even).
- If the ternary palindrome is odd, it converts it to binary and checks if its length is odd (odd-length binary strings can be palindromes).
- If both conditions are met and the binary representation is palindromic, it displays the number and increments the count.
- The loop continues until six such numbers are found.
- It creates a ternary palindrome for the current number (
Source code in the cpp programming language
#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 );
}
You may also check:How to resolve the algorithm Last Friday of each month step by step in the 360 Assembly programming language
You may also check:How to resolve the algorithm 99 bottles of beer step by step in the Verilog programming language
You may also check:How to resolve the algorithm Exponentiation order step by step in the ALGOL W programming language
You may also check:How to resolve the algorithm Evaluate binomial coefficients step by step in the Racket programming language
You may also check:How to resolve the algorithm Chinese remainder theorem step by step in the Ruby programming language