The Hailstone sequence of numbers can be generated from a starting positive integer,   n   by:

   If   n   is     1     then the sequence ends.
   If   n   is   even then the next   n   of the sequence    = n/2 
   If   n   is   odd   then the next   n   of the sequence    = (3 * n) + 1 


The (unproven) Collatz conjecture is that the hailstone sequence for any starting number always terminates.



This sequence was named by Lothar Collatz in 1937   (or possibly in 1939),   and is also known as (the):

   hailstone sequence,   hailstone numbers
   3x + 2 mapping,   3n + 1 problem
   Collatz sequence
   Hasse's algorithm
   Kakutani's problem
   Syracuse algorithm,   Syracuse problem
   Thwaites conjecture 
   Ulam's problem


The hailstone sequence is also known as   hailstone numbers   (because the values are usually subject to multiple descents and ascents like hailstones in a cloud).



Task

 Create a routine to generate the hailstone sequence for a number.
 Use the routine to show that the hailstone sequence for the number 27 has 112 elements starting with 27, 82, 41, 124 and ending with 8, 4, 2, 1
 Show the number less than 100,000 which has the longest hailstone sequence together with that sequence's length.
   (But don't show the actual sequence!)


See also

   xkcd (humourous).
   The Notorious Collatz conjecture Terence Tao, UCLA (Presentation, pdf).
   The Simplest Math Problem No One Can Solve Veritasium (video, sponsored).


Home is a room.
 
To decide which list of numbers is the hailstone sequence for (N - number):
	let result be a list of numbers;
	add N to result;
	while N is not 1:
		if N is even, let N be N / 2;
		otherwise let N be (3 * N) + 1;
		add N to result;
	decide on result.
 
Hailstone length cache relates various numbers to one number.
 
To decide which number is the hailstone sequence length for (N - number):
	let ON be N;
	let length so far be 0;
	while N is not 1:
		if N relates to a number by the hailstone length cache relation:
			let result be length so far plus the number to which N relates by the hailstone length cache relation;
			now the hailstone length cache relation relates ON to result;
			decide on result;
		if N is even, let N be N / 2;
		otherwise let N be (3 * N) + 1;
		increment length so far;
	let result be length so far plus 1;
	now the hailstone length cache relation relates ON to result;
	decide on result.
 
To say first and last (N - number) entry/entries in (L - list of values of kind K):
	let length be the number of entries in L;
	if length <= N * 2:
		say L;
	else:
		repeat with M running from 1 to N:
			if M > 1, say ", ";
			say entry M in L;
		say " ... ";
		repeat with M running from length - N + 1 to length:
			say entry M in L;
			if M < length, say ", ".
 
When play begins:
	let H27 be the hailstone sequence for 27;
	say "Hailstone sequence for 27 has [number of entries in H27] element[s]: [first and last 4 entries in H27].";
	let best length be 0;
	let best number be 0;
	repeat with N running from 1 to 99999:
		let L be the hailstone sequence length for N;
		if L > best length:
			let best length be L;
			let best number be N;
	say "The number under 100,000 with the longest hailstone sequence is [best number] with [best length] element[s].";
	end the story.