2

我正在努力解决 Project Euler问题 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 并检查这些是否丰富。结果还是错了。

4

3 回答 3

3

您的逻辑中的错误在于以下行：

“我可以将它们乘以 2 并得到两个丰富数字之和的数字”

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

于 2013-01-14T16:01:48.033 回答
3

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

不，这是不对的。丰富数只有一个<= 16，但<= 32可以写成丰富数之和的数是24（= 12 + 12）、30（= 12 + 18）、32（= 12 + 20）。

如果你有k数字，有k*(k+1)/2办法选择其中两个（不一定不同）。k*(k+1)/2通常，这些对中的许多将具有相同的和，因此通常可以写成两个给定数字之和的数字要少得多k，但通常多于2*k.

此外，有许多数<= 28123可以写为丰富数之和，只有两个丰富数之一大于28123/2。

这现在应该存储所有无法创建为大量数字的总和的内容，

不，这将存储非丰富数字，那些可能是也可能不是丰富数字的总和，例如 32 是一个不足的数字（除 32 之外的所有除数的总和是 31），但可以写成两个丰富数字的总和数字（见上文）。

您需要找到丰富的数字，但不仅要找到给定限制的一半，而且您需要检查哪些数字可以写为两个丰富的数字之和。您可以通过取所有两个丰富数对 ( <= $limit) 并标记总和来做到这一点，或者通过检查$number - $abundant直到找到一对丰富数或确定没有一个总和为$number。

有一些数论性质可以大大加快速度。

于 2013-01-14T16:04:06.837 回答
1

下面是 php 代码需要 320 秒

 <?php

set_time_limit(0);
ini_set('memory_limit', '2G');
$time_start = microtime(true);

$abundantNumbers = array();
$sumOfTwoAbundantNumbers = array();
$totalNumbers = array();
$limit = 28123;

for ($i = 12; $i <= $limit; $i++) {
    if ($i >= 24) {
        $totalNumbers[] = $i;
    }
    if (isAbundant($i)) {
        $abundantNumbers[] = $i;
    }
}


$countOfAbundantNumbers = count($abundantNumbers);
for ($j = 0; $j < $countOfAbundantNumbers; $j++) {
    if (($j * 2) > $limit)
        break;                    //if sum of two abundant exceeds limit ignore that
    for ($k = $j; $k < $countOfAbundantNumbers; $k++) {  //set $k = $j to avoid duble addtion like 1+2, 2+1
        $l = $abundantNumbers[$j] + $abundantNumbers[$k];
        $sumOfTwoAbundantNumbers[] = $l;
    }
}
$numbers = array_diff($totalNumbers, $sumOfTwoAbundantNumbers);

echo '<pre>';print_r(array_sum($numbers));

$time_end = microtime(true);
$execution_time = ($time_end - $time_start);

//execution time of the script
echo '<br /><b>Total Execution Time:</b> ' . $execution_time . 'seconds';
exit;

function isAbundant($n) {
    if ($n % 12 == 0 || $n % 945 == 0) { //first even and odd abundant number. a multiple of abundant number is also abundant
        return true;
    }
    $k = round(sqrt($n));
    $sum = 1;
    if ($n >= 1 && $n <= 28123) {
        for ($i = 2; $i <= $k; $i++) {
            if ($n % $i == 0)
                $sum+= $i + ( $n / $i);
            if ($n / $i == $i) {
                $sum = $sum - $i;
            }
        }
    }
    return $sum > $n;
}
于 2014-01-08T12:15:16.553 回答