Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
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
add comment

6 Answers 6

up vote 10 down vote accepted
+50

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

share|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! –  Bananarama 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
2  
@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
show 4 more comments

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|improve this answer
add comment

is very simple logic that, n! will have only atmost 2n distinct divisors and
they are n!,(n!/2),(n!/3)...(n!/n) and1,2,..n
your question is wrong because take 8! as case
take x as sum of 7 distinct divisors say 1,2,3,4,5,6,7=28
but still x less than n! wich contradicts x can be only sum of atmost 6 distinct divisors of n! so that x could be less than n!.

share|improve this answer
4  
Refuting the claim of $n!$ having only at most $2n$ distinct divisors: $3!$ has 4 divisors, $4!$ has 8, $5!$ has 16 and $6!$ has 30. –  Sasha Feb 23 '13 at 17:45
add comment

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|improve this answer
add comment

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|improve this answer
5  
$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? –  Bananarama 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?? –  Bananarama 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
show 1 more comment

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

share|improve this answer
1  
That is the question. Can you make this answer answer it? –  Bananarama Feb 19 '13 at 22:54
add comment

Your Answer

 
discard

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.