-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathEuler_Problem-057.b93
139 lines (95 loc) · 5.92 KB
/
Euler_Problem-057.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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
v
############################################################################### // Numerator [1]
###############################################################################
###############################################################################
###############################################################################
###############################################################################
############################################################################### // Numerator [2]
###############################################################################
###############################################################################
###############################################################################
###############################################################################
############################################################################### // Numerator [3]
###############################################################################
###############################################################################
###############################################################################
###############################################################################
############################################################################### // Denominator [1]
###############################################################################
###############################################################################
###############################################################################
###############################################################################
############################################################################### // Denominator [2]
###############################################################################
###############################################################################
###############################################################################
###############################################################################
############################################################################### // Denominator [3]
###############################################################################
###############################################################################
###############################################################################
###############################################################################
>77*8*2+>:0\:"O"%1+\"O"/2+p:0\:"O"%1+\"O"/8+p:0\:"O"%1+\"O"/72*+p:0\: v // Initialize arrays
|+1:-1p+*84/"O"\+1%"O":\0:p++*298/"O"\+1%"O":\0:p+*45/"O"\+1%"O"<
>$ 1"O"6p1"O"62*p1"O"56*p v
v <
>60*70p61*80p62*90p60*71p61*81p v > 0>$ v // Initialize variables
v*"o"9 p040p121p111p19*26 < ^p11_^#`g11 :-g02*5"O"<
> 010p"O"5*>1-:::20p:"O"%1+\"O"/70g2++g\:"O"%1+\"O"/80g2++g2*10g++:55+%:#^_v // Calculate Numerator
^ _v#:p01/+55p++2g09/"O"\+1%"O":g02<
v p09%+99+6g09p08%+99+6g08p07%+99+6g07$< > 0>$ v
^p12_^#`g12 :-g02*5"O"<
>010p"O"5*>1-:::20p:"O"%1+\"O"/71g54*++g\:"O"%1+\"O"/81g54*++g2*10g++:55+%:#^_v // Calculate Denominator
^ _v#:p01/+55p++*45g19/"O"\+1%"O":g02<
v p19%+99+6g19p18%+99+6g18p17%+99+6g17$<
>11g21g`!#v_40g1+40pv // Test for finish
|: -1< <
>$40g.@
[7,0] numerator arr-index [SEC-LAST]
[8,0] numerator arr-index [LAST]
[9,0] numerator arr-index [CURRENT]
[7,1] denominator arr-index [SEC-LAST]
[8,1] denominator arr-index [LAST]
[9,1] denominator arr-index [CURRENT]
[1,0] carry
[2,0] current calculation index
[1,1] numerator length
[2,1] denominator length
[4,0] N>D count
79*5 = 395 ==> "O"5*
79*5-1 = 394 ==> 77*8*2+
999 ==> "o"9*
// index to array-coord [Numerator] [stack] -> [stack, stack]
:"O"%1+\"O"/70g2++ // SEC-LAST
:"O"%1+\"O"/80g2++ // LAST
:"O"%1+\"O"/90g2++ // CURRENT
// index to array-coord [Denominator] [stack] -> [stack, stack]
:"O"%1+\"O"/71g54*++ // SEC-LAST
:"O"%1+\"O"/81g54*++ // LAST
:"O"%1+\"O"/91g54*++ // CURRENT
// => indizies are [0;6;12]
// cycle-index one step:
idx = (idx + 6) % 18
// index to array-coord [N_1] [stack] -> [stack, stack]
:"O"%1+\"O"/2+
// index to array-coord [N_2] [stack] -> [stack, stack]
:"O"%1+\"O"/8+
// index to array-coord [N_3] [stack] -> [stack, stack]
:"O"%1+\"O"/72*+
// index to array-coord [D_1] [stack] -> [stack, stack]
:"O"%1+\"O"/54*+
// index to array-coord [D_2] [stack] -> [stack, stack]
:"O"%1+\"O"/892*++
// index to array-coord [D_3] [stack] -> [stack, stack]
:"O"%1+\"O"/48*+
// OEIS-A123335 (= numerator)
a(n) = 2*a(n-1)+a(n-2) for n>1, a(0)=1, a(1)=1.
// OEIS-A000129 (= denominator)
a(n) = 2*a(n-1)+a(n-2) for n>1, a(0)=0, a(1)=1.
---------------------------------------
I was a bit lazy with this problem. The first thing i did was search on OEIS for the numerator and denominator sequences.
And I found both, they are **A123335** and **A000129**.
But still there are two mayor problems:
- First these are recursive functions, so we need to store the last and the second last result. This is again the reason why our programs exceeds the Befunge-93 size restrictions. We need three fields for the numerator and three for the denominator (Current value | Last value | Second last value).
- Second the numbers become big. Like *really* big. The last values get close to four hundred digits. So - again - we need to do the calculations manually *(long multiplication and addition)*
In the end we have a reasonable fast program with six 79*5 arrays for value storage.