RSS FEED

Project Euler: Problem 14

Yet another day and yet another problem to discuss. Today it is problem No. 14:

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.

This Post needs Your Comment!

Viktoras Makauskas

that is so much code for simple "find function maximum". This one completes almost instantly on python (don't have Max available at the moment, but they're pretty similar in performance). I know it could be further simplified with python specific code, but I did not want to make it too unreadable:)

on pastebin.com

Vojta

Thanks for the comment, as for the perfomance of MAXScript and Python, I wish they really were comparable. However, timing the two different pieces of code over five successive runs (after correcting the iterator limit to 1000000) gives me 13 sec on average for mine and 2m 34s for yours. Both test were run on a new instance of 3ds max with no background processes that would skew the figures.

Viktoras Makauskas

wow - I totally take my words back, just tested it myself on Max, the performance was so terrible I could not believe it.

I first wrote this on Java, this ran in a fraction of a second. A couple of seconds for python... and it took like a few minutes for maxscript. I guess this proves how long it's been I tried to write something on maxcript :)

Return to top