Self Numbers In C++

What are Self Numbers?

A Self Number is a unique type of number within the realm of mathematics. It differs in that it is not attainable by adding a number to the total of its individual digits. Essentially, it remains distinct as no alternative number yields it through the application of a designated function known as the "generator function."

What is a Generator Function?

A generator function operates in the following manner:

• ✅ Receive an input of a number, denoted as n.
• ✅ Sum the digits of the number n and add it to n.

For example:

• ✅ For n=21, the sum of the digits is 2+1=3.
• ✅ The generator function would give 21+3=24.

So, the number 24 is considered a non-self number as it is generated by the number 21.

Identifying Self Numbers

A number is considered a self number when there is no other value n for which the generator function results in the same number.

For instance, numbers like

• ✅ 1,3,5,7,9__ are considered self numbers since they cannot be generated by any other number through a specific function.

Approach 1: Simple Approach

Example:

#include <iostream>
#include <vector>
using namespace std;
// Function to calculate the generator of a number
int generator(int n) {
    int sum = n;
    while (n > 0) {
        sum += n % 10;  // Add the last digit of n
        n /= 10;        // Remove the last digit
    }
    return sum;
}
int main() {
    const int LIMIT = 100; // Define the range to find self numbers
    vector<bool> isSelfNumber(LIMIT + 1, true); // Initialize all as true
    // Mark numbers that are not self numbers
    for (int i = 1; i <= LIMIT; i++) {
        int gen = generator(i);
        if (gen <= LIMIT) {
            isSelfNumber[gen] = false; // Mark generated numbers as false
        }
    }
    // Print all self numbers
    cout << "Self Numbers from 1 to " << LIMIT << " are:\n";
    for (int i = 1; i <= LIMIT; i++) {
        if (isSelfNumber[i]) {
            cout << i << " ";
        }
    }
    cout << endl;
    return 0;
}

Output:

Self Numbers from 1 to 100 are:
1 3 5 7 9 20 31 42 53 64 75 86 97

Explanation:

Step 1: Understanding the Purpose

The objective of the script is to identify self numbers within the range of 1 to 100. A self number is a numeric value that is unable to be formed by adding another number to the total sum of its individual digits. For instance, 21 is not considered a self number since it can be derived from 15 (15 + 1 + 5 = 21). Conversely, 1, 3, and 5 are classified as self numbers because they cannot be generated by any other number.

Step 2: Generator Function

The generator function is a basic mathematical operation that involves taking a numerical input, adding the sum of its individual digits to the input, and then producing the final output.

• ✅ As an illustration, consider the case where n=15. In this scenario, the individual digits are 1 and 5. When these digits are added together (1+5), the result is 6. Adding this sum to the original number 15 (15+6) yields 21. Therefore, the generator of 15 is 21.

This generator function assists in identifying numbers that are not self numbers since any number generated by this function is not a self number.

Step 3: Marking Non-Self Numbers

Assumes at the beginning that all numbers are self numbers.

During the calculation of the generator function for each number, it flags the generated numbers as non-self numbers.

This process involves utilizing an array (or list) named isSelfNumber to monitor the status of numbers being self numbers:

When isSelfNumber[x] is true, it indicates that x is a self number.

Conversely, when isSelfNumber[x] is false, it signifies that x is not a self number as it was produced by another number.

Step 4: Loop Through Numbers

The software iterates over integers ranging from 1 to 100. With each integer:

• ✅ It computes the output of the generator.
• ✅ In case the output falls within the specified range (1 to 100), it flags that integer as false in the isSelfNumber array.

This labeling guarantees the identification of all generated numbers as non-self numbers.

Step 5: Finding Self Numbers

After identifying all non-self numbers, the software loops through the isSelfNumber array once more. Any number that remains flagged as true is displayed as a self number since it was not derived from any other number.

Example Walkthrough

Let's go through an example to see how the logic works:

• ✅ Start with number 1: Generator function: 1+1=2. Mark 2 as not a self number.
• ✅ Move to number 2: Generator function: 2+2=4. Mark 4 as not a self number.
• ✅ Continue with number 3: Generator function: 3+3=6. Mark 6 as not a self number.
• ✅ After processing all numbers: Numbers like 1, 3, 5, 7, 9, etc., remain unmarked because no other number generated them. These are self numbers.
• ✅ Generator function: 1+1=2.
• ✅ Mark 2 as not a self number.
• ✅ Generator function: 2+2=4.
• ✅ Mark 4 as not a self number.
• ✅ Generator function: 3+3=6.
• ✅ Mark 6 as not a self number.
• ✅ Numbers like 1, 3, 5, 7, 9, etc., remain unmarked because no other number generated them. These are self numbers.

Step 6: Output the Result

Eventually, the software displays all the numbers that remain labeled as true in the isSelfNumber array. These particular numbers represent the self-contained values falling within the specified range.

Time Complexity

Outer Iteration:

• ✅ Goes through each number between 1 and n inclusively. This operation has a time complexity of O(n).

Generator Function:

• ✅ Iterating through each number, the function computes the total of its individual digits.
• ✅ Given that a number i typically consists of approximately O(log10(i)) digits, the generator function operates in O(log(i)) time complexity.

Total Time Complexity:

When considering all n elements, the overall complexity amounts to: O(n⋅log(n))

Space Complexity

Array for Monitoring:

• ✅ A boolean array comprising n+1 elements is employed to monitor self-numbers.
• ✅ This necessitates O(n) space allocation.

Other Variables:

• ✅ Several transient variables are employed for computations, requiring constant space complexity O(1).

Total Space Complexity:

The space complexity is mainly influenced by the array, resulting in a space complexity of O(n).

Approach 2: Using Mathematical Elimination

Instead of explicitly determining the generator function for each number, we can efficiently detect non-self numbers by iterating through the range and flagging the generated numbers. This approach eliminates the necessity for a boolean array and minimizes repetitive computations.

Program:

#include <iostream>
#include <unordered_set>
using namespace std;
// Function to calculate the generator of a number
int generator(int n) {
    int sum = n;
    while (n > 0) {
        sum += n % 10;  // Add the last digit of n
        n /= 10;        // Remove the last digit
    }
    return sum;
}
int main() {
    const int LIMIT = 100; // Define the range to find self numbers
    unordered_set<int> generatedNumbers; // Set to store generated numbers
    // Calculate generated numbers
    for (int i = 1; i <= LIMIT; i++) {
        int gen = generator(i);
        if (gen <= LIMIT) {
            generatedNumbers.insert(gen); // Add generated number to the set
        }
    }
    // Print all self numbers
    cout << "Self Numbers from 1 to " << LIMIT << " are:\n";
    for (int i = 1; i <= LIMIT; i++) {
        if (generatedNumbers.find(i) == generatedNumbers.end()) {
            // If number is not in the set, it is a self number
            cout << i << " ";
        }
    }
    cout << endl;
    return 0;
}

Output:

Self Numbers from 1 to 100 are:
1 3 5 7 9 20 31 42 53 64 75 86 97

Explanation:

Step 1: Purpose of the Code

The script detects self-numbers within a specified range (1 to 100 in this instance). A self-number is a unique number that cannot be obtained by adding any combination of its digits to the original number. For instance:

• ✅ The number 21 is not considered a self-number since it can be created by 15 (15 + 1 + 5 = 21).
• ✅ On the contrary, numbers like 1, 3, 5, and various others are self-numbers as they have no possible combination that generates them.

Step 2: Generator Function

The generator function computes the "generator" value of a given number.

For a specified value n, it calculates the sum of n added to its individual digits.

For instance:

• ✅ When n equals 15, the individual digits are 1 and 5. When added together, they result in 1+5=6, and subsequently, 15+6=21.
• ✅ Hence, the output of 15 as a generator is 21.

This function assists in distinguishing between generated numbers and those that are not.

Step 3: Storing Generated Numbers

Instead of opting for a sizable array to monitor the produced numbers, the code employs an unordered_set for this purpose.

The rationale behind using a set lies in its property of retaining solely distinct values, thereby eliminating any possibility of redundancy.

During the computation of generators, each newly generated number is appended to the set.

• ✅ In the case where n equals 15, the generator becomes 21, resulting in the addition of 21 to the set.
• ✅ In the scenario where n is 20, the generator changes to 22, leading to the inclusion of 22 in the set.

Step 4: Identifying Self Numbers

Once all produced numbers are saved in the set:

The software iterates over every number within the range of 1 to 100.

For every numerical value:

• ✅ The number is verified to be absent from the set.
• ✅ In case it's absent, it qualifies as a self number and is displayed.

For instance:

• ✅ Figures such as 1, 3, 5, etc., are excluded from the group as they cannot be produced by any number.
• ✅ Figures like 21, 22, and so on are part of the group, hence they are not self-numbers.

Step 5: Output

The software displays all numbers within the specified range that are not part of the given set, identifying them as self numbers.

For a series spanning from 1 to 100, the resulting sequence includes: 1 3 5 7 9 20 31 42 53 64 75 86 97

Advantages of This Approach

Optimal Memory Utilization:

• ✅ The set only retains the computed numbers, resulting in decreased memory consumption in contrast to preserving all numbers.

Efficient Retrieval:

Verifying the presence of a number within a set is fast and effective.

Clean Procedure:

By employing a set, the procedure becomes more streamlined as it directly targets the produced numbers, eliminating the need for redundant array manipulations.

Complexity analysis:

Time Complexity:

Generator Function:

When determining the generator for a given number, the time complexity is O(log(n)) due to the summation of its digits.

This process is repeated for all numbers ranging from 1 to LIMIT, resulting in an overall time complexity of O(LIMIT⋅log(LIMIT)).

Checking for Self Numbers:

Every number is validated within the set, with a time complexity of O(1) for each number.

When considering LIMIT numbers, the time complexity increases to O(LIMIT).

Total Time Complexity: O(LIMIT⋅log(LIMIT))

Space Complexity

Generated Numbers Storage:

The unordered_set can hold a maximum of LIMIT numbers, utilizing O(LIMIT) memory space.

Temporary Variables:

• ✅ Utilizes constant space for loop and generator variables.

Total Space Complexity: O(LIMIT)

Approach 3: Using Reverse Mapping

This method operates by inversely undoing the number generation process. Rather than determining the produced numbers, we aim to "invert" the function that generates numbers for each value within the specified range. This approach eliminates the necessity of utilizing sets or arrays to monitor generated numbers, enhancing its efficiency in terms of memory consumption.

Program:

#include <iostream>
using namespace std;
// Function to calculate the sum of digits of a number
int sumOfDigits(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;  // Add the last digit to the sum
        n /= 10;        // Remove the last digit
    }
    return sum;
}
// Function to check if a number is a self number
bool isSelfNumber(int n) {
    for (int x = 1; x < n; x++) {
        if (x + sumOfDigits(x) == n) {
            // If any number x generates n, it is not a self number
            return false;
        }
    }
    return true; // If no x generates n, it is a self number
}
int main() {
    const int LIMIT = 100; // Define the range to find self numbers
    cout << "Self Numbers from 1 to " << LIMIT << " are:\n";
    // Check for self numbers in the range
    for (int i = 1; i <= LIMIT; i++) {
        if (isSelfNumber(i)) {
            cout << i << " "; // Print the self number
        }
    }
    cout << endl;
    return 0;
}

Output:

Self Numbers from 1 to 100 are:
1 3 5 7 9 20 31 42 53 64 75 86 97

Explanation:

Step 1: Purpose of the Code

The objective is to recognize self numbers, which are numbers that cannot be produced by adding a number to the sum of its digits. For instance:

• ✅ 21 is not considered a self number since it can be created by 15 (15 + 1 + 5 = 21).
• ✅ 1, 3, 5, and so forth, qualify as self numbers because no other number can generate them.

Step 2: Sum of Digits Function

The initial section of the code comprises a utility function that computes the total of the digits within a given number. For instance:

When n=15, the individual digits are 1 and 5, leading to a sum of 1+5=6.

This particular function plays a crucial role in determining whether a number x has the capability to produce another number n.

Step 3: Checking if a Number is a Self Number

To determine if a number n is a self number:

• ✅ The program loops through all numbers x less than n.
• ✅ For each x, it calculates x+sum of digits of x.
• ✅ If this value equals n, it means n can be generated by x, so n is not a self number.
• ✅ If no such x exists, n is a self number.

For example:

For the value of n being 21:

When x=15: 15 + (1 + 5) = 21. Therefore, 21 is not considered a self number.

For n=3:

• ✅ No value of x less than 3 results in 3. Therefore, 3 is considered a self number.

Step 4: Loop Through the Range

The software iterates over every number within the defined range (from 1 to 100 in this instance):

It examines each number based on the self-number algorithm described earlier.

In the event that a number qualifies as a self number, it displays the number.

For instance:

• ✅ Figures such as 1, 3, 5, and 7 are considered self numbers as they are not produced by any smaller numbers.
• ✅ In contrast, figures like 21 and 42 are not self numbers since they are derived from other numbers.
• ✅ The result will display a compilation of all self numbers within the specified range. In the interval from 1 to 100, the self numbers identified are as follows:
• ✅ 1 3 5 7 9 20 31 42 53 64 75 86 97

Advantages:

Numerous benefits of Self Numbers in C++ include:

No Additional Memory:

The code operates without utilizing arrays or sets, thereby conserving memory.

Straightforward Reasoning:

• ✅ It directly proceeds from the concept of self numbers by reversing the generation procedure.

Easy to Grasp:

• ✅ The method is straightforward and functions effectively with narrow intervals such as 1 to 100.

Complexity Analysis:

Time Complexity

• ✅ For each number n, it checks all smaller numbers x to see if x generates n.
• ✅ The digit sum calculation adds a small cost.
• ✅ Total Time Complexity: O(LIMIT^2 ⋅log(LIMIT)).

Space Utilization

Instead of employing additional data structures, the algorithm relies solely on a minimal number of variables.

Overall, the Space Complexity remains constant at O(1).

Properties:

Several characteristics of Self Numbers in C++ include:

Uniqueness is a key characteristic of each self number as it cannot be produced by any number smaller than itself.

An illustration of this concept is the number 3, which stands out due to the absence of any value x where x + sumDigits(x) equals 3.

Range Neutrality

• ✅ Self numbers are present across various numerical intervals.
• ✅ Within every limited numerical range, there will consistently exist certain numbers classified as self numbers.

As values escalate, the difference between successive self numbers expands. With higher numerical values, there is a greater probability of producing larger numbers due to their increased x+ sumDigits(x) total. Consequently, the occurrence of self numbers decreases.

Infinite Quantity

• ✅ The collection of self numbers is boundless. Not every numerical value can be represented as the sum of its digits plus the original number, guaranteeing the presence of self numbers within any given range.