Skip to Content
author's profile photo Marcello Urbani

CCC2 Longest Collatz (Euler 14)

My submissions for the 2nd SAP Community Coding Challenge.

My favourite is the functional one (see here):

const nextCollatz = n => (n % 2 ? 3 * n + 1 : n / 2)
const naturals = n => [...Array(n + 1).keys()].slice(1)
const collatzLength = idx =>
  idx === 1 ? 1 : 1 + collatzLength(nextCollatz(idx))

const longestCollatz = n =>
  naturals(n)
    .map(collatzLength)
    .reduce( (state, max, idx) => (max <= state.max ? state : { max, maxIdx: idx + 1 }), { max: 0, maxIdx: 0 } )

const result = longestCollatz(1000000)
console.log(`Longest sequence at ${result.maxIdx}, length ${result.max}`)

Outputs:

Longest sequence at 837799, length 525

This one is much faster, but relies on a mutable array. Did try a pure functional version, worked but took well over an hour to run. This runs in about 250ms on my laptop:

const nextCollatz = n => (n % 2 ? 3 * n + 1 : n / 2)
const naturals = n => [...Array(n + 1).keys()].slice(1)
const max = s => s.lengths[s.maxIdx]

const collatzLengths = maxNumber =>
  naturals(maxNumber).reduce(
    (state, current) => {
      const calcLength = idx => {
        if (idx < current || idx === 1) return state.lengths[idx]
        return calcLength(nextCollatz(idx)) + 1
      }
      const length = calcLength(current)
      state.lengths[current] = length
      state.maxIdx = length > max(state) ? current : state.maxIdx
      return state
    },
    { lengths: [0, 1], maxIdx: 0 }
  )

const longestCollatz = n => {
  const { maxIdx, lengths } = collatzLengths(n)
  return { max: maxIdx, length: lengths[maxIdx] }
}

const result = longestCollatz(1000000)
console.log(`Longest sequence at ${result.max}, length ${result.length}`)

Outputs:

Longest sequence at 837799, length 525

* Please Login or Register to Comment on or Follow discussions.

1 Comment

  • May 13, 2020 at 11:05 PM

    ...and this is my fastest, shamelessly "inspired" by Alexander Frank's

    const nextCollatz = n => (n & 1 ? 3 * n + 1 : n / 2)
    
    const longestCollatz = limit => {
      const values = new Uint32Array(limit)
      values[1] = 1
      let maxIdx = 0
      let maxLen = 0
      const collatzLength = start => {
        let next = start
        let len = 1
        while (next !== 1) {
          if (next < start) return values[next] + len
          len++
          next = nextCollatz(next)
        }
      }
      for (let index = 1; index < limit; index++) {
        const length = collatzLength(index)
        values[index] = length
        if (length > maxLen) {
          maxIdx = index
          maxLen = length
        }
      }
      return { maxIdx, maxLen }
    }
    
    const result = longestCollatz(1000000)
    console.log(`Longest sequence at ${result.maxIdx}, length ${result.maxLen}`)

    Outputs:

    Longest sequence at 837799, length 554

  • Add a comment
    10|10000 characters needed characters exceeded