project Euler 023

環境

• javascript

問題

完全数とは, その数の真の約数の和がそれ自身と一致する数のことである. たとえば, 28の真の約数の和は, 1 + 2 + 4 + 7 + 14 = 28 であるので, 28は完全数である.

真の約数の和がその数よりも少ないものを不足数といい, 真の約数の和がその数よりも大きいものを過剰数と呼ぶ.

12は, 1 + 2 + 3 + 4 + 6 = 16 となるので, 最小の過剰数である. よって2つの過剰数の和で書ける最少の数は24である. 数学的な解析により, 28123より大きい任意の整数は2つの過剰数の和で書けることが知られている. 2つの過剰数の和で表せない最大の数がこの上限よりも小さいことは分かっているのだが, この上限を減らすことが出来ていない.

2つの過剰数の和で書き表せない正の整数の総和を求めよ.

考え方

1. やりたいことは、2つの過剰数の和で書き表せない正の整数の総和を求めること
2. 過剰数の計算の仕方は、約数の和が自身の数よりも大きい場合
3. 「2つの過剰数の和で書き表せない正の整数」は上記2.のそれぞれを足していった数以外の正の整数になる
4. 上記3.で分かる正の整数の総和を計算する

コード

let kajosuList = [];
let limitNum = 28123;
for (let i = 12; i < limitNum; i++) {
  let yakusuList = [];
  for (let j = 1; j < i; j++) {
    if (i % j === 0) {
      yakusuList.push(j);
    }
  }
  if (yakusuList.length > 0) {
    let yakusuSum = yakusuList.reduce((a, b) => a + b);
    if (i < yakusuSum) {
      kajosuList.push(i);
    }
  }
}
let kajosuWaList = [];
for (let i = 0; i < kajosuList.length; i++) {
  for (let j = i; j < kajosuList.length; j++) {
    kajosuWaList.push(kajosuList[i] + kajosuList[j]);
  }
}
let notKajosuWaList = [];
for (let i = 1; i < limitNum; i++) {
  if (!kajosuWaList.includes(i)) {
    notKajosuWaList.push(i);
  }
}
return notKajosuWaList.reduce((a, b) => a + b);

説明

• 問題より、数え上げ数は、12から28123までの数字内とする
• まず、数え上げ数の約数の和を計算する
• 約数の和が、数え上げ数よりも大きいとき、過剰数として配列に格納しておく
• 28123までの過剰数の配列が得られたので、この配列から、2つの過剰数の和をそれぞれ計算し、さらに配列に格納する
• この2つの過剰数の和以外の数が、「2つの過剰数の和で書き表せない正の整数」なので、1から28123までの数に含まれない数を配列に格納する
• 最後に得られた配列の和を計算する