[C/C++] Project Euler #29 Distinct Powers

This problem involves handling duplicates, but due to the large range of numbers, you’ll need to either use big integers for processing or come up with some other approach.

To calculate the number of distinct \(a^b\) values, consider the following:

For different a and b (where b > a), \(a^m\) and \(b^n\) will yield the same result only if b is a power of a. Otherwise, it’s impossible for the same number to appear.

Based on this logic, I wrote a program.

The first part of the program processes non-power values of a, computing all \(a^k\) values. These results are stored in an array called v, separated by cases: when only the 1st power is possible, up to when the n-th power is possible.

For example, if we consider the number 3, the distinct powers under 100 are 3, 9, 27, 81. Since 3 can go up to the 4th power under 100, there are 100 distinct n-th powers when considering all cases from \(3^1\) to \(3^{100}\).  However, the powers of 9 (\(9^1\) to \(9^{100}\)) exclude even powers from \(3^2\) to \(3^{100}\). This method lets us calculate all distinct n-th powers related to the base number 3, including those associated with 9, 27, and 81.

The second part of the program simulates the actual computation of \(a^n\).

By doing this, we can significantly reduce the computational load while efficiently handling big integer operations and duplicate elimination.

 

distinct powers

The program I wrote is for reference.

//------------------------------------------------
//    Project Euler #29 - Distinct Powers
//        - by Aubrey Choi
//        - created at 2015-10-15
//------------------------------------------------
#include <stdio.h>
#include <memory.h>

int main()
{
    int n = 100;
    int md = 1;
    while( n>>md ) md++;
    int v[100];

    char check[1000];
    memset(check, 0, sizeof(check));
    for( int i = 1, ls = 0 ; i < md ; i++ )
    {
        for( int j = 2 ; j <= n ; j++ ) 
            if( !check[i*j] ) { check[i*j] = 1; ls++; }
        v[i] = ls;
    }

    int sum = 0;
    memset(check, 0, sizeof(check));
    for( int a = 2 ; a <= n ; a++ )
    {
        if( check[a] ) continue;
        int c = 1;
        int t = a*a;
        for( ; t <= n ; t *= a, c++ ) check[t] = 1;
        sum += v[c];
    }

    printf("Ans = %d\n", sum);
}

 

It can be done much more simply using Python. The following source code is the Python version.

 

from sets import Set
set = Set([])
for a in range(2,101):
    for b in range(2,101):
    set.add(a**b)
        
print len(set)