Greedy algorithm for Egyptian fractions: Difference between revisions
Content added Content deleted
(Added Prolog Solution) |
|||
Line 2,047: | Line 2,047: | ||
Largest number of terms is 13 for 529/914, 641/796 |
Largest number of terms is 13 for 529/914, 641/796 |
||
Largest size for denominator is 2847 digits (83901...92705) for 36/457, 529/914 |
Largest size for denominator is 2847 digits (83901...92705) for 36/457, 529/914 |
||
</pre> |
|||
=={{header|Prolog}}== |
|||
{{works with|SWI Prolog}} |
|||
<lang prolog>count_digits(Number, Count):- |
|||
atom_number(A, Number), |
|||
atom_length(A, Count). |
|||
integer_to_atom(Number, Atom):- |
|||
atom_number(A, Number), |
|||
atom_length(A, Count), |
|||
(Count =< 20 -> |
|||
Atom = A |
|||
; |
|||
sub_atom(A, 0, 10, _, A1), |
|||
P is Count - 10, |
|||
sub_atom(A, P, 10, _, A2), |
|||
atom_concat(A1, '...', A3), |
|||
atom_concat(A3, A2, Atom) |
|||
). |
|||
egyptian(0, _, []):- !. |
|||
egyptian(X, Y, [Z|E]):- |
|||
Z is (Y + X - 1)//X, |
|||
X1 is -Y mod X, |
|||
Y1 is Y * Z, |
|||
egyptian(X1, Y1, E). |
|||
print_egyptian([]):- !. |
|||
print_egyptian([N|List]):- |
|||
integer_to_atom(N, A), |
|||
write(1/A), |
|||
(List = [] -> true; write(' + ')), |
|||
print_egyptian(List). |
|||
print_egyptian(X, Y):- |
|||
writef('Egyptian fraction for %t/%t: ', [X, Y]), |
|||
(X > Y -> |
|||
N is X//Y, |
|||
writef('[%t] ', [N]), |
|||
X1 is X mod Y |
|||
; |
|||
X1 = X |
|||
), |
|||
egyptian(X1, Y, E), |
|||
print_egyptian(E), |
|||
nl. |
|||
max_terms_and_denominator1(D, Max_terms, Max_denom, Max_terms1, Max_denom1):- |
|||
max_terms_and_denominator1(D, 1, Max_terms, Max_denom, Max_terms1, Max_denom1). |
|||
max_terms_and_denominator1(D, D, Max_terms, Max_denom, Max_terms, Max_denom):- !. |
|||
max_terms_and_denominator1(D, N, Max_terms, Max_denom, Max_terms1, Max_denom1):- |
|||
Max_terms1 = f(_, _, _, Len1), |
|||
Max_denom1 = f(_, _, _, Max1), |
|||
egyptian(N, D, E), |
|||
length(E, Len), |
|||
last(E, Max), |
|||
(Len > Len1 -> |
|||
Max_terms2 = f(N, D, E, Len) |
|||
; |
|||
Max_terms2 = Max_terms1 |
|||
), |
|||
(Max > Max1 -> |
|||
Max_denom2 = f(N, D, E, Max) |
|||
; |
|||
Max_denom2 = Max_denom1 |
|||
), |
|||
N1 is N + 1, |
|||
max_terms_and_denominator1(D, N1, Max_terms, Max_denom, Max_terms2, Max_denom2). |
|||
max_terms_and_denominator(N, Max_terms, Max_denom):- |
|||
max_terms_and_denominator(N, 1, Max_terms, Max_denom, f(0, 0, [], 0), |
|||
f(0, 0, [], 0)). |
|||
max_terms_and_denominator(N, N, Max_terms, Max_denom, Max_terms, Max_denom):-!. |
|||
max_terms_and_denominator(N, N1, Max_terms, Max_denom, Max_terms1, Max_denom1):- |
|||
max_terms_and_denominator1(N1, Max_terms2, Max_denom2, Max_terms1, Max_denom1), |
|||
N2 is N1 + 1, |
|||
max_terms_and_denominator(N, N2, Max_terms, Max_denom, Max_terms2, Max_denom2). |
|||
show_max_terms_and_denominator(N):- |
|||
writef('Proper fractions with most terms and largest denominator, limit = %t:\n', [N]), |
|||
max_terms_and_denominator(N, f(N_max_terms, D_max_terms, E_max_terms, Len), |
|||
f(N_max_denom, D_max_denom, E_max_denom, Max)), |
|||
writef('Most terms (%t): %t/%t = ', [Len, N_max_terms, D_max_terms]), |
|||
print_egyptian(E_max_terms), |
|||
nl, |
|||
count_digits(Max, Digits), |
|||
writef('Largest denominator (%t digits): %t/%t = ', [Digits, N_max_denom, D_max_denom]), |
|||
print_egyptian(E_max_denom), |
|||
nl. |
|||
main:- |
|||
print_egyptian(43, 48), |
|||
print_egyptian(5, 121), |
|||
print_egyptian(2014, 59), |
|||
nl, |
|||
show_max_terms_and_denominator(100), |
|||
nl, |
|||
show_max_terms_and_denominator(1000).</lang> |
|||
{{out}} |
|||
<pre> |
|||
Egyptian fraction for 43/48: 1/2 + 1/3 + 1/16 |
|||
Egyptian fraction for 5/121: 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795...3418846225 |
|||
Egyptian fraction for 2014/59: [34] 1/8 + 1/95 + 1/14947 + 1/670223480 |
|||
Proper fractions with most terms and largest denominator, limit = 100: |
|||
Most terms (8): 44/53 = 1/2 + 1/4 + 1/13 + 1/307 + 1/120871 + 1/20453597227 + 1/6972493991...6783218655 + 1/1458470173...7836808420 |
|||
Largest denominator (150 digits): 8/97 = 1/13 + 1/181 + 1/38041 + 1/1736503177 + 1/3769304102927363485 + 1/1894353789...8154430149 + 1/5382864419...4225813153 + 1/5795045870...3909789665 |
|||
Proper fractions with most terms and largest denominator, limit = 1000: |
|||
Most terms (13): 641/796 = 1/2 + 1/4 + 1/19 + 1/379 + 1/159223 + 1/28520799973 + 1/9296411783...1338400861 + 1/1008271507...4174730681 + 1/1219933718...8484537833 + 1/1860297848...1025882029 + 1/4614277444...8874327093 + 1/3193733450...1456418881 + 1/2039986670...2410165441 |
|||
Largest denominator (2847 digits): 36/457 = 1/13 + 1/541 + 1/321409 + 1/114781617793 + 1/1482167225...0844346913 + 1/2510651068...4290086881 + 1/7353930250...3326272641 + 1/6489634815...7391865217 + 1/5264420004...5476206145 + 1/3695215730...1238141889 + 1/2048192894...4706590593 + 1/8390188268...5525592705 |
|||
</pre> |
</pre> |
||