another interesting math riddle

[Don Shepherd]

145 = 1! + 4! + 5!

find three other numbers like that.

[Gerson W. Barbosa]

1 = 1!

2 = 2!

Well, that’s 2/3 of the answers. In an examination that would grant me a C, wouldn’t it? :-)

[Joe Horn]

UBASIC:

list
   10   repeat:inc X0:X=X0:clr T
   20   while X>0:X\=10:T+=!(res):wend
   30   until T=X0:print T:goto 10
OK
run
 1
 2
 145
 40585

[Don Shepherd]

Joe, you got it.

I got this from a book, "The Penguin Dictionary of Curious and Interesting Numbers." At first I thought 40585 was wrong until I remembered that 0!=1 and not 0, another math oddity.

[Didier Lachieze]

To find a limit to the numbers that could meet the criteria, we can compare the number of digits of a number to the number of digits of the maximum sum of its digits factorials.

On the Prime in the sequence app, entering U1(N)= CEILING(LOG(9!*N))-N and going to the NUM view tells us that any number with more 7 digits cannot meet the criteria as it is superior to the maximum sum of its digits factorials (9!*8 has only 7 digits and is lower than any 8-digit number) and that for 7 digit numbers only the ones below 9!*7 (2540160) are candidates.

So the following program returns all possible solutions :

Code:

EXPORT TST()
BEGIN
 LOCAL n,r:={};
 FOR n FROM 1 TO 9!*7 DO
  IF ΣLIST((ASC(STRING(n))-48)!)==n THEN r(0):=n END;
 END;
 RETURN r;
END;

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.

[SlideRule]

(01-13-2018 06:14 AM)Don Shepherd Wrote:  … from … "The Penguin Dictionary of Curious and Interesting Numbers." …

page 140 ?

BEST!
SlideRule

[Don Shepherd]

(01-13-2018 12:47 PM)SlideRule Wrote:  

(01-13-2018 06:14 AM)Don Shepherd Wrote:  … from … "The Penguin Dictionary of Curious and Interesting Numbers." …

page 140 ?

BEST!
SlideRule

yes, that's where I saw it.

[SlideRule]

from the front cover insert of the Penguin Dictionary of Curious & Interesting Geometry…
David Wells was born in 1940. He had the rare distinction
of being a Cambridge scholar in mathematics and
failing his degree. He subsequently trained as a teacher
and, after working on computers and teaching machines,
taught mathematics and science in a primary school and
mathematics in secondary schools. He continues to be
involved with education through writing and working
with teachers.
While at university he became British under-21 chess
champion, and in the middle seventies was a game inventor,
devising 'Guerilla' and 'Checkpoint Danger', a
puzzle composer, and the puzzle editor of Games and
Puzzles magazine. From 1981 to 1983 he published The
Problem Solver, a magazine of mathematical problems
for secondary pupils. He has published several books of
problems and popular mathematics, including Can You
Solve These? and Hidden Connections, Double
Meanings, and also publishes the journal Studies of
Meaning, Language and Change. He has written The
Penguin Dictionary of Curious and Interesting Numbers
and recently published a book comparing the psychology
of the Russians with that of the West.
sic: bold my emphasis
[attachment=5559] [attachment=5560]
BEST!
SlideRule

[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;

[Didier Lachieze]

(01-13-2018 09:08 PM)olr Wrote:  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.

Great solution and optimization !

[Joe Horn]

(01-13-2018 10:03 AM)Didier Lachieze Wrote:  ... any number with more 7 digits cannot meet the criteria as it is superior to the maximum sum of its digits factorials (9!*8 has only 7 digits and is lower than any 8-digit number) and that for 7 digit numbers only the ones below 9!*7 (2540160) are candidates.

That's true in base 10, but if we extend the riddle to larger bases, it allows the factorials to be larger. For example, both 1441 and 1442 are solutions in base 15:

#1441d = #661(15) = 6! + 6! + 1!
#1442d = #662(15) = 6! + 6! + 2!

Unfortunately there don't seem to be ANY solutions which include a digit > 9, regardless of base. Strange.

[Gamo]

Here another interesting math riddle.

12345 MOD 67890 = 12345

98765 MOD 43210 = 12345

Gamo

[grsbanks]

(01-14-2018 10:22 AM)Gamo Wrote:  Here another interesting math riddle.

12345 MOD 67890 = 12345

Err... Nothing surprising about that one.

X MOD Y = X for all cases where X < Y

[Didier Lachieze]

(01-13-2018 09:08 PM)olr Wrote:  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;

I've made a few changes to your program and now it returns the result in less than 7 seconds.

Code:

EXPORT TST()
BEGIN
    // r result list
    // l list of digits  
    // s factorial sum
    // n helper
  LOCAL 
    r:= {}, 
    l:= {0},
    k, 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 successor digits to the same value
    n:= (POS(l,9)-1) MOD (SIZE(l)+1);
  
    l(n):= (l(n)+1) MOD 10; //if n=0, add a 0 element to l
    FOR k FROM n TO SIZE(l)-1 DO
      // a digit is never smaller than its predecessor
      l(k+1):= l(k); 
    END;

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

  END;
  RETURN r;
END;