Files

2.4 KiB
Raw Permalink Blame History

id, title, challengeType, forumTopicId, dashedName
id title challengeType forumTopicId dashedName
5900f37a1000cf542c50fe8d 問題 14最長考拉茲序列 5 301768 problem-14-longest-collatz-sequence

--description--

對正整數集定義如下迭代序列:

nn / 2n 爲偶數)
n → 3n + 1n 爲奇數)

從 13 開始使用上述規則,我們可以得到如下序列:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

可以看出,該序列(從 13 開始到 1 結束)共包含 10 項。 雖然考拉茲猜想尚未得到證明,但是該猜想認爲以任意數字開始,序列均到 1 結束。

求出在小於 limit 的數中,哪個可以產生最長的考拉茲序列?

注意: 序列中數字的個數允許超過一百萬。

--hints--

longestCollatzSequence(14) 應該返回一個數字。

assert(typeof longestCollatzSequence(14) === 'number');

longestCollatzSequence(14) 應該返回 9。

assert.strictEqual(longestCollatzSequence(14), 9);

longestCollatzSequence(5847) 應該返回 3711。

assert.strictEqual(longestCollatzSequence(5847), 3711);

longestCollatzSequence(46500) 應該返回 35655。

assert.strictEqual(longestCollatzSequence(46500), 35655);

longestCollatzSequence(54512) 應該返回 52527。

assert.strictEqual(longestCollatzSequence(54512), 52527);

longestCollatzSequence(100000) 應該返回 77031。

assert.strictEqual(longestCollatzSequence(100000), 77031);

longestCollatzSequence(1000000) 應該返回 837799。

assert.strictEqual(longestCollatzSequence(1000000), 837799);

--seed--

--seed-contents--

function longestCollatzSequence(limit) {

  return true;
}

longestCollatzSequence(14);

--solutions--

function longestCollatzSequence(limit) {
  let longest = 1;
  let maxLength = 1;
  for (let i = Math.floor(limit / 2); i < limit; i++) {
    let len = colLen(i);
    if (len > maxLength) {
      longest = i;
      maxLength = len;
    }
  }
  return longest;
}

const knownSequence = { '1': 1 };

function colLen(n) {
  if (knownSequence[n]) {
    return knownSequence[n];
  } else {
    const len = n % 2 === 0 ? colLen(n / 2) + 1 : colLen((3 * n + 1) / 2) + 2;
    knownSequence[n] = len;
    return len;
  }
}