2

私はプロジェクトオイラーの問題23に苦しんでいます：豊富でない合計。

ここに画像の説明を入力してください

豊富な数を計算するスクリプトがあります。

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を掛けて、2つの過剰数の合計である数を得ることができます。

しかし、そのように書くことができないすべての数字を見つける必要があるので、私は次のifようにステートメントを逆にします：

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

これで、すべてを格納する必要があります。これは、豊富な数の合計として作成することはできませんが、ここで何かが終了するわけではありません。それらを合計すると、正しい答えにさえ近くない数が得られます。

私は答えを見たくありませんが、私が間違っていること（または私が見逃していることや誤解していること）に関するいくつかのガイドライン/ヒントが必要です。

編集：私も逆の順序で試しました。つまり、上から始めて2で割り、それらが豊富かどうかを確認しました。それでも間違って出てきます。

4

3 に答える 3

3

私はすでにインターネットで入手可能なものでそれらの番号をチェックしました、そしてそれらは正しいです。それらに2を掛けて、2つの過剰数の合計である数を得ることができます。

いいえ、そうではありません。過剰数は1つだけです<= 16が、<= 32過剰数の合計として記述できる数は、24（= 12 + 12）、30（= 12 + 18）、32（= 12 + 20）です。

k数字がある場合はk*(k+1)/2、そのうちの2つ（必ずしも異なるとは限りません）を選択する方法があります。多くの場合、これらのペアの多くは同じ合計になるため、一般にk*(k+1)/2、指定された2つの数値の合計として記述できる数値よりもはるかに少ない数ですkが、通常は、より多くなり2*kます。

また、<= 281232つの過剰数のうちの1つが。より大きい場合にのみ、過剰数の合計として記述できる数が多数あり28123/2ます。

これで、豊富な数の合計として作成できないすべてを保存する必要があります。

いいえ、それは非豊富な数を格納します、それらは豊富な数の合計である場合とそうでない場合があります、例えば32は不足数です（32を除くすべての除数の合計は31です）が、2つの豊富な数の合計として書くことができます番号（上記を参照）。

与えられた制限の半分だけでなく、豊富な数を見つける必要があります。また、2つの豊富な数の合計としてどの数を書き込むことができるかを確認する必要があります。これを行うには、2つの豊富な数のすべてのペア（ ）を取得して合計をマークするか、豊富な数のペアが見つかるか、合計が。にならないと判断するまで<= $limitチェックします。$number - $abundant$number

それを大幅にスピードアップできるいくつかの理論的特性があります。

于 2013-01-14T16:04:06.837 に答える
3

ロジックのエラーは次の行にあります。

「それらに2を掛けて、2つの豊富な数の合計である数を得ることができます」

最初に、分析的に証明された制限を下回るすべての過剰数[n1、n2、n3....]を決定します。次に、すべての整数[2 * n1、2 * n2、....]は2つの過剰数の合計ですが、 n1 + n2、およびn2+n3も2つの過剰数の合計であると述べるのは真実です。そこにあなたの誤りがあります。[n1、n2、n3 ....]からの任意の2つの数値の合計である可能性のあるすべての整数を計算してから、逆数をとって、ではない整数を見つける必要があります。

于 2013-01-14T16:01:48.033 に答える
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 に答える