Fortran Implementation of Problem 14

View source code here on GitHub!

integer Problem0014/p0014()
 1! Project Euler Problem 14
 2!
 3! Problem:
 4!
 5! The following iterative sequence is defined for the set of positive integers:
 6!
 7! n → n/2 (n is even)
 8! n → 3n + 1 (n is odd)
 9!
10! Using the rule above and starting with 13, we generate the following sequence:
11! 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
12!
13! It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been
14! proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
15!
16! Which starting number, under one million, produces the longest chain?
17!
18! NOTE: Once the chain starts the terms are allowed to go above one million.
19
20module Problem0014
21    use constants
22    implicit none
23    integer, parameter :: collatz_cache_size = 2**20
24contains
25    integer(i18t) function p0014() result(answer)
26        integer, allocatable :: collatz_len_cache(:)
27        integer(i18t) :: test
28        integer :: tmp, length = 2
29        allocate(collatz_len_cache(collatz_cache_size))
30        if (.not. allocated(collatz_len_cache)) then
31            print *, "Allocation of collatz length cache failed. Stopping run."
32            stop ERROR_ALLOCATE_FAILED
33        end if
34        collatz_len_cache = 0
35        collatz_len_cache(1) = 1
36        answer = 2
37        do test = 3, 999999
38            call collatz_len(tmp, test, collatz_len_cache)
39            if (tmp > length) then
40                answer = test
41                length = tmp
42            end if
43        end do
44        deallocate(collatz_len_cache)
45    end function p0014
46
47    recursive subroutine collatz_len(answer, n, collatz_len_cache)
48        integer(i18t), intent(in) :: n
49        integer, intent(out) :: answer
50        integer, intent(inout), dimension(:) :: collatz_len_cache
51        if (n < collatz_cache_size) then
52            if (collatz_len_cache(int(n)) /= 0) then
53                answer = collatz_len_cache(int(n))
54                return
55            end if
56        end if
57        answer = 0
58        if (mod(n, 2_i18t) == 1) then
59            call collatz_len(answer, (3 * n + 1) / 2, collatz_len_cache)
60            answer = answer + 2
61        else
62            call collatz_len(answer, n / 2, collatz_len_cache)
63            answer = answer + 1
64        end if
65        if (n < collatz_cache_size) then
66            collatz_len_cache(int(n)) = answer
67        end if
68    end subroutine
69end module Problem0014

Tags: collatz, recursion, longest-path