-
Notifications
You must be signed in to change notification settings - Fork 6
/
700 Eulercoin.sf
55 lines (39 loc) · 866 Bytes
/
700 Eulercoin.sf
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
#!/usr/bin/ruby
# Daniel "Trizen" Șuteu
# Date: 09 February 2020
# https://github.com/trizen
# https://projecteuler.net/problem=700
# Runtime: ~100ms.
# Using the denominators of Farey approximations of 1504170715041707 / 4503599627370517.
# See also:
# https://en.wikipedia.org/wiki/Farey_sequence
func farey_approximations(r, callback) {
var a1 = r.int
var b1 = 1
var a2 = a1+1
var b2 = 1
loop {
var a3 = a1+a2
var b3 = b1+b2
if (a3 < r*b3) {
(a1, b1) = (a3, b3)
}
else {
(a2, b2) = (a3, b3)
}
callback(a3, b3)
}
}
var a = 1504170715041707
var b = 4503599627370517
var min = a
var sum = min
farey_approximations(a/b, {|_,d|
var t = (a*d % b)
if (t < min) {
min = t
sum += t
break if (t == 0)
}
})
say sum