2nd SAP Code Challenge

Collatz Sequence length calculation

by hapejot

HTML

<html>
<body>
<table>
<tr><td id=num></td><td>sequences tested</td></tr>
<tr><td id=max></td><td>elements has the longest sequence</td></tr>
<tr><td id=pos></td><td>starting number for this sequence</td></tr>

</table>
</table>
</body>
</html>

CSS

#num {text-align:right}
#max {text-align:right}
#pos {text-align:right}
td {font-family: sans-serif}

JavaScript

function CollatzTest(limit) {
	var me = this
	me.limit = limit
	lengths = {}		// length cache to store known lengths
	max = 0
	max_pos = 0

	// defines the step n -> n+1 for the collatz sequence
	function CollatzStep(n) {
		if (n % 2 == 0) { return n / 2 }
		else { return 3 * n + 1 }
	}

	// this.length represents a caching mechanism in order to prevent 
  // the recalculation of an already known sequence lenth
	// this improves the performance by an order of a magnitude.
  // The reqursiveness of the approach gives the opportunity to use a 
  // cache to cut-off some recursions.
	function SeqLen(n) {
		if (lengths[n] === undefined) {
			var n1 = CollatzStep(n)
			var result = 0
			if (n1 > 1) result = 1 + SeqLen(n1)
			else result = 1
			lengths[n] = result

			if (result > max) {
				max = result
				max_pos = n
			}
			return result
		}
		else {
			return lengths[n]
		}
	}

	this.run = function (){
		for (var i = 1; i <= limit; i++)	SeqLen(i)
		return(	{ max:  max, pos: max_pos} )
	}
}



var tst = new CollatzTest(1000000)
var result = tst.run()
document.getElementById("pos").innerHTML = result.pos
document.getElementById("max").innerHTML = result.max
document.getElementById("num").innerHTML = tst.limit


//console.log(tst.run())