1

[Hardy about Ramanujan]：我记得有一次他在普特尼生病时去看他。我曾坐过 1729 号出租车，并说这个号码在我看来是一个沉闷的数字，我希望这不是一个不祥之兆。“不，”他回答，“这是一个非常有趣的数字；它是可以用两种不同方式表示为两个立方体之和的最小数字。”

两种不同的方式是 1³ + 12³ 和 9³ + 10³

我正在编写一系列函数（用 C 语言）来计算与 Ramanujan 数字相关的不同事物。我现在正在尝试编写一个返回第i 个Ramanujan 数字的函数。由于我已经创建了一个检查数字是否为拉马努金数字的函数，因此简单的方法是检查从 0 到无穷大的每个数字。如果给定数字是 Ramanujan 数字，则将计数器加一。一旦计数器等于我要查找的索引，我就会返回该数字。在代码中：

unsigned long ramanujan_index (unsigned long x, int counter, int index) 
{
    if (counter == index)
        return x - 1;
    if (is_ramanujan(x))
        return ramanujan_index(x + 1, counter + 1, index);
    else
        return ramanujan_index(x + 1, counter, index);
}

它确实有效，但我有点担心它的效率可能没有那么高。检查每个数字似乎不是最好的解决方案。如果我们考虑第一个数字是 1729，第二个是 4104，则更是如此。似乎要找到第 5 个 Ramanujan 数字需要相当多的步骤（实际上是 32832 步骤，因为它必须检查从 0 开始的每个数字到 32832，这是第 5 个数字）。有更好的方法吗？

4

1 回答 1

1

这是一个使用嵌套循环枚举不同阶数的拉马努金数的简单程序。它使用一个数组来存储路数并枚举立方体以生成总和。计算在切片中执行，以利用 CPU 缓存并允许超出内存大小的范围。

该程序在不到 0.01 秒的时间内枚举 2 到 100 万个拉马努金数，并在几个小时内找到最小的 4 级拉马努金数：6963472309248

#include <stdio.h>
#include <stdlib.h>

#define MAX_SLICE   0x400000   // use 4MB at a time

int main(int argc, char **argv) {
    int order = 2;
    size_t min = 0, max = 1000000, a, a3, b, n, i, n1, n2;

    while (*++argv) {
        char *p;
        n = strtoull(*argv, &p, 0);
        if (*p == '-') {
            min = n;
            max = strtoull(p + 1, NULL, 0);
        } else {
            if (n < 10)
                order = n;
            else
                max = n;
        }
    }
    for (n1 = min; n1 <= max; n1 = n2) {
        size_t slice = (max + 1 - n1 <= MAX_SLICE) ? max + 1 - n1 : MAX_SLICE;
        unsigned char *count = calloc(slice, 1);
        n2 = n1 + slice;
        for (a = 1; (a3 = a * a * a) < n2; a++) {
            if (a3 + a3 >= n1) {
                for (b = 1; b <= a && (n = a3 + b * b * b) < n2; b++) {
                    if (n >= n1)
                        count[n - n1]++;
                }
            }
        }
        for (i = n1; i < n2; i++) {
            if (count[i - n1] >= order)
                printf("%llu\n", (long long unsigned int)i);
        }
        free(count);
    }
    return 0;
}

运行：

chqrlie$ time ./rama
1729
4104
13832
20683
32832
39312
40033
46683
64232
65728
110656
110808
134379
149389
165464
171288
195841
216027
216125
262656
314496
320264
327763
373464
402597
439101
443889
513000
513856
515375
525824
558441
593047
684019
704977
805688
842751
885248
886464
920673
955016
984067
994688

real    0m0.008s
user    0m0.002s
sys     0m0.002s

chqrlie$ time ./rama 10000000000 2 | wc -l
    4724

real    0m7.526s
user    0m7.373s
sys     0m0.061s

chqrlie$ time ./rama 6963000000000-6964000000000 4
6963472309248

real    0m10.383s
user    0m10.243s
sys     0m0.050s
于 2021-10-24T12:56:44.063 回答