30
$\begingroup$

Let S be the set $\{0!, 1!, 2!, \ldots\}$. Is it possible to construct any positive integer using only addition, subtraction and multiplication, and using any element in S at most once? For example:

$$ 3 = 2! + 1!$$ $$ 4 = 3! - 2! = 2! + 1! + 0!$$ $$ 146 = 4!\cdot3! + 2!$$

etc. My gut instinct says that this isn't true, but I can't see why. Something like 8076 doesn't have an obvious solution, but maybe you can get it by subtraction a huge factorial from the product of two smaller factorials or something. Or maybe there's a way of finding sets of factorials that add/subtract/multiply to 1, in which case any number can be constructed this way. I've tried finding something but haven't had much luck.

EDIT: Oops, positive integer, not positive number.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Do you mean positive integer? Any positive even integer can be written as the sum of $2!$s, and any positive odd integer is $1!$ plus some nonnegative even integer. $\endgroup$ – user17794 Jul 23 '12 at 19:31
  • 2
    $\begingroup$ @TimDuff: "and using any element in $S$ at most once"; so you can only use 2! at most once. $\endgroup$ – Arturo Magidin Jul 23 '12 at 19:32
  • 1
    $\begingroup$ Do you allow the use of parens? $\endgroup$ – ncmathsadist Jul 23 '12 at 19:40
  • 1
    $\begingroup$ Note, since $0!=1!$, it isn't technically a "set" if you mean you can use $0!$ and $1!$. Just a minor language nit. $\endgroup$ – Thomas Andrews Jul 23 '12 at 19:42
  • 2
    $\begingroup$ @EricStucky No, he explicitly uses 0! and 1! in one of his examples, so he clearly means something like, "Express every natural number in terms of the sequence 0!,1!,...,k!,... with each term used at most once." $\endgroup$ – Thomas Andrews Jul 23 '12 at 20:07
17
$\begingroup$

Let me assume you're only allowed to use $0! = 1!$ once. In that case, all factorials past $4!$ are divisible by $24$, so working $\bmod 24$ the only numbers you're allowed to use are $1, 2, 6$, each at most once, and I am reasonably certain you cannot get any numbers congruent to $10 \bmod 24$ this way.

Edit: If you want to use both $0!$ and $1$, then all factorials past $5!$ are divisible by $120$, so working $\bmod 120$ the only numbers you're allowed to use are $1, 1, 2, 6, 24$. This time I am reasonably certain you cannot get any numbers congruent to $57 \bmod 120$. Just kidding! Every conjugacy class $\bmod 120$ is reachable.

Okay, working $\bmod 720$ the only numbers you're allowed to use are $1, 1, 2, 6, 24, 120$...

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ for example $10=4!-2!*(3!+1!)$. But I'm not sure whether we were allowed to use parentheses $\endgroup$ – Tigran Hakobyan Jul 23 '12 at 20:16
  • 4
    $\begingroup$ 1+6+2*(24+1)=57 $\endgroup$ – Colin McQuillan Jul 23 '12 at 21:43
  • 6
    $\begingroup$ @mjqxxxx: I just ran a (hopefully) exhaustive search, and it seems there's no way to obtain the numbers 352, 356, 364 or 368 modulo 720 from 1, 1, 2, 6, 24 and 120 using addition, multiplication and negation. $\endgroup$ – Ilmari Karonen Jul 23 '12 at 22:34
  • 2
    $\begingroup$ I got the same result [352,356,364,368] with this code: hpaste.org/72038 $\endgroup$ – Colin McQuillan Jul 23 '12 at 23:07
  • 1
    $\begingroup$ @Belgi: well, it suffices to get the first $60$. You can get $0$ through $19$ without using $24$, so by reusing all of those representations you can get $0$ through $43$ by using $24$. Then I checked $44$ through $60$... $\endgroup$ – Qiaochu Yuan Jul 23 '12 at 23:48
2
$\begingroup$

Relaxing your restriction using each factorial at most once, you may find the following helpful. For every positive integer $n$ there is a positive integer $k$ and $k$ positive integers $\{c_1, \dots, c_k \}$ such that $n$ has a unique representation in the factorial basis, \begin{align} n = \sum_{l = 1}^{k} c_{l} \ l!. \end{align}

|cite|improve this answer
$\endgroup$
  • 6
    $\begingroup$ He wants to use each number at most once $\endgroup$ – Thomas Andrews Jul 23 '12 at 20:18
0
$\begingroup$

The numbers you can construct are of the form $\sum_{j=0}^nc_jj!$ with $c_j\in\{-1,\,0,\,+1\}$. Imagine you want to construct a number smaller than $4165$. Since $7!-\sum_{j=0}^6j!=4166$, you can only use the numbers $k!$ with $0\leq k\leq 6$. That's $7$ numbers. Using your formula you can construct $3^7=2187$ numbers this way. Sadly, $2187<4165$ so the answer is no.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I like this line of thought, but you can also multiply factorials together, so there'll be more than 2187 combinations. $\endgroup$ – Hovercouch Feb 28 '14 at 18:13

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.