2
$\begingroup$

What is the smallest positive integer one can find impossible to create by $11$ or less factorials?

I only know how to limit the possibilities, but not how to actually solve this. I'm assuming that this is a simple trick in a logic question, but I can't seem to see how to start, nor figure out what type of question this is. Any ideas?

Thanks!

$\endgroup$
  • 1
    $\begingroup$ $1$? ${}{}{}{}{}{}$ $\endgroup$ – user384138 Jan 15 '17 at 0:51
  • $\begingroup$ I'm sorry, I edited the question $\endgroup$ – user406996 Jan 15 '17 at 0:56
2
$\begingroup$

$<2!$ you need one factorial, $1!=1$

$<3!$ you might need another $2 \times 2!$

$<4!$ you might need another $3 \times 3!$

$<5!$ you might need another $4 \times 4!$

$<2\times 5!$ you might need another $1 \times 5!$ - we could need $11$ factorials at this point

At $3\times 5!-1=359$, then, you should need $12$ factorial to sum to this number.

(see also factorial number system)

$\endgroup$
  • $\begingroup$ So the strategy is to try numbers 1 less than a multiple of n factorial? $\endgroup$ – user406996 Jan 15 '17 at 1:06
  • 1
    $\begingroup$ @user406996 Such numbers require a lot of factorials to sum to, for sure. $\endgroup$ – Joffan Jan 15 '17 at 1:07
  • $\begingroup$ Ok, thanks! I understand how you did it now. $\endgroup$ – user406996 Jan 15 '17 at 1:07
1
$\begingroup$

1 cannot be summed as 11 factorials.

Does your question mean "no more than 11 factorials"?

(after your edit)

it looks like task of dynamical programming - calculate for an n the minimal number of the factorials in the sum.

$\endgroup$
  • 1
    $\begingroup$ Yes, thanks for catching that! :) $\endgroup$ – user406996 Jan 15 '17 at 0:55
  • $\begingroup$ Yes, but is there a way to this with just pencil and paper? $\endgroup$ – user406996 Jan 15 '17 at 1:03
  • $\begingroup$ Try to precalculate answer(it is 359 ^_^) and create a proof after $\endgroup$ – kotomord Jan 15 '17 at 1:12
  • 1
    $\begingroup$ You can build up to the number knowing that 1 less than factorials is hard to create as a sum of factorials :) Thanks for pointing out the Dynamical Programming approach! $\endgroup$ – user406996 Jan 15 '17 at 1:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.