Creative Scratchpad

The following iterative sequence is defined for the set of positive integers:

    n → n/2 (n is even)
    n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

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

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

There are not many tweaks in this one. First of all we raise the heap size to 128 MB to avoid automatic garbage collection interrupting the execution almost instantly, then we go through the sequence, saving values less then one million to a predeclared array. If the number is even, we first look if there is a value for nr/2 – if it is so, we just add one and return the lenght, if not, we go the whole way of finding the sequence. Well, almost, as in the getLengthIter function we save and search for previous results as well, adding them to the count so far if we find any. That's basically it.

(
    if heapSize < 134217728L do heapSize = 134217728L
    local arr = #(1L)
    arr[1000000] = undefined

    fn isEven nr = bit.and 1L nr == 0

    fn alg nr = if isEven nr then nr/2 else 3*nr + 1

    fn getLengthIter nr =
    (
        local count = 1L

        while nr != 1 do
        (
            nr = alg nr
            if nr < 1000000 AND arr[nr] != undefined then
            (
                count += arr[nr]
                nr = 1
            )
            else count += 1
        )
        count
    )

    fn getLength nr =
    (
        if arr[nr] != undefined then arr[nr]
        else if isEven nr AND arr[nr/2] != undefined then
            arr[nr] = arr[nr/2]
        else arr[nr] = getLengthIter (alg nr) + 1
    )

    local result, seqLength = 10L

    for i = 2L to 999999L
        where getLength i > seqLength do
    (
        seqLength = getLength i
        result = i
    )

    result
)

Although it satisfies the 1-minute limit, it's quite slow and I'm not very happy about it. I'd really love to hear some suggestions of a different approach to make it faster and less memory hungry.

DISCLAIMER: All scripts and snippets are provided as is under Creative Commons Zero (public domain, no restrictions) license. The author and this blog cannot be held liable for any loss caused as a result of inaccuracy or error within these web pages. Use at your own risk.