Let $p_1, p_2, \ldots, p_{25}$ are primes which don’t exceed 2004. Find the largest integer $T$ such that every positive integer $\leq T$ can be expressed as sums of distinct divisors of $(p_1\cdot p_2 \cdot \ldots \cdot p_{25})^{2004}.$
Problem
Source: China Team Selection Test 2004, Day 2, Problem 2
Tags: LaTeX, number theory unsolved, number theory
14.10.2005 18:28
Please post your solutions. Use $\LaTeX$ please! Please omit jokes/smilies etc. Comments and generalizations are welcome. If you noticed that the comment has been discussed elsewhere, please provide a link. If you don't know the link(s) do NOT post and state that the problems has been discussed many times. If the provided solution is not complete, right or in $\LaTeX$-style I would be happy if you could (re-) post your/the solution in this thread again! At the end of your (re-)written solution post the links to those insufficient solutions as follows:
Happy Problem-Solving!
18.11.2005 09:42
here is my solution: Lemma If the sequence $1=a_1<a_2<...<a_n$ satisfies the condition: $a_{i+1}\le 1+a_1+...+a_i$ for any $1\le i\le n-1$ then $a_1+a_2+...+a_n$ is the largest number T such that every positive integer $\le T$ can be expressed as sums of distict terms of the sequence.
18.11.2005 09:58
here is my solution: Denote $M=(p_1p_2...p_{25})^{2004}$ Lemma 1 If the sequence $1=a_1<a_2<...<a_n$ satisfies the condition: $a_{i+1}\le 1+a_1+...+a_i$ for any $1\le i\le n-1$ then $a_1+a_2+...+a_n$ is the largest number $T$ such that every positive integer $\leq T$ can be expressed as sums of distict terms of the sequence. proof: The lemma is very easy. Lemma 2: If the sequence $1=a_1<a_2<...<a_n$ satisfies the condition: $a_{i+1}\le 2a_i$ for any $1\le i\le n-1$ then $a_1+a_2+...+a_n$ is the largest number $T$ such that every positive integer $\leq T$ can be expressed as sums of distict terms of the sequence proof: use lumma 1. Let $1=n_1<n_2<...<n_N$ are all divisors of $M$ If $min\{p_1;p_2;...;p_{25}\}$=2. We will show that $n_{i+1}\le 2n_i$ for any $1\le i\le N$. Suppose $p_1=2$. and $n_i=2^{t}p_2^{t_2}...p_{25}^{t_{25}}$. Case 1: if $t< 2003$ we have $n_i<2n_i=2^{t+1}p_2^{t_2}...p_{25}^{t_{25}}$ $\Rightarrow 2n_i|M$ $\Rightarrow n_{i+1}\le 2n_i$ Case 2: if $t=2004$. we have $min\{t_2;t_3;...;t_{25}\}\le 2003$. Suppose $t_2\le 2003$. Let x is the positive integer such that $2^x<p_2<2^{x+1}$ ( Always exist x) we have $n_i<2^{2004-x}p_2^{t_2+1}...p_{25}^{t_{25}}<2^{2005}p_2^{t_2}...p_{25}^{t_{25}}$ and $2^{2004-x}p_2^{t_2+1}...p_{25}^{t_{25}}| M \Rightarrow$ we have $n_{i+1}\le 2n_i$. Use lemma 2: We have $T=n_1+n_2+...+n_N=\frac{(p_1^{2005}-1)...(p_{25}^{2005}-1) }{(p_1-1)(p_2-1)...(p_{25}-1)}$. if $min\{p_1;..;p_{25}\}\ge 3$ then $M=1$. .
25.10.2016 18:21
Actually the rest part is simple just use induction on the number of primes.