/////////////////////////////////////////////////////////////////////////////// // Five fives /////////////////////////////////////////////////////////////////////////////// // Enigma 1358 Adrian Somerfield, New Scientist magazine, September 17, 2005. /////////////////////////////////////////////////////////////////////////////// // You might think there is something wrong with the addition sum shown below, // but in fact each of the five numbers shown in the sum is in a different base. // // 1 1 1 0 1 // 1 1 1 0 1 // 1 1 1 0 1 // 1 1 1 0 1 // --------- // 1 1 1 0 1 // // All five numbers are even and the given total at the bottom is less // than 100,000. // // What is that total? // /////////////////////////////////////////////////////////////////////////////// // // Solve the problem by running the query: // // all FiveFives(x) // /////////////////////////////////////////////////////////////////////////////// // // Results: // // x = 88724 // ___ Solution: 1 ___ [00:00:00] __ [Backtracks: 746] ____ // // Number of solutions: 1 Number of backtracks: 1238 // Elapsed time: 00:00:00 // /////////////////////////////////////////////////////////////////////////////// // // Notes: // 1. We can express a number "x" in a numerical base "b" as follows: // // x4*(b**4) + x3*(b**3) + x2*(b**2) + x1*(b**1) + x0*(b**0) // // In our case, the constraint on the upper value of the numerical base "b" // can be obtained by realizing that the most significant digit to the // fourth power must be less than 100000: // // b**4 < 100000 => b < 18 as 18*18*18*18 = 104976. // // We don't have to be very precise here, smaller estimate will find no // solutions, a larger one will work fine, but the program may run an extra // second or so longer. // // 2. There are actually 24 identical solutions, as there are as many permutations // you can add four numbers. We get around it by setting the requirement that // the base numbers are in a fixed order. This reduces the number of // permutations from 24 to 1. // // 3. As it happens, the requirement that all numbers are even is not required. // To prove it, simply remove all constraints // // z mod 2 = 0 // // and re-run the program. The results will be the same. // /////////////////////////////////////////////////////////////////////////////// pred FiveFives(x::L) iff // Array of five numerical bases, all different. Max. base 17. a::[0..4]->>[2..17] & a = [b1,b2,b3,b4,b5] & // Constrain the first four bases to be in a fixed order. // Feel free to remove the constraint, this will result in 24 // identical solutions. _AllAscending(b1,b2,b3,b4) & // Convert the strings '11101' to numbers using varios numerical bases. // Feel free to remove the requirement of the number being even y1 = RtlStoLx('11101',b1) & y1 mod 2 = 0 & y2 = RtlStoLx('11101',b2) & y2 mod 2 = 0 & y3 = RtlStoLx('11101',b3) & y3 mod 2 = 0 & y4 = RtlStoLx('11101',b4) & y4 mod 2 = 0 & x = RtlStoLx('11101',b5) & x mod 2 = 0 & x = y1 + y2 + y3 + y4 & x < 100000
This page was created by F1toHTML