4 ms·
I took it down to under 5 mins on my old Macbook by memoizing exponentiation and aborting calculation/addition/comparison of later terms if the earlier sum exce
by pinewurst 8y ago
I took it down to under 5 mins on my old Macbook by memoizing exponentiation and aborting calculation/addition/comparison of later terms if the earlier sum exceeded the result.
- triska 8y agoVery nice! For comparison, here is a Prolog program that uses CLP(ℤ), constraint logic programming over integers, to search for solutions: solution(Options, Vs) :- A^5 + B^5 + C^5 + D^5 #= E^5, Vs = [A,B,C,D,E], A #>= B, B #>= C, C #>= D, length(_, Exp), Upper #= 2^Exp, portray_clause(Upper), Vs ins 1..Upper, labeling(Options, Vs). The speed of this program depends a lot on the Prolog implementation, and also on the options that are used to specify the search strategy. With this program, one can find a solution within one minute even with rather slow Prolog systems on (current) commodity machines: ?- time(solution([bisect], Vs)). 1. 2. 4. 8. 16. 32. 64. 128. 256. % 609,346,692 inferences, 57.855 CPU in 58.197 seconds (99% CPU, 10532282 Lips) Vs = [133, 110, 84, 27, 144] .