Project Euler #29 alternative solution

Question

This is a question about a Project Euler problem. This is where you can find the description of the problem: https://projecteuler.net/problem=29

OK, first of all, let me clarify that I have solved this problem, I am just looking for an alternative solution that is based more on maths.
Second, in order to not spoil the problem for anyone that has not solved, please if you have not solved it, don't continue. :)

So, I solved this problem using Python and because it has support for big numbers and list comprehensions, I was able to come up with an one liner:

print(len(set([a ** b for a in range(2, 101) for b in range(2, 101)])))

Now, I am trying to solve it in C, by using more mathematical knowledge(C natively has no support for big numbers, or list comprehensions). I came across this thread: PROJECT EULER #29 where the accepted answer gave me some ideas and I came up with this code:

int main(void) {

    int found[1000];    // an array where I hold the found values(0 or 1)
    int e, b, i, count, x;

    count = 0;     // number of duplicates
    x = 3;
    for(i = 0; i < 1000; i++)
         found[i] = 0;


    for(e = 1; (int)pow(x, e) <= 100; e++) {
        for(b = 2; b <= 10; b++) {
            if(found[e * b])    // if the value has been found, then we have duplicate
                count++;
            found[e * b] = 1;   // mark that we found the value
        }
    }

    printf("count: %d\n", count);

    return 0;
}

With this code, I am doing what you can see on the bottom of the answer above, where he shows some diagrams on how the to find the duplicates for x = 3, based on what he has explained previously. I am trying to do the same thing. Now, if you run my code, it correctly outputs 13, based on the diagrams of the above answer, which is the number of the duplicates.

So, I tried to extend it to solve the actual project euler problem because if I am able to find the number of duplicates, then I will just subtract it from the number 99 * 99(which is the possible power combinations because 2 <= a <= 100 and 2 <= b <= 100) and that would be the answer. The result was that:

int main(void) {

    int found[1000];
    int e, b, i, count, x;

    count = 0;
    for(x = 2; x <= 100; x++) {
        for(i = 0; i < 1000; i++)
             found[i] = 0;


        for(e = 1; (int)pow(x, e) <= 100; e++) {
            for(b = 2; b <= 100; b++) {
                if(found[e * b])
                    count++;
                found[e * b] = 1;
            }
        }
    }

    printf("count: %d\n", count);

    return 0;
}

If you pay attention, the changes are that I loop for all the xs from 2 to 100 and b is not going from 2 to 10 but from 2 to 100.
However, the program prints 814, which is incorrect. It should be 618. Any help is highly appreciated! I am probably counting some duplicates twice, but where? What is wrong with the code? Also, if you have any mathematical explanations that would help construct a new algorithm, this is highly appreciated too!

EDIT:
Something that I forgot to mention is that if instead of putting:
for(x = 2; x <= 100; x++) I do:
for(x = 2; x <= 6; x++)
i.e. stop to 6, it prints the correct answer. And that is even more bizzarre.

EDIT2:
Let me also note that for 8 and 9(instead of 100) it gives correct results. 44 and 54 respectively.

Answer 1

the observation to find overlapped numbers is as flow
first lets make the range from 2 to 10 so the numbers will be like
2², 2³, 2⁴, 2⁵, 2⁶, 2⁷, 2⁸, 2⁹, 2¹⁰
3², 3³, 3⁴, 3⁵, 3⁶, 3⁷, 3⁸, 3⁹, 3¹⁰
4², 4³, 4⁴, 4⁵, 4⁶, 4⁷, 4⁸, 4⁹, 4¹⁰
5², 5³, 5⁴, 5⁵, 5⁶, 5⁷, 5⁸, 5⁹, 5¹⁰
6², 6³, 6⁶, 6⁵, 6⁶, 6⁷, 6⁸, 6⁹, 6¹⁰
7², 7³, 7⁷, 7⁵, 7⁷, 7⁷, 7⁸, 7⁹, 7¹⁰
8², 8³, 8⁸, 8⁵, 8⁸, 8⁸, 8⁸, 8⁹, 8¹⁰
9², 9³, 9⁴, 9⁵, 9⁶, 9⁷, 9⁹, 9⁹, 9¹⁰
10², 10³, 10⁴, 10⁵, 10⁶, 10⁷, 10⁸, 10⁹, 10¹⁰
the key point is 4² = (2²)² = 2⁴ so
4², 4³, 4⁴, 4⁵, 4⁶, 4⁷, 4⁸, 4⁹, 4¹⁰ will be 2⁴, 2⁶, 2⁸, 2¹⁰, 2¹², 2¹⁴, 2¹⁶, 2¹⁸, 2²⁰
did you notice that until 2¹⁰ we still have repeated numbers, after that we start to have a new number
so rewrite the numbers above using this observation it will be
2², 2³, 2⁴, 2⁵, 2⁶, 2⁷, 2⁸, 2⁹, 2¹⁰
3², 3³, 3⁴, 3⁵, 3⁶, 3⁷, 3⁸, 3⁹, 3¹⁰
2⁴, 2⁵, 2⁸, 2¹⁰, 2¹², 2¹⁴, 2¹⁶, 2¹⁸, 2²⁰
5², 5³, 5⁴, 5⁵, 5⁶, 5⁷, 5⁸, 5⁹, 5¹⁰
6², 6³, 6⁴, 6⁵, 6⁶, 6⁷, 6⁸, 6⁹, 6¹⁰
7², 7³, 7⁴, 7⁵, 7⁶, 7⁷, 7⁸, 7⁹, 7¹⁰
2⁶, 2⁹, 2¹², 2¹⁵, 2¹⁸, 2²¹, 2²⁴, 2²⁷, 2³⁰
3⁴, 3⁶, 3⁸, 3¹⁰, 3¹², 3¹⁴, 3¹⁶, 3¹⁸, 3²⁰
10², 10³, 10⁴, 10⁵, 10⁶, 10⁷, 10⁸, 10⁹, 10¹⁰
so we need to keep track of the number we get the powers for it, for examlpe we start with 2² the number is 2, the power is 2 the gap to increase power is 1. the code for it is:

vector<int>  calcCache(int rangeStart, int rangeEnd)
{
    int maxBase = rangeEnd*rangeEnd;
    int maxStartPow = 1;
    while (maxBase > 0)
    {
        maxBase /= 2;
        maxStartPow++;
    }
    maxStartPow /= 2;
    vector<bool> seen(maxStartPow*rangeEnd, false);
    int i = rangeStart;
    vector<int> cahce;


    int maxprev = 0;

    int gap = 1;
    int startpow = 2 * gap;
    int j = pow(i, startpow);

    int diff = rangeEnd - rangeStart;
    int maxCurrent = diff*gap + startpow;

    while (j <= rangeEnd*rangeEnd)
    {

        int currPow = startpow;
        int k = 0;
        int currRes = 0;
        while (k <= diff)
        {

            if (!seen[currPow])
            {
                currRes++;
            }
            seen[currPow] = true;
            currPow += gap;
            k++;
        }
        cahce.push_back(currRes);

        maxprev = currPow - gap;


        gap++;
        startpow = 2 * gap;
        j = pow(i, startpow);
    }

    return cahce;
}
int distinctpowers(int rangeStart, int rangeEnd)
{
    vector<bool> arr(rangeEnd*rangeEnd + 1, false);
    int res = 0;

    vector<int> cache = calcCache(rangeStart, rangeEnd);
    for (int i = rangeStart; i <= rangeEnd; i++)
    {

        if (!arr[i*i])
        {
            int maxprev = 0;

            int gap = 1;
            int startpow = 2 * gap;
            int j = pow(i, startpow);

            int diff = rangeEnd - rangeStart;
            int maxCurrent = diff*gap + startpow;

            while (j <= rangeEnd*rangeEnd)
            {

                int currPow = startpow;
                res += cache[gap - 1];

                maxprev = currPow - gap;
                arr[j] = true;

                gap++;
                startpow = 2 * gap;
                j = pow(i, startpow);


            }
        }
    }
    return res;
}

you can add a lot of enhancement to this code like using bit vector instead of bool array.

EDIT:

here is some explanation to the above code, first consider each distinct base at a time from 2 to 10.
2², 2³, 2⁴, 2⁵, 2⁶, 2⁷, 2⁸, 2⁹, 2¹⁰
2⁴, 2⁵, 2⁸, 2¹⁰, 2¹², 2¹⁴, 2¹⁶, 2¹⁸, 2²⁰
2⁶, 2⁹, 2¹², 2¹⁵, 2¹⁸, 2²¹, 2²⁴, 2²⁷, 2³⁰

3², 3³, 3⁴, 3⁵, 3⁶, 3⁷, 3⁸, 3⁹, 3¹⁰
3⁴, 3⁶, 3⁸, 3¹⁰, 3¹², 3¹⁴, 3¹⁶, 3¹⁸, 3²⁰

5², 5³, 5⁴, 5⁵, 5⁶, 5⁷, 5⁸, 5⁹, 5¹⁰

6², 6³, 6⁴, 6⁵, 6⁶, 6⁷, 6⁸, 6⁹, 6¹⁰

7², 7³, 7⁴, 7⁵, 7⁶, 7⁷, 7⁸, 7⁹, 7¹⁰

10², 10³, 10⁴, 10⁵, 10⁶, 10⁷, 10⁸, 10⁹, 10¹⁰

did you notice that the powers sequence is repeating it self for each new base, with maximum numbers in the sequence for base 2.
so we need to save our result for base 2 and reuse it with another base this is the idea of cache.
one more thing in the cache is that you need to figure out how many lines with base 2 you have. so start with the max base which is 10*10 each time divide by 2 until it becomes zero but this will give you the maximum power of base 2 as start of the last line which is 6 as our last 2 ⁶ and you start powers from 2 till 6 each line increase by 2 so we need to divide our result by 2

int maxBase = rangeEnd*rangeEnd;
int maxStartPow = 1;
while (maxBase > 0)
{
    maxBase /= 2;
    maxStartPow++;
}
maxStartPow /= 2;

after that we need to keep track with powers we have seen and the maximum power you can encounter is the maxStartPow*rangeEnd.

vector<bool> seen(maxStartPow*rangeEnd, false);

then we start to go line by line in our base which in this case 2, each line remember the powers we have seen, and when we see new power we increase our result for this line.
the most important part of this code is that, after computing each line we need to store it as we will reuse it in our main problem.

int maxprev = 0;

int gap = 1;
int startpow = 2 * gap;
int j = pow(i, startpow);

int diff = rangeEnd - rangeStart;
int maxCurrent = diff*gap + startpow;

while (j <= rangeEnd*rangeEnd)
{

    int currPow = startpow;
    int k = 0;
    int currRes = 0;
    while (k <= diff)
    {

        if (!seen[currPow])
        {
            currRes++;
        }
        seen[currPow] = true;
        currPow += gap;
        k++;
    }
    cahce.push_back(currRes);

    maxprev = currPow - gap;


    gap++;
    startpow = 2 * gap;
    j = pow(i, startpow);
}

after that we back to our distinictPowers function and go base by base, each base go line by line and reuse our calculation from the cache function