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.

  • 1
    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.2012-07-23
  • 2
    @TimDuff: "and using any element in $S$ at most once"; so you can only use 2! at most once.2012-07-23
  • 0
    @TimDuff: Thanks for the catch. Edited to be positive integer.2012-07-23
  • 1
    Do you allow the use of parens?2012-07-23
  • 1
    Note, since $0!=1!$, it isn't technically a "set" if you mean you can use $0!$ and $1!$. Just a minor language nit.2012-07-23
  • 0
    @mathsadist: Parens should be okay. ThomasAndrews: how would you rephrase it?2012-07-23
  • 0
    Just remove $0!$. Like he said, it's just a language thing.2012-07-23
  • 2
    @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."2012-07-23
  • 0
    It can be rephrased using "multiset" instead of "set" to indicate the allowed repetitions.2012-07-23

3 Answers 3

17

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$...

  • 0
    He actually explicitly uses $0!$ and $1!$ in one of his examples2012-07-23
  • 0
    He gets away with it though, as a second way of expressing 4, when he first used $3!-2!$.2012-07-23
  • 0
    True, but it still implies that he probably wants to allow it, @Jean-Sébastien.2012-07-23
  • 0
    It definitely doesn't work for 10 mod 24 for 0! and 1! separately, as 34 = 4!*(3!+2!)-1!-0!. Still playing around with restricting it to using just one.2012-07-23
  • 1
    for example $10=4!-2!*(3!+1!)$. But I'm not sure whether we were allowed to use parentheses2012-07-23
  • 0
    @Hovercouch Not sure how you get $34=4!*(3!+2!)-1!-0!$. But it's easy to get $10$ with $0!$ and $1!$ as just $0!+1!+2!+3!$2012-07-23
  • 0
    130 = 24*5+10 = 5! + 4! - 2!*(3! + 1!), following Tigran's argument.2012-07-23
  • 0
    @ThomasAndrews: Ah, typo on my part. I meant 4!+(3!*2!)-1!-0!. Switched the first two operators by mistake.2012-07-23
  • 4
    1+6+2*(24+1)=572012-07-23
  • 0
    @Colin: very nice! I did not think of adding something to $24$. I can now get every congruence class $\bmod 120$...2012-07-23
  • 0
    Wow, did you actually try to get all $120$ congruence class mod $120$ ?2012-07-23
  • 0
    So I'm assuming this method works (working mod 720). Does it allow you to find the smallest number that can't be represented this way?2012-07-23
  • 6
    @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.2012-07-23
  • 2
    I got the same result [352,356,364,368] with this code: http://hpaste.org/720382012-07-23
  • 1
    @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$...2012-07-23
2

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}

  • 6
    He wants to use each number at most once2012-07-23
0

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.

  • 0
    I like this line of thought, but you can also multiply factorials together, so there'll be more than 2187 combinations.2014-02-28