-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathEuler_Problem-026.b93
92 lines (61 loc) · 3.8 KB
/
Euler_Problem-026.b93
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
v
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
>"d"00p"}"8*60p080p090p #v v# p+1/g00g04%g00g04g05<
>60g>:30p>:10p>0\00g%10g00g/v>140p050p>4 0g55+*30g%40p50g1+50p40g00g%40g00g/1+g!|
>80g.@ |p01::-1g01p+1< vp08g03p09_v#`g09:-g+1/g00g04%g00g04g05 <
^_^#p06:-1g06 ># $# ^# < $<
[0,0] Width
[1,0] clear index
[2,0] (getRepCo) result
[3,0] (getRepCo) divisor
[4,0] (getRepCo) current
[5,0] (getRepCo) position
[6,0] current number
[8,0] divisor :max
[9,0] divisor-count :max
// Clear 1-"m"
> "m" :10p> 0 \00g% 10g00 v
|p01::-1g01p+1/g<
@
// Expanded:
> "d"00p "}"8*60p 080p 090p v
v <
v p +1/g00g04 %g00g04 g05<
> 60g >:30p>:10p >0\00g%10g00g/v> 140p 050p > 40g55+*30g%40p 50g1+50p 40g00g%40g00g/1+g!| > 90p 30g80p v
|p01::-1g01p+1< > 50g 40g00g% 40g00g/1+ g - : 90g ` |
>$ ^ >$ v
| p06:-1g06 <
>80g. @
---------------------------------------
To calculate the repeating-digit-count we use an algorithm based on the idea of a long division. Here on the example of `1/7`
| Position | Value | Remainder | Note |
|----------|-------------- |---------------|----------------------------------------|
| 0 | 0, | 10/7 | `10/7 = 1` **&** `(10%7)*10 = 30` |
| 1 | 0,1 | 30/7 | `30/7 = 1` **&** `(30%7)*10 = 20` |
| 2 | 0,13 | 20/7 | `20/7 = 1` **&** `(20%7)*10 = 60` |
| 3 | 0,132 | 60/7 | `60/7 = 1` **&** `(60%7)*10 = 40` |
| 4 | 0,1328 | 40/7 | `40/7 = 1` **&** `(40%7)*10 = 50` |
| 5 | 0,13285 | 50/7 | `50/7 = 1` **&** `(50%7)*10 = 10` |
| 6 | 0,132857 | 10/7 | **duplicate remainder -> loop closed** |
**=>** RepeatingDigitCount := `6 - 0` = `6`
We use a 1000-field "array" to remember every remainder we already had - as soon as we reach one that is already in use the digits start repeating itself.
For better understanding here the **FindRepeatingDigitCount(int divisor)** algorithm in pseudo-code:
```
int current = 1;
int position = 0;
while(true) {
current = (current*10) % divisor;
position++;
if (grid[current] != 0) return position - grid[current];
else grid[current] = position;
}
```