blob: 1edaf98ba30e6df887ab9d583e0c6d8f3a49d8f9 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
###
# Longest Collatz sequence
# Problem 14
#
# 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?
# NOTE: Once the chain starts the terms are allowed to go above one million.
###
function collatz_length(n)
n == 1 && return 1
n % 2 == 0 && return 1 + collatz_length(n ÷ 2)
return 1 + collatz_length(3n + 1)
end
result = argmax([collatz_length(x) for x in 1:(1_000_000 - 1)])
println(result)
|
