Greedy algorithm for Egyptian fractions
mを動かして、m/nをGreedy algorithmでエジプト式分数にしたときに分母が大きなものが出るようにしてみた。
def A(x, y)
m = y / x
m += 1 if y % x > 0
m
end
def B(n, a = [])
return [1] if n == 1
x, y = n.numerator, n.denominator
return a if y == 1
m = A(x, y)
a << m
x, y = (-y) % x, y * m
n = x.to_r / y
return B(n, a)
end
def show(a, b, ary)
print "#{a}/#{b} = 1/#{ary[0]}"
ary[1..-1].each{|i|
print " + 1/#{i}"
}
puts
end
def C(n)
(2..n).each{|i|
max = 0
m = 0
ary = []
(1..i - 1).each{|j|
x = j.to_r / i
a = B(x)
b = a[-1]
if max < b
max = b
m = j
ary = a
end
}
show(m, i, ary)
}
end
n = 200
ary = C(n)
出力結果
1/2 = 1/2
2/3 = 1/2 + 1/6
1/4 = 1/4
4/5 = 1/2 + 1/4 + 1/20
1/6 = 1/6
3/7 = 1/3 + 1/11 + 1/231
3/8 = 1/3 + 1/24
2/9 = 1/5 + 1/45
3/10 = 1/4 + 1/20
8/11 = 1/2 + 1/5 + 1/37 + 1/4070
1/12 = 1/12
3/13 = 1/5 + 1/33 + 1/2145
6/14 = 1/3 + 1/11 + 1/231
2/15 = 1/8 + 1/120
7/16 = 1/3 + 1/10 + 1/240
4/17 = 1/5 + 1/29 + 1/1233 + 1/3039345
4/18 = 1/5 + 1/45
14/19 = 1/2 + 1/5 + 1/28 + 1/887 + 1/2359420
9/20 = 1/3 + 1/9 + 1/180
17/21 = 1/2 + 1/4 + 1/17 + 1/1428
5/22 = 1/5 + 1/37 + 1/4070
7/23 = 1/4 + 1/19 + 1/583 + 1/1019084
5/24 = 1/5 + 1/120
4/25 = 1/7 + 1/59 + 1/5163 + 1/53307975
6/26 = 1/5 + 1/33 + 1/2145
20/27 = 1/2 + 1/5 + 1/25 + 1/1350
11/28 = 1/3 + 1/17 + 1/1428
27/29 = 1/2 + 1/3 + 1/11 + 1/148 + 1/28328 + 1/1003066152
4/30 = 1/8 + 1/120
5/31 = 1/7 + 1/55 + 1/3979 + 1/23744683 + 1/1127619917796295
5/32 = 1/7 + 1/75 + 1/16800
5/33 = 1/7 + 1/116 + 1/26796
8/34 = 1/5 + 1/29 + 1/1233 + 1/3039345
29/35 = 1/2 + 1/4 + 1/13 + 1/607 + 1/1104740
5/36 = 1/8 + 1/72
11/37 = 1/4 + 1/22 + 1/543 + 1/884004
9/38 = 1/5 + 1/28 + 1/887 + 1/2359420
31/39 = 1/2 + 1/4 + 1/23 + 1/718 + 1/1288092
17/40 = 1/3 + 1/11 + 1/1320
36/41 = 1/2 + 1/3 + 1/23 + 1/809 + 1/915465 + 1/1396792694910
13/42 = 1/4 + 1/17 + 1/1428
7/43 = 1/7 + 1/51 + 1/3071 + 1/11785731 + 1/185204595153417
7/44 = 1/7 + 1/62 + 1/9548
14/45 = 1/4 + 1/17 + 1/438 + 1/223380
14/46 = 1/4 + 1/19 + 1/583 + 1/1019084
35/47 = 1/2 + 1/5 + 1/23 + 1/832 + 1/1498987 + 1/6740884579520
11/48 = 1/5 + 1/35 + 1/1680
19/49 = 1/3 + 1/19 + 1/559 + 1/780644 + 1/1218809328828
8/50 = 1/7 + 1/59 + 1/5163 + 1/53307975
12/51 = 1/5 + 1/29 + 1/1233 + 1/3039345
5/52 = 1/11 + 1/191 + 1/109252
44/53 = 1/2 + 1/4 + 1/13 + 1/307 + 1/120871 + 1/20453597227 + 1/697249399186783218655 + 1/1458470173998990524806872692984177836808420
13/54 = 1/5 + 1/25 + 1/1350
48/55 = 1/2 + 1/3 + 1/26 + 1/1073 + 1/2301585
11/56 = 1/6 + 1/34 + 1/2856
42/57 = 1/2 + 1/5 + 1/28 + 1/887 + 1/2359420
25/58 = 1/3 + 1/11 + 1/148 + 1/28328 + 1/1003066152
17/59 = 1/4 + 1/27 + 1/911 + 1/1160979 + 1/2246452569756
7/60 = 1/9 + 1/180
5/61 = 1/13 + 1/199 + 1/52603 + 1/4150560811 + 1/34454310087467394631
10/62 = 1/7 + 1/55 + 1/3979 + 1/23744683 + 1/1127619917796295
46/63 = 1/2 + 1/5 + 1/34 + 1/1339 + 1/7170345
7/64 = 1/10 + 1/107 + 1/34240
4/65 = 1/17 + 1/369 + 1/203873 + 1/83128196385
10/66 = 1/7 + 1/116 + 1/26796
60/67 = 1/2 + 1/3 + 1/17 + 1/298 + 1/101827 + 1/25921742996 + 1/1343873519875428369036
15/68 = 1/5 + 1/49 + 1/5554 + 1/46264820
11/69 = 1/7 + 1/61 + 1/5893 + 1/86812730 + 1/15072900093293070
23/70 = 1/4 + 1/13 + 1/607 + 1/1104740
53/71 = 1/2 + 1/5 + 1/22 + 1/977 + 1/1271729 + 1/2425940702433 + 1/11770376583439808963536545
11/72 = 1/7 + 1/101 + 1/50904
18/73 = 1/5 + 1/22 + 1/893 + 1/1024399 + 1/2448583368404 + 1/8993340768034569594892420
22/74 = 1/4 + 1/22 + 1/543 + 1/884004
12/75 = 1/7 + 1/59 + 1/5163 + 1/53307975
17/76 = 1/5 + 1/43 + 1/2335 + 1/7630780
47/77 = 1/2 + 1/10 + 1/97 + 1/12449 + 1/232453953 + 1/108069680298198465
23/78 = 1/4 + 1/23 + 1/718 + 1/1288092
39/79 = 1/3 + 1/7 + 1/58 + 1/4184 + 1/40259285 + 1/8104050103296840
39/80 = 1/3 + 1/7 + 1/89 + 1/13593 + 1/677475120
20/81 = 1/5 + 1/22 + 1/686 + 1/764033 + 1/1167492086145
31/82 = 1/3 + 1/23 + 1/809 + 1/915465 + 1/1396792694910
61/83 = 1/2 + 1/5 + 1/29 + 1/2189 + 1/5854359 + 1/308461667853570
19/84 = 1/5 + 1/39 + 1/1820
33/85 = 1/3 + 1/19 + 1/441 + 1/356108 + 1/253625459220
14/86 = 1/7 + 1/51 + 1/3071 + 1/11785731 + 1/185204595153417
70/87 = 1/2 + 1/4 + 1/19 + 1/509 + 1/673102 + 1/1132665082908
43/88 = 1/3 + 1/7 + 1/81 + 1/9980 + 1/124490520
50/89 = 1/2 + 1/17 + 1/337 + 1/145681 + 1/29711989585 + 1/1471337208468868797457 + 1/6494499543074890436870241790813851000203090
28/90 = 1/4 + 1/17 + 1/438 + 1/223380
5/91 = 1/19 + 1/433 + 1/249553 + 1/93414800161 + 1/17452649778145716451681
9/92 = 1/11 + 1/145 + 1/48914 + 1/3588820180
15/93 = 1/7 + 1/55 + 1/3979 + 1/23744683 + 1/1127619917796295
23/94 = 1/5 + 1/23 + 1/832 + 1/1498987 + 1/6740884579520
62/95 = 1/2 + 1/7 + 1/103 + 1/15222 + 1/260657723 + 1/135884896858431735
23/96 = 1/5 + 1/26 + 1/892 + 1/1391520
8/97 = 1/13 + 1/181 + 1/38041 + 1/1736503177 + 1/3769304102927363485 + 1/18943537893793408504192074528154430149 + 1/538286441900380211365817285104907086347439746130226973253778132494225813153 + 1/579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665
38/98 = 1/3 + 1/19 + 1/559 + 1/780644 + 1/1218809328828
71/99 = 1/2 + 1/5 + 1/59 + 1/4494 + 1/21874545
49/100 = 1/3 + 1/7 + 1/73 + 1/9018 + 1/230409900
84/101 = 1/2 + 1/4 + 1/13 + 1/211 + 1/48182 + 1/3813853094 + 1/16969721322568415215 + 1/863914325296899369798407851627362073460
24/102 = 1/5 + 1/29 + 1/1233 + 1/3039345
24/103 = 1/5 + 1/31 + 1/1331 + 1/3035631 + 1/32252691452933 + 1/2080472211916162528417152045
51/104 = 1/3 + 1/7 + 1/71 + 1/9122 + 1/141449381 + 1/100039636784966424
31/105 = 1/4 + 1/23 + 1/569 + 1/422811 + 1/774665857980
35/106 = 1/4 + 1/13 + 1/307 + 1/120871 + 1/20453597227 + 1/697249399186783218655 + 1/1458470173998990524806872692984177836808420
64/107 = 1/2 + 1/11 + 1/139 + 1/36357 + 1/1699461221 + 1/4043435816656473957 + 1/27248955339034010790024973983708922458
17/108 = 1/7 + 1/69 + 1/17388
6/109 = 1/19 + 1/415 + 1/214867 + 1/61556888719 + 1/5683875823083467302723 + 1/64612888744465525793841376769540622379126735
41/110 = 1/3 + 1/26 + 1/1073 + 1/2301585
79/111 = 1/2 + 1/5 + 1/86 + 1/11933 + 1/284781045
25/112 = 1/5 + 1/44 + 1/2054 + 1/6326320
14/113 = 1/9 + 1/79 + 1/8035 + 1/92222287 + 1/14883662791920859 + 1/886093672414437662516188885270665
27/114 = 1/5 + 1/28 + 1/887 + 1/2359420
73/115 = 1/2 + 1/8 + 1/103 + 1/13538 + 1/213810147 + 1/137144336666674680
45/116 = 1/3 + 1/19 + 1/509 + 1/673102 + 1/1132665082908
94/117 = 1/2 + 1/4 + 1/19 + 1/1271 + 1/2260347 + 1/8515278673668
34/118 = 1/4 + 1/27 + 1/911 + 1/1160979 + 1/2246452569756
111/119 = 1/2 + 1/3 + 1/11 + 1/118 + 1/17823 + 1/688244057 + 1/947359763303394441
19/120 = 1/7 + 1/65 + 1/10920
5/121 = 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225
10/122 = 1/13 + 1/199 + 1/52603 + 1/4150560811 + 1/34454310087467394631
89/123 = 1/2 + 1/5 + 1/43 + 1/3112 + 1/11756692 + 1/241884650113320
20/124 = 1/7 + 1/55 + 1/3979 + 1/23744683 + 1/1127619917796295
123/125 = 1/2 + 1/3 + 1/7 + 1/129 + 1/17366 + 1/490046813 + 1/480291757372867125
29/126 = 1/5 + 1/34 + 1/1339 + 1/7170345
63/127 = 1/3 + 1/7 + 1/51 + 1/3779 + 1/19037343 + 1/543630623712131 + 1/591068510075280592134089410191
7/128 = 1/19 + 1/487 + 1/394795 + 1/467588881280
21/129 = 1/7 + 1/51 + 1/3071 + 1/11785731 + 1/185204595153417
8/130 = 1/17 + 1/369 + 1/203873 + 1/83128196385
65/131 = 1/3 + 1/7 + 1/51 + 1/2599 + 1/8103163 + 1/82076555152549 + 1/8982081207612474990993110653 + 1/121016674230217765593132828801254329768662133572660018961 + 1/29290070883485305257170727916346131549433432526041820570286255057924204445456330131039739635641147751253099020081
31/132 = 1/5 + 1/29 + 1/2735 + 1/10469580
44/133 = 1/4 + 1/13 + 1/257 + 1/77279 + 1/27471324390 + 1/1886684159324050855860
53/134 = 1/3 + 1/17 + 1/298 + 1/101827 + 1/25921742996 + 1/1343873519875428369036
44/135 = 1/4 + 1/14 + 1/223 + 1/76631 + 1/64595335140
11/136 = 1/13 + 1/253 + 1/149102 + 1/33346960504
106/137 = 1/2 + 1/4 + 1/43 + 1/2143 + 1/5610851 + 1/40476400174551 + 1/2293674559526508636175097691 + 1/8768238308365205681757381048272405318708454952814121444
22/138 = 1/7 + 1/61 + 1/5893 + 1/86812730 + 1/15072900093293070
66/139 = 1/3 + 1/8 + 1/61 + 1/10711 + 1/167665051 + 1/52207200010738351 + 1/19079142130728669285180785264656056
53/140 = 1/3 + 1/23 + 1/569 + 1/422811 + 1/774665857980
23/141 = 1/7 + 1/50 + 1/3797 + 1/17034723 + 1/1063999871149950
35/142 = 1/5 + 1/22 + 1/977 + 1/1271729 + 1/2425940702433 + 1/11770376583439808963536545
32/143 = 1/5 + 1/43 + 1/1922 + 1/8441699 + 1/166278649573704 + 1/41472883956081813852742845720
11/144 = 1/14 + 1/202 + 1/101808
9/145 = 1/17 + 1/309 + 1/108813 + 1/13813538318 + 1/381627681711894999930
36/146 = 1/5 + 1/22 + 1/893 + 1/1024399 + 1/2448583368404 + 1/8993340768034569594892420
8/147 = 1/19 + 1/559 + 1/780644 + 1/1218809328828
71/148 = 1/3 + 1/7 + 1/283 + 1/175913 + 1/154726741932
40/149 = 1/4 + 1/55 + 1/3643 + 1/17059649 + 1/679073772281154 + 1/691711782300234218923463076420
24/150 = 1/7 + 1/59 + 1/5163 + 1/53307975
130/151 = 1/2 + 1/3 + 1/37 + 1/1765 + 1/4551257 + 1/24480106688801 + 1/6592031858445849582740304810
25/152 = 1/7 + 1/47 + 1/2942 + 1/24520590 + 1/901888976401560
112/153 = 1/2 + 1/5 + 1/32 + 1/1289 + 1/2868611 + 1/90518216893920
17/154 = 1/10 + 1/97 + 1/12449 + 1/232453953 + 1/108069680298198465
86/155 = 1/2 + 1/19 + 1/454 + 1/222839 + 1/74485607043 + 1/11096211313053936800655
25/156 = 1/7 + 1/58 + 1/6334 + 1/100292556
13/157 = 1/13 + 1/171 + 1/31729 + 1/1384221253 + 1/3065709562226802762 + 1/15664291866548091057524723739191244978
78/158 = 1/3 + 1/7 + 1/58 + 1/4184 + 1/40259285 + 1/8104050103296840
132/159 = 1/2 + 1/4 + 1/13 + 1/307 + 1/120871 + 1/20453597227 + 1/697249399186783218655 + 1/1458470173998990524806872692984177836808420
78/160 = 1/3 + 1/7 + 1/89 + 1/13593 + 1/677475120
102/161 = 1/2 + 1/8 + 1/118 + 1/15199 + 1/385000803 + 1/444676854546933624
40/162 = 1/5 + 1/22 + 1/686 + 1/764033 + 1/1167492086145
39/163 = 1/5 + 1/26 + 1/1247 + 1/2935993 + 1/11082924787499 + 1/286606184305828343790787504 + 1/123214657323519667859049566141092194172466586933037520
39/164 = 1/5 + 1/27 + 1/1303 + 1/2622584 + 1/18914351179320
134/165 = 1/2 + 1/4 + 1/17 + 1/304 + 1/121818 + 1/17312774160
39/166 = 1/5 + 1/29 + 1/2189 + 1/5854359 + 1/308461667853570
100/167 = 1/2 + 1/11 + 1/127 + 1/51845 + 1/3455824759 + 1/27866357781351460764 + 1/1164800843997430660100641743273595734780
41/168 = 1/5 + 1/23 + 1/1757 + 1/4849320
101/169 = 1/2 + 1/11 + 1/149 + 1/79141 + 1/8768537893 + 1/128145427959526261189 + 1/49263752120790404508611388524063616819974
66/170 = 1/3 + 1/19 + 1/441 + 1/356108 + 1/253625459220
17/171 = 1/11 + 1/118 + 1/31709 + 1/1407613245 + 1/3302291744424770130
37/172 = 1/5 + 1/67 + 1/5239 + 1/33541243 + 1/1446447800439535 + 1/2929095735154914968387066983180
96/173 = 1/2 + 1/19 + 1/439 + 1/262363 + 1/108167992132 + 1/13650366942071648230863 + 1/558997552959607441944152226025691321588943444
53/174 = 1/4 + 1/19 + 1/509 + 1/673102 + 1/1132665082908
52/175 = 1/4 + 1/22 + 1/593 + 1/507345 + 1/463317600900
39/176 = 1/5 + 1/47 + 1/3182 + 1/21934587 + 1/1443378298647120
127/177 = 1/2 + 1/5 + 1/58 + 1/3667 + 1/23528389 + 1/2214340332212895
11/178 = 1/17 + 1/337 + 1/145681 + 1/29711989585 + 1/1471337208468868797457 + 1/6494499543074890436870241790813851000203090
144/179 = 1/2 + 1/4 + 1/19 + 1/545 + 1/353057 + 1/153978126369 + 1/31004421369217672882150 + 1/1249656387772001920982167116032051316452327100
17/180 = 1/11 + 1/283 + 1/560340
6/181 = 1/31 + 1/1123 + 1/1575289 + 1/3308712336073 + 1/16421365984319164633255921 + 1/539322521581909053519582180808841844787134329860561
10/182 = 1/19 + 1/433 + 1/249553 + 1/93414800161 + 1/17452649778145716451681
15/183 = 1/13 + 1/199 + 1/52603 + 1/4150560811 + 1/34454310087467394631
15/184 = 1/13 + 1/218 + 1/86910 + 1/11329935240
169/185 = 1/2 + 1/3 + 1/13 + 1/308 + 1/96619 + 1/12629922011 + 1/387393401425515625140
30/186 = 1/7 + 1/55 + 1/3979 + 1/23744683 + 1/1127619917796295
135/187 = 1/2 + 1/5 + 1/46 + 1/5377 + 1/38544129 + 1/2228474782008833 + 1/9932199708098629290522998034945
89/188 = 1/3 + 1/8 + 1/67 + 1/6871 + 1/103856540 + 1/13482726022107960
110/189 = 1/2 + 1/13 + 1/197 + 1/88006 + 1/10649364044 + 1/226817909072630703828
29/190 = 1/7 + 1/103 + 1/15222 + 1/260657723 + 1/135884896858431735
148/191 = 1/2 + 1/4 + 1/41 + 1/2089 + 1/5948713 + 1/55608429754153 + 1/7215360739352604644951989802 + 1/78092145898486448316413360318084768475684343693716009004
19/192 = 1/11 + 1/125 + 1/20308 + 1/1340328000
51/193 = 1/4 + 1/71 + 1/6091 + 1/47694271 + 1/3184640833015747 + 1/16903228725518715094350416930935 + 1/857157424041603136173297512143544981234507697558703363262991740
16/194 = 1/13 + 1/181 + 1/38041 + 1/1736503177 + 1/3769304102927363485 + 1/18943537893793408504192074528154430149 + 1/538286441900380211365817285104907086347439746130226973253778132494225813153 + 1/579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665
157/195 = 1/2 + 1/4 + 1/19 + 1/401 + 1/349578 + 1/346246521660
76/196 = 1/3 + 1/19 + 1/559 + 1/780644 + 1/1218809328828
58/197 = 1/4 + 1/23 + 1/1067 + 1/1289221 + 1/3561621825439 + 1/17759210038417246800734371 + 1/525649235314366514313374231178048734749528033875031 + 1/828921355759734781847129205289349573374693956396002400876921135513991799841861945209498105233141877852
43/198 = 1/5 + 1/59 + 1/4494 + 1/21874545
11/199 = 1/19 + 1/379 + 1/159223 + 1/28520799973 + 1/929641178371338400861 + 1/1008271507277592391123742528036634174730681 + 1/1219933718865393655364635368068124756713122928811333803786753398211072842948484537833 + 1/1860297848030936654742608399135821395565274404917258533393305147319524009551744684579405649080712180254407780735949179513154143641842892458088536544987153757401025882029 + 1/4614277444518045184646591832326467411359277711335974416082881814986405515888533562332069783067894981850924485553345190160771506460024406127868096951360637582674289834858262576425271895218431296391169922044160278696744025988461165811212428548328350795432691637759392474030879286312785400132190057899968737693594392669884878193448874327093 + 1/31937334502481972335865307630139228000187060941658399518862518849553429993133277230560087986574331290756232125775998863890963263813589266879406694561350952988662850757053371133819179770003609046815203982179108798005308113258134895569927488690118483730232440575942894680942308888321353318333183158977270294582315388855860989819894602178852719674244639951777398683083694723999674418435726557523519535770015019287382321071804865681731226989916286199314883016472947639367666251368202759691810399195092598892275413777035275182318485652713871000041272524440519262054008953943029365257325370839037761555465335452562216651250516983405134378252470216494582635109781712938341456418881 + 1/2039986670246850822853427080268636607703538330430958135006350872460188775376402385474575383380701179275926633909293920375037781006938834602683282504456671345800481611955974906577358109966753513899436209725756764159504134559394933538420714469300931804842468643272796657406808805007786178371184391663721349034183315512035012402176731111044506314978549915206516847224339930494935465558632905912262959736737614637514921726288403470224139024425700070180324623265095949577758695292697562554242228453440276043742370033993859881981612938703208463591285870376619588297958810138295747858827756577616148419423031480258559516303907719233914603343421735341220080271152090557188286289527661792734931298102513902518914250419121432886312102736349552224188669212688846219382874287241971706387850290821170997846726526589069990513808709560793139660289273086403155344460608865436195352720549406793512677065107181955781264579349071905411393100989250722104770801720673437692418988638492506057962758754921169589084980707251205329924087857682559921447010465898318288868258062129919867004394488124710647843586978379399594154917914477913086776811741840849911967039211773201428676384229432761943488196359561416605048969002045397348240530911560634680322446588472763785839765588633770016209055874572792498932175778494089116461654628549726895871636209026849103988563732410165441
9/200 = 1/23 + 1/658 + 1/504467 + 1/763460357800
