blob: ae16eedb7fdedb3b6e6208db15e0d94d5dd03091 (
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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
# Collatz Conjecture
# Contributed by Ryan Thompson
#
# It is thought that the following sequence will always reach 1:
#
# $n = $n / 2 when $n is even
# $n = 3*$n + 1 when $n is odd
#
# For example, if we start at 23, we get the following sequence:
#
# 23 → 70 → 35 → 106 → 53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
#
# Write a function that finds the Collatz sequence for any positive integer.
# Notice how the sequence itself may go far above the original starting number.
#
# Extra Credit
#
# Have your script calculate the sequence length for all starting numbers up to
# 1000000 (1e6), and output the starting number and sequence length for the
# longest 20 sequences.
sub collatz-seq($n) {
if ($n == 1) {
[1];
} elsif ($n % 2 == 0) {
[$n, |(collatz-seq($n / 2))];
} else {
[$n, |(collatz-seq(3 * $n + 1))];
}
}
say collatz-seq(23);
# Extra Credit
# I have no good idea how to do this smart. I don't even know if there is a
# faster way. The Collatz Conjecture is a Conjecture for a reason of course.
# Therefore, I do it the lazy way:
#
# 1. Parallelize the whole search. Depending on the amount of threads this
# speeds up tremendously.
# 2. Use cached to store older results. (I'm surprised this works well with
# multi-threading)
#
# On my Intel i7 (4 cores, 8 threads) it still takes half an hour to compute.
# Results:
#
# 922524 444
# 922525 444
# 922526 444
# 938143 444
# 615017 446
# 410011 448
# 818943 449
# 820022 449
# 820023 449
# 546681 451
# 970599 457
# 767903 467
# 796095 467
# 511935 469
# 910107 475
# 927003 475
# 704623 503
# 939497 506
# 626331 508
# 837799 524
use experimental :cached; # My favourite Raku feature!
sub collatz-length($n) is cached {
if ($n == 1) {
0;
} elsif ($n % 2 == 0) {
collatz-length($n / 2) + 1;
} else {
collatz-length(3 * $n + 1) + 1;
}
}
my $collatz-list = Channel.new;
await (1..1e6).map: -> $n {
start {
$collatz-list.send((collatz-length($n), $n));
}
}
$collatz-list.close();
for $collatz-list.list.sort.tail(20) -> ($l, $n) {
say $n, ' ', $l;
}
|
