Greedy algorithm for Egyptian fractions: Difference between revisions
Greedy algorithm for Egyptian fractions (view source)
Revision as of 08:45, 10 April 2020
, 4 years agoAdded Prolog Solution
(Added Prolog Solution) |
|||
Line 2,047:
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
</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>
| |||