-
Notifications
You must be signed in to change notification settings - Fork 12
/
farey_sequence.go
79 lines (73 loc) · 1.45 KB
/
farey_sequence.go
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
///main package has examples shown
// in Go Data Structures and algorithms book
package main
// importing fmt package
import (
"fmt"
)
// fraction class
type fraction struct {
numerator int
denominator int
}
// string method
func (frac fraction) String() string {
return fmt.Sprintf("%d/%d", frac.numerator, frac.denominator)
}
// g method
func g(l fraction, r fraction, num int) {
var frac fraction
frac = fraction{l.numerator + r.numerator, l.denominator + r.denominator}
if frac.denominator <= num {
g(l, frac, num)
fmt.Print(frac, " ")
g(frac, r, num)
}
}
// main method
func main() {
var num int
var l fraction
var r fraction
for num = 1; num <= 11; num++ {
l = fraction{0, 1}
r = fraction{1, 1}
fmt.Printf("F(%d): %s ", num, l)
g(l, r, num)
fmt.Println(r)
}
var primes [1001]bool
var p int
for _, p = range []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31} {
for num = p * 2; num <= 1000; num += p {
primes[num] = true
}
}
var totients [1001]int
var i int
for i = range totients {
totients[i] = 1
}
for num = 2; num <= 1000; num++ {
if !primes[num] {
totients[num] = num - 1
var a int
var f int
var r int
for a = num * 2; a <= 1000; a += num {
f = num - 1
for r = a / num; r%num == 0; r /= num {
f *= num
}
totients[a] *= f
}
}
}
var sum int
for num, sum = 1, 1; num <= 1000; num++ {
sum += totients[num]
if num%100 == 0 {
fmt.Printf("|F(%d)|: %d\n", num, sum)
}
}
}