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

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

-
What have you tried? –  Matthew Conroy Aug 2 '12 at 18:07
If only Goldbach conjecture was true. –  Jayesh Badwaik Feb 20 '13 at 2:55

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

-
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! –  dREaM 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

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

-
$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? –  dREaM 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?? –  dREaM 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

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!]]  Example: 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$. - That is the question. Can you make this answer answer it? – dREaM Feb 19 '13 at 22:54 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. - 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.$$

-