3 ms·
I was just pretending to misunderstand as a joke. You did make me curious, though. The numbers are fairly small. I implemented the dumbest possible brute force
by mikeash 8y ago
I was just pretending to misunderstand as a joke.
You did make me curious, though. The numbers are fairly small. I implemented the dumbest possible brute force search for all combinations of numbers 1-255. On my laptop, it found 133^5 + 110^5 + 84^5 + 27^5 = 144^5 in about 50 minutes.
I'd guess that this laptop is something like 100,000 times faster than the CDC 6600, so that dumb search would have taken about a decade. However, you can get at least a couple orders of magnitude improvement with some simple improvements.
- pinewurst 8y agoI 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] .