Prove that for any $x \in \mathbb N$ such that $x
Prove that for any $x \in \mathbb N$ such that $x is the sum of at most $n$ distinct divisors of $n!$
-
0http://meta.math.stackexchange.com/questions/1803/how-to-ask-a-homework-question – 2012-08-02
-
0If only Goldbach conjecture was true. – 2013-02-20
5 Answers
Let $x = nq+r$, with $0 \leq r < n$. Note that $x < n!$ implies that $q < (n-1)!$. Now use induction on $q$.
-
0Works for me. Note that, as the initial case is 2! rather than 1!, this proves that $(n-1)$ divisors suffice. – 2013-02-20
-
0Great, may I ask if you had seen a similar problem before or how you figured it out. Thanks! – 2013-02-20
-
0@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. – 2013-02-20
-
0No, this doesn't work, either. Let $n=5, x=119$, then $q=23$ and $115$ doesn't divide $120$ – 2013-02-20
-
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. – 2013-02-20
-
0I see. Thanks.. – 2013-02-20
-
0@WillJagy Or rather: As $r
the summands are divisors of $(n-1)!$, i.e. $1\le x<(n+1)!$ implies that $x$ is the sum of at most $n$ distinct divisors of $n!$. – 2013-02-23 -
0@HagenvonEitzen, what you say may be true, but it doesn't follow from my proof, since for $1 \leq x < (n+1)!$ I need to multiply $n+1$ to the summands of $q$, making it possible that it doesn't divide $n!$. – 2013-02-23
-
0@HagenvonEitzen, I posted my argument as a separate, and CW answer, just now. – 2013-02-23
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. $$
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!$.
-
5$m(n-1)!$ isn't necessarily a divisor of $n!$, is it? – 2012-08-02
-
0@RobertIsrael Then what is the correct answer? – 2012-09-22
-
0I 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)$. – 2012-09-23
-
0Can you edit or delete your answer please?? If it is wrong why is it here?? – 2013-02-19
-
0@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. – 2013-02-19
-
0I got it as homework on a math competition training camp – 2013-02-19
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.
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$.
-
1That is the question. Can you make this answer answer it? – 2013-02-19