php - 欧拉计划 #23 : Non-abundant sums

Question

我正在为 Euler 项目而苦苦挣扎 problem 23: Non-abundant sums .

我有一个脚本，可以计算大量数字:

function getSummOfDivisors( $number )
{
    $divisors = array ();
    for( $i = 1; $i < $number; $i ++ ) {
        if ( $number % $i == 0 ) {
            $divisors[] = $i;
        }
    }
    return array_sum( $divisors );
}

$limit = 28123;
//$limit  = 1000;
$matches = array();
$k = 0;

while( $k <= ( $limit/2 ) ) {
    if ( $k < getSummOfDivisors( $k ) ) {
        $matches[] = $k;
    }
    $k++;
}

echo '<pre>'; print_r( $matches );

我已经用互联网上可用的数据检查了这些数字，它们是正确的。我可以将它们乘以 2，得到两个丰富数字之和的数字。

但是因为我需要找到所有不能这样写的数字，所以我只是像这样反转 if 语句:

if ( $k >= getSummOfDivisors( $k ) )

这现在应该存储所有不能创建为大量数字总和的内容，但这里并没有停止。当我对它们求和时，我得到一个与正确答案相去甚远的数字。

我不想看到答案，但我需要一些指导方针/提示来说明我做错了什么(或者我遗漏或误解了什么)。

编辑:我还尝试了相反的顺序，也就是说，从顶部开始，除以 2 并检查它们是否充足。还是出错了。

Answer 1

你的逻辑错误在于:

“我可以将它们乘以 2，得到两个大量数字之和的数字”

您首先确定所有低于分析证明极限的丰度数 [n1、n2、n3....]。那么所有整数 [2*n1, 2*n2,...] 都是两个丰富数字的总和是正确的但是 n1+n2 和 n2+n3 也是总和两个丰富的数字。这就是你的错误。您必须计算所有可能的整数，这些整数是 [n1, n2, n3....] 中任意两个数字之和，然后求逆以找到不是的整数。