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.

$\endgroup$
9
  • 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, 2012 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, 2012 at 19:32
  • 1
    $\begingroup$ Do you allow the use of parens? $\endgroup$
    – ncmathsadist
    Jul 23, 2012 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, 2012 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, 2012 at 20:07

3 Answers 3

Reset to default
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$...

$\endgroup$
15
  • 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, 2012 at 20:16
  • 4
    $\begingroup$ 1+6+2*(24+1)=57 $\endgroup$
    – Colin McQuillan
    Jul 23, 2012 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, 2012 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, 2012 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, 2012 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}

$\endgroup$
1
  • 7
    $\begingroup$ He wants to use each number at most once $\endgroup$
    – Thomas Andrews
    Jul 23, 2012 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.

$\endgroup$
1
  • $\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, 2014 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.