another interesting math riddle

[olr]

(01-13-2018 10:03 AM)Didier Lachieze Wrote:  On my Prime rev C with the Beta 3 firmware it returns {1,2,145,40585} after 16'21".

There may be smarter and faster ways to check for all possible solutions.

Another approach is to go through all sorted lists containing up to 7 digits, calculate the "factorial sum" of the digits and compare the digits of the sum with those in the list. There are \( \sum_{j=1}^7 \binom{9+j}{j} = 19447 \) sorted lists with up to 7 digits. Hence only 19447 possibilities need to be checked (and not 2540160).

If we additionally take into account that at least three (of seven) digits need to be 9s in order to get a 7-digit factorial sum ( \( 5\cdot 8!+2\cdot 9! = 927360 \) ), the number of sorted lists with seven digits decreases from 11440 down to 715. Therfore only a total of 8722 possibilities need to be checked.

The following program returns the result in 9 seconds on my Prime rev A (in 19 seconds if the 7-digit optimization is removed).

Code:


EXPORT TST()
BEGIN
    // r result list
    // l list of digits  
    // s factorial sum
    // n helper
  LOCAL 
    r:= {}, 
    l:= {0},
    s, n;

  WHILE SIZE(l) <= 7 DO
  
    s:= ΣLIST(l!);

    IF EQ( l, SORT(ASC(STRING(s))-48) ) THEN
      // The sum of factorials contains exactly
      // the summed up digits
      r(0):= s;
    END;

    // get next list of digits
    // add 1 to the last digit, that is different from 9
    // set succesor digits to the same value
    n:= SIZE(l);
    WHILE n > 0 AND l(n) == 9 DO
      n:= n-1; 
    END;
  
    IF n > 0 THEN
      l(n):= l(n)+1;
      WHILE n < SIZE(l) DO
        // a digit is never smaller than its predecessor
        l(n+1):= l(n); 
        n:= n+1; 
      END;
    ELSE
      // all digits are 9s -> new digit
      l:= MAKELIST(0,X,1,SIZE(l)+1);
    END;  

    // to get a 7-digit number at least three 9s are necessary
    // 8!*5 + 9!*2 = 927360
    IF SIZE(l) == 7 THEN
      l(5):= 9;
      l(6):= 9;
      l(7):= 9;
    END;

  END;
  RETURN r;
END;