123456789101112131415161718192021222324252627282930313233343536 |
- #!/usr/bin/ruby
- # Author: Daniel "Trizen" Șuteu
- # License: GPLv3
- # Website: https://github.com/trizen
- # The following iterative sequence is defined for the set of positive integers:
- # n → n/2 (n is even)
- # n → 3n + 1 (n is odd)
- # Which starting number, under one million, produces the longest chain?
- # https://projecteuler.net/problem=14
- # Runtime: 34.996s (previously: 47.259s)
- func collatz(n) is cached {
- n.is_one ? 1
- : (n.is_even ? 1+collatz(n>>1)
- : 1+collatz((3*n + 1)>>1));
- }
- var num = 0;
- var max = 0;
- for i in (1 ..^ 1e6) {
- var value = collatz(i);
- if (value > max) {
- max = value;
- num = i;
- }
- }
- say num;
|