In this article, we will discuss how to check whether a number is Edqidigital or not. Before going into this, let's understand what is Equidigital number .
What is the Equidigital Number?
An n-digit number is called an Equidigital number if the number of digits in the prime factorization of n (including powers) is the same as the number of digits in n. For instance, 16 is an Equidigital number as prime factorization of 2 by 2 is 2^4. It has a total number of two digits (2 and 4), which is similar to its prime factorization, which is 2^7, which has a total of 2 digits (2 and 7), whereas the number has 3 digits (1,2 and 8). So, 128 is not an Equidigital number.
Solution Approach:
One possible solution to this problem is to find the factors of the number and then compare them to the number of primes with the same number of digits. The prime factors can be determined with the use of the sieves method.
Algorithm:
Step 1: First, search out all prime numbers.
Step 2: Next, find the number of digits in the number n.
Step 3: Take all prime factors of the number and count the number of digits in it.
Step 4: Now compare both the values.
Step 5: After that, if the condition is true, return the number.
Example:
Let us take an example to find the Equidigital Numbers in C++.
#include<bits/stdc++.h>
using namespace std;
const int MAX = 10000;
// an array for storing the prime numbers up to the max value
vector <int> primeNumbers;
// The Algorithm
void sieveSundaramAlgorithm()
{
// This one describes the sieve of Sundaram, a tool for generating prime numbers.
// 2*x + 2-> where x is a given number. (2x+2) modifies then (x - 2*x -2)
//We want primes smaller than MAX, so we reduce MAX to half
// This array is used to distinguish the numbers that are written with letters.
//The Range
// i+j+2i-j from others where 1 <= i <= j is defined.
bool markedArray[MAX/2 + 1] = {0};
// Marking the non-prime numbers
for (int i=1; i<=(sqrt(MAX)-1)/2; i++)
for (int j=(i*(i+1))<<1; j<=MAX/2; j=j+2*i+1)
markedArray[j] = true;
// as 2 is prime, then push back
primeNumbers.push_back(2);
// display of the other prime numbers
for (int i=1; i<=MAX/2; i++)
if (markedArray[i] == false)
primeNumbers.push_back(2*i + 1);
}
// the boolean condition to check
//the number is Equidigital or nor
bool isEquidigitalNumber(int num) {
if (num == 1)
return true;
// to check the count of the numbers in the num
int original_number = num;
int sumOftheDigits = 0;
while (original_number > 0)
{
sumOftheDigits++;
original_number = original_number/10;
}
// counting the digits of the prime number
// the primeDigit will hold the values
int primeDigit = 0 , count_exponent = 0, prime;
for (int i = 0; primeNumbers[i] <= num/2; i++)
{
// Count powers of p in n
while (num % primeNumbers[i] == 0)
{
prime = primeNumbers[i];
num = num/prime;
// Find the power of the prime numbers
count_exponent++;
}
// add the count of the digits to primeDigit
while (prime > 0)
{
primeDigit++;
prime = prime / 10;
}
// Adding the power of digital to count-exponent
while (count_exponent > 1)
{
primeDigit++;
count_exponent = count_exponent / 10;
}
}
//If the condition is true, the
//number has 1 prime factor
if (num != 1)
{
while (num > 0)
{
primeDigit++;
num = num/10;
}
}
//If the prime factors and the initial number have the same
// number of digits, then it returns true.
return (primeDigit == sumOftheDigits);
} // Driver code
int main() {
// Finding all the prime numbers
//in the given range
sieveSundaramAlgorithm();
cout << "The Equidigital numbers are: \n";
for (int i=10; i<30; i++)
if (isEquidigitalNumber(i))
cout << i << " ";
return 0;
}
Output:
The Equidigital numbers are:
10 13 14 16 19 21 23 25 27 29
Explanation:
The C++ program is based on the sieve of Sundaram algorithm for prime numbers generation and detecting equidigital numbers. Equidigital numbers have their digit count equal to the count of their prime factors. The isEquidigitalNumber function is given to determine if a given number is equidigital. It takes the number of digits and executes cycles through the prime numbers to check for the factors. If a prime factor exists, it determines the digit in the factor and sums them up to primeDigit .
The equation has the operand of the prime exponent also. Thus, the product (abcd...)(r1r2r3...rN) represents the outcome of the multiplication of all prime factors and their respective digit counts until every factor is reduced to a value less than or equal to 1. The function compares the result of primeDigit while iterating through and counting all digits in the original number (sumOftheDigits). If they match, the number is equidigital, and the return statement is true. In the main function, a sequence of prime numbers is produced, then the check for equidigital numbers from 10 to 29 is performed using the isEquidigitalNumber function. After that, Equidigital numbers are printed.
Conclusion:
In conclusion, the program uses the Sundaram sieve algorithm to generate prime numbers and to see for equidigital numbers. Digital numbers of equal length are those whose prime factorization contains the same number of digits as in the original number. The function of the program is to compute and compare the number of digits and prime factors of those two numbers and return True when they are equal. As a result, it helps to determine the effectiveness of prime factorization and digit counting in finding the Equidigital integers.