Project Euler in PL/SQL: Problem 14

  • by

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!

Leave a Reply

Your email address will not be published. Required fields are marked *