Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Prove that for any $x \in \mathbb N$ such that $x<n!$ is the sum of at most $n$ distinct divisors of $n!$.

share|cite|improve this question
If only Goldbach conjecture was true. – Jayesh Badwaik Feb 20 '13 at 2:55
up vote 10 down vote accepted

Let $x = nq+r$, with $0 \leq r < n$. Note that $x < n!$ implies that $q < (n-1)!$. Now use induction on $q$.

share|cite|improve this answer
Works for me. Note that, as the initial case is 2! rather than 1!, this proves that $(n-1)$ divisors suffice. – Will Jagy Feb 20 '13 at 3:34
Great, may I ask if you had seen a similar problem before or how you figured it out. Thanks! – Carry on Smiling Feb 20 '13 at 3:56
@Khromonkey, I haven't seen this before. Induction seems to be a natural idea though. I guess that Robert Israel's attempt helped inspire this solution too. – user27126 Feb 20 '13 at 4:04
No, this doesn't work, either. Let $n=5, x=119$, then $q=23$ and $115$ doesn't divide $120$ – Ross Millikan Feb 20 '13 at 13:42
@Ross Millikan, $q = 23 < 4!$, and you want to cut 23 up into sum of divisors of 4! first. For example, 23 = 12 + 8 + 3, and 119 = 60 + 40 + 15 + 4. – user27126 Feb 20 '13 at 16:33

People do not seem to be going along with my comment. So this is CW, and directly from the answer by Sanchez.

For $n=2,$ we need only 1 divisor of $2!,$ as $1=1.$

For $n=3,$ we need only 2 divisors of $3!=6,$ as $1=1, 2=2,3=3,4=3+1,5=3+2.$

Induction hypothesis: for some $n \geq 2,$ we need at most $(n-1)$ distinct divisors of $n!$ to write any $1 \leq x < n!$ as a sum.

Induction step (Sanchez, above). Let $N = n+1.$ Let $1 \leq x < N! = (n+1)!$ Write $$ x = N q + r, \; \; \mbox{with} \; \; 0 \leq r < N. $$ Because $q < (N-1)! = n!,$ we need at most $(n-1) = (N-2)$ divisors of $n!$ to write $q$ as a sum. So $$ q = \sum_{i=1}^{n-1} d_i, $$ where each $d_i | n!$ Therefore each $Nd_i | N!$

At this stage, we have at most $N-2$ divisors of $N!$ What about $r?$ Well, $r < N,$ so it is automatically a factor of $N!$ So we have finished the decomposition as a sum with at most $(N-1)$ divisors of $N!,$ where $N=n+1.$

CONCLUSION: For all $N \geq 2,$ every integer $1 \leq x < N!$ can be written as the sum of (at most) $N-1$ distinct divisors of $N!$

SUGGESTION: try it for $N=4, \; \; N! = 24.$

NEVER MIND, do it myself. Aliquot divisors 1,2,3,4,6,8,12. $$1=1,2=2,3=3,4=4,5=4+1,6=4+2,7=4+3, 8=8,9=8+1,10=8+2, $$ $$11=8+3, 12= 12, 13 = 12+1, 14 = 12+2, 15 = 12+3, 16 = 12+4,$$ $$17=12+4+1, 18=12+6,19=12+4+3,20=12+8,$$ $$21=12+8+1,22=12+8+2,23 = 12+8+3. $$

share|cite|improve this answer

Hint: Note that $x = m (n-1)! + r$ where $0 \le m < n$ and $0 \le r < (n-1)!$. Use induction.

EDIT: Oops, this is wrong: as Steven Stadnicki noted, $m (n-1)!$ doesn't necessarily divide $n!$.

share|cite|improve this answer
$m(n-1)!$ isn't necessarily a divisor of $n!$, is it? – Steven Stadnicki Aug 2 '12 at 19:04
@RobertIsrael Then what is the correct answer? – Carry on Smiling Sep 22 '12 at 16:55
I don't know. I believe it is true, and probably not too hard to prove, that for any $x \in \{1,\ldots,n!\}$ there is always a divisor $y$ of $n!$ with $x/2 \le y \le x$. Then we can take a greedy approach: let $y_1$ be the greatest divisor of $n!$ less than $x$, and replace $x$ by $x - y_1$. This will result in writing $x$ as a sum of distinct divisors of $n!$, but it's not clear to me that there will be at most $n$ of them: the easy bound would be about $\log_2(n!) \approx n \log_2(n)$. – Robert Israel Sep 23 '12 at 18:07
Can you edit or delete your answer please?? If it is wrong why is it here?? – Carry on Smiling Feb 19 '13 at 22:55
@Khromonkey, it is probably here because it is a reasonable direction to take, yet involves an error that has been identified. As such, it is educational for others. Meanwhile, noting that you say you are a high-school student, I cannot see how this is an ordinary homework problem, so I am asking why you think your assertion is true and where you got the problem. – Will Jagy Feb 19 '13 at 23:35

Not quite there, but a start: As suggested in Wikipedia on practical numbers we will use the greedy algorithm. First pull out $n!/2$ if that is possible, then $n!/3$, then $n!/4$ and so on, stopping when the remainder is less than or equal to $n$ and skipping denominators that don't divide $n!$. If $n$ and $x$ are very large, the denominators we use will follow Sylvester's sequence: $2, 3, 7, 43, 1807, 3263443, 10650056950807,\ldots$ which is given by $a(0)=2, a(n+1)=a(n)^2-a(n)+1$. To use induction, we need to find a sequence of $m$ denominators that reduce $n!-1$ to something less than $n$. For $n$ in the range $5-6$ we can use $2,3,8,30$. For $7$ we can use $2,3,7,45$, for $8-10$ we can use $2,3,7,45,640$. Then $44$ becomes available at $11$. It "obviously" works, but I can't prove it.

share|cite|improve this answer

A natural number $m$ is called practical if all smaller natural numbers can be represented as sum of distinct divisors of $m$.

The problem asks to establish that factorial numbers are practical. The wikipedia article on practical numbers even gives an algorithm, implemented in Mathematica:

dec2[0, n_] := {};
dec2[1, n_] := {1};
dec2[x_, n_] := Module[{fcts, pa, q, r, quo},
  fcts = Last[FactorInteger[n]]; pa = Power @@ fcts;
  q = Min[Quotient[x, pa], DivisorSigma[1, quo = Quotient[n, pa]]];
  Join[dec2[x - q pa, Quotient[n, First[fcts]] ], dec2[q, quo] pa]

dec[x_, n_] := Block[{$RecursionLimit = Infinity}, dec2[x, n!]]


In[32]:= dec[17, 4]

Out[32]= {2, 3, 12}

In[33]:= dec[137, 6]

Out[33]= {2, 45, 90}

It remains to be proven that the decomposition length of $x < n!$ will be less of equal than $n$.

share|cite|improve this answer
That is the question. Can you make this answer answer it? – Carry on Smiling Feb 19 '13 at 22:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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