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
93
94
95
96
97
98
99
100
101
102
103
104
105
|
/*
* Ordered fractions
* Problem 71
*
* Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1,
* it is called a reduced proper fraction.
* If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we
* get:
* 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5,
* 5/6, 6/7, 7/8
* It can be seen that 2/5 is the fraction immediately to the left of 3/7.
* By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of
* size, find the numerator of the fraction immediately to the left of 3/7.
*/
package main
import (
"fmt"
"sort"
)
const MAX_DENOMINATOR = 1_000_000
// from: https://www.101computing.net/hcf-and-lcm-algorithms/
func hcf(a, b int) int {
var t int
if a < b {
t = a
a = b
b = t
}
for b > 0 {
t = b
b = a % b
a = t
}
return a
}
func hasCommonFactor(a, b int) bool {
return hcf(a, b) != 1
}
type Fraction struct {
N int
D int
}
func (f1 Fraction) isLower(f2 Fraction) bool {
ni_common := f1.N * f2.D
nj_common := f2.N * f1.D
return ni_common < nj_common
}
var targetFraction = Fraction {N: 3, D: 7}
func main() {
fractions := make([]Fraction, 0, MAX_DENOMINATOR)
fractions = append(fractions, targetFraction)
for d := 1; d <= MAX_DENOMINATOR; d++ {
lo := 1
hi := d
n := (hi + lo) / 2
var f Fraction
for lo < hi {
factor := hcf(n, d)
f = Fraction{
N: n / factor,
D: d / factor,
}
if f.isLower(targetFraction) {
lo = n + 1
} else {
hi = n
}
n = (hi + lo) / 2
}
fractions = append(fractions, f)
// in case we're at the fraction just one above the target fraction
f.N--
fractions = append(fractions, f)
}
sort.Slice(fractions, func (i, j int) bool {
return fractions[i].isLower(fractions[j])
})
new_fractions := make([]Fraction, 0, len(fractions))
for i := 0; i < len(fractions); {
new_fractions = append(new_fractions, fractions[i])
curr := fractions[i]
for i < len(fractions) && curr.N == fractions[i].N && curr.D == fractions[i].D {
i++
}
}
for i, f := range new_fractions {
if f.N == targetFraction.N && f.D == targetFraction.D {
fmt.Printf("to the left of %d/%d is %d/%d\n", f.N, f.D, new_fractions[i - 1].N, new_fractions[i - 1].D)
fmt.Printf("answer %d\n", new_fractions[i - 1].N)
}
}
}
|
