Home

More Samples

///////////////////////////////////////////////////////////////////////////////
// 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