CCC2 - two (completely different) approaches for solving the Longest Collatz sequence Problem

Today, I stumbled across the blog titled "SAP Community Coding Challenge Nr.2" by DJ Adams and found the challenge interesting and (at least the problem description) easy enough to spend a bit of time on a solution.

In the end, I came up with two (completely different) approaches to solve the problem (keep in mind: the problem was to compute the required number for n=1.000.000, not to prove or disprove Collatzes conjecture. Links to both approaches down below.

First things first: the answer is 837799

First approach

My first approach started with the observation that the problem cried for recursion. Although I think that this probably will lead to some stack overflow problems for larger numbers, I thought this should be fine for a million. So first, I startet by pinning down a recursive function that returned the correct sequence for n=13. The function was something along these lines (sorry, didn't keep the version) when I continued

collatz = function(n) {
    return 1 + collatz( n%2 ? n/2 : 3*n+1 )
}

the trivial approach would be to go and use map to compute this number for all integers up to a million, then take the max of the results, and voilà, the result

max( array_0_to_1000000.map( n => collatz(n) ) )

but I felt that this would be a misuse of computer resources, as the same numbers would be computed again and again. But keeping an array of intermediate results outside of the map sounded like a misuse of the map function, although it would probably work.

So, reduce it was, although it didn't feel like the usual case for the reduce function either.

Basically, my modified collatz function got an array of previously computed results and the integer to compute the collatz number for. before recursing, it checks in the array whether to descend in recursion or just to read the result from the array.

This is the final version, as is also available here: https://repl.it/@bistrOmath/CCC2-Compute-Manually

runManually = function(l){
    var N=10**l, collatzSequenceLengths, seqLenFun, done=Number.isInteger;

    seqLenFun = function(L,n) {
        L[n] = done(L[n]) ? L[n] : ((p)=>1+seqLenFun(L,p)[p])(n%2?3*n+1:n/2)
        return L
    }

    collatzSequenceLengths = Array.from(Array(N+1).keys())  // array [0,1,2,...,N]
        .reduce(seqLenFun, [0,1])                           // reduce

    // Math.max.apply will cause a stack overflow applied to an array of 
    // size 10^6, so use reduce function again
    return collatzSequenceLengths.indexOf(collatzSequenceLengths.slice(0,N+1).reduce( (a,b) => Math.max(a,b)))
}
runManually(6)

A couple more notes on this one:

1. As input, I chose the power of 10, so runManually(6) returns the result for 10^6 = 1.000.000
2. Usually, I would get the maximum of an array by using Math.max.apply(null, array) but that caused stack overflow. so I resorted to another reduce
3. slice is needed, as we are only interested int he first one million (or 10^n) results, but the intermediate array contains way more values above the million

Second approach

Being mathematician myself I thought that this must have been analysed before (being an unsolved problem), and in fact, n => the number under 10^n that produces the longest Collatz chain defines the sequence A284668 in The On-line Encyclopedia of Integer Sequences: https://oeis.org/A284668 and the table of the first 10 values of that sequence is available online. So my second approach accesses oeis sequence page and grabs the necessary result. and ended up with a ONE-LINER (if you don't count input parameter check)

Full code: https://repl.it/@bistrOmath/CCC2-OEIS-Version

/** just a library for ajax requests **/
const got = require("got")


/**
* given a small integer l (between 1 and 10, inclusively), returns an integer with largest
* Collatz sequence among integers between 1 and 10^l
* 
* Example: for l=2 this is 97: 97 has the largest Collatz sequence among integers in the range [1..10^2]
* 
* we basically just retrieve the required information from the OEIS sequence A284668 
*/
runOeis = function(l){
    if (l<1||l>10) throw new Error("Exponents smaller than 1 or larger than 10 not supported")
    return got("https://oeis.org/search?q=%22largest+collatz%22&fmt=text").then(d=>1*/^%S\s[A0-9]+\s(.*)$/m.exec(d.body)[1].split(",")[l-1])
}

// alternatively, "await runOeis(6)" in an async context
// we just print the result to console
runOeis(6).then(console.log)

this one is aynchronous as we get the published values asynchronously. So I printed the result to console log. In an asynchronous environment, one could also "await" the result.

A couple of notes on this one:

1. works only for powers of 10
2. works only for exponents 1 .. 10 (as only these are published on OEIS sequence page )

Further reading:

Gary T. Leavens and Mike Vermeulen published a paper in 1992 in the Journal "Computers and Mathematics with Applications": https://www.sciencedirect.com/science/article/pii/089812219290034F (Link to full article). I have to admit that I didn't read the article, but it seems to describe some algorithmic improvements to various approaches of determining the required numbers.

I hope you all enjoy reading it as much as I had fun writing it :)

Cheers, Sergei