Back from a brief hiatus to take on Problem 14 of Project Euler.
Problem 14:
Longest Collatz Sequence
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?
To take on this issue, I made two functions to handle for the case of when our number is even or odd and simply looped through our range to find the solution. For each number, we go through the sequence and count each jump in the loop until we get to the end of the sequence, a value of 1.
DECLARE i NUMERIC; chain_length PLS_INTEGER := 0; answer PLS_INTEGER := 0; answer_jumps PLS_INTEGER := 0; FUNCTION func_even(n_in NUMERIC) RETURN NUMERIC IS BEGIN RETURN n_in/2; END; FUNCTION func_odd(n_in NUMERIC) RETURN NUMERIC IS BEGIN RETURN (n_in*3)+1; END; BEGIN FOR x IN 2..1000000 LOOP IF EULER_PKG.is_even(x) THEN CONTINUE; END IF; i := x; chain_length := 0; WHILE i != 1 LOOP IF EULER_PKG.is_even(i) THEN i := func_even(i); ELSE i := func_odd(i); END IF; chain_length := chain_length + 1; END LOOP; IF chain_length > answer_jumps THEN answer_jumps := chain_length; answer := x; END IF; END LOOP; dbms_output.put_line(answer); END; --output: 837799
Questions or comments? Feel free to leave them below or reach out to me on Twitter!