欧拉计划 #29 替代解决方案

Question

这是一个关于 Project Euler 问题的问题。您可以在这里找到问题的描述：https://projecteuler.net/problem=29

好的，首先，让我澄清一下，我已经解决了这个问题，我只是在寻找一个更基于数学的替代解决方案。
其次，为了不破坏任何尚未解决的问题，如果您尚未解决，请不要继续。 :)

所以，我使用 Python 解决了这个问题，因为它支持大数字和列表理解，所以我能够想出一个单行代码：

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

现在，我正在尝试使用更多的数学知识在 C 中解决它（C 本身不支持大数或列表理解）。我遇到了这个线程：PROJECT EULER #29 接受的答案给了我一些想法，我想出了这个代码：

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;
}

使用此代码，我正在执行您在答案底部看到的操作上面，他展示了一些关于如何找到重复项的图表 x = 3，根据他之前的解释。我正在尝试做同样的事情。现在，如果你运行我的代码，根据上述答案的图表，它正确输出 13，这是重复项的数量。

所以，我尝试扩展它来解决实际的项目欧拉问题，因为如果我能够找到重复项的数量，那么我只需从数字 99 * 99（这是可能的幂组合）中减去它因为 2 <= a <= 100 和 2 <= b <= 100) 这就是答案。结果是：

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;
}

如果你注意的话，变化是我对所有 xs 从 2 到 100 进行循环，而 b 不是从 2 到 10，而是从 2 到 100。
但是，程序打印出 814，这是不正确的。应该是618。非常感谢任何帮助！我可能会重复计算一些重复项，但是在哪里？代码有什么问题？另外，如果您有任何有助于构建新算法的数学解释，也非常感谢！

编辑：
我忘了提到的是，如果不是放置：
for(x = 2; x <= 100; x++) 我愿意：
for(x = 2; x <= 6; x++)
即停止到 6，它会打印正确答案。这更奇怪。

EDIT2：
我还要注意，对于 8 和 9（而不是 100），它给出了正确的结果。分别是 44 和 54。

Answer 1

寻找重叠数字的观察就像流程一样
首先让范围 从 2 到 10 这样数字就会像
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¹⁰
关键点是 4² = (2²)² = 2⁴ 所以
4², 4³, 4⁴, 4⁵, 4⁶, 4⁷, 4⁸, 4⁹, 4¹⁰ 将是 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¹⁰
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¹⁰
所以我们需要跟踪我们得到它的权力的数字，例如我们从 2² 开始数字是 2，权力是 2 增加权力的差距是 1。它的代码是：

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;
}

您可以为此代码添加很多增强功能，例如使用位向量而不是 bool 数组。

编辑：

这是对上述代码的一些解释，首先一次考虑从 2 到 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²⁰

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¹⁰

您是否注意到每个新碱基的幂序列都在重复，碱基 2 的序列中的最大数字。
所以我们需要保存 base 2 的结果并在另一个 base 中重用它，这就是缓存的想法。
缓存中的另一件事是您需要计算出有多少行以 2 为基数。所以从每次 10*10 的最大基数开始，每次除以 2 直到它变为零，但这会给你基数 2 的最大功率作为最后一行的开始，即 6 作为我们的最后一个 2 ⁶ 从 2 到 6 开始，每行增加 2，所以我们需要将结果除以 2

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

之后我们需要跟踪我们看到的功率，您可以遇到的最大功率是 maxStartPow*rangeEnd。

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

然后我们开始在我们的基础中逐行进行，在本例中为 2，每一行记住我们看到的权力，当我们看到新权力时，我们增加我们的权力该行的结果。
这段代码最重要的部分是，在计算每一行之后我们需要存储它，因为我们将在我们的主要问题中重用它。

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);
}

之后我们回到我们的 distinictPowers 函数并逐个碱基，每个碱基逐行重复使用缓存函数中的计算

欧拉计划 #29 替代解决方案

Project Euler #29 alternative solution

c

python

algorithm

math

combinatorics

编辑：