Prove that if $n\ge16,$then $10\mid g(n),$where $g(n)$ is the largest LCM of partitions of $n$.
For more information,see http://oeis.org/A000793
Here is the list of $g(n)$ for $n>0,$ $g(15)=105,g(16)=140.$ $1, 2, 3, 4, 6, 6, 12, 15, 20, 30, 30, 60, 60, 84, 105, 140, 210, 210, 420, 420, 420, 420, 840, 840, 1260, 1260, 1540, 2310, 2520, 4620, 4620, 5460, 5460, 9240, 9240, 13860, \cdots$
If $a_1+a_2+\cdots +a_k=n,$ and LCM$(a_1,a_2,\cdots ,a_k)=g(n),$ then we need to prove that at least one of $a_i$ is even, and one of $a_i$ is divisible by 5.
PS:This is only my conjecture,maybe it's wrong,see http://oeis.org/A000793/b000793.txt
Thanks in advance!
I will first prove the claim by @Gerry Myerson in the comments: For every $m$, there exists $n_0$ such that $n>n_0$ implies $m \mid g(n)$. At the end, I show that $10 \nmid g(n) \Rightarrow n<1550$.
First, a trivial lemma:
Lemma 1: If $a_1, a_2, \ldots , a_k \geq 2$ are positive integers, then $a_1a_2 \ldots a_k \geq a_1+a_2+ \ldots +a_k$.
Proof: We proceed by induction on $k$. This is clearly true when $k=1$. When $k=2$, since $(a_1-1)(a_2-1) \geq 1$, we easily get $a_1a_2 \geq a_1+a_2$. Suppose that it holds for $k=i$. Then $a_1a_2 \ldots a_ia_{i+1} \geq (a_1+a_2+ \ldots +a_{i-1})+a_ia_{i+1}$ by the induction hypothesis. By the base case where $k=2$, we have $a_ia_{i+1} \geq a_i+a_{i+1}$, so we are done by induction.
Now, suppose that we have $n=x_1+x_2+ \ldots +x_t$, $lcm(x_1, x_2, \ldots, x_t)=g(n)$. If $x_i$ is neither $1$ nor a prime power for some $i$, then we may write $x_i=a_1a_2 \ldots a_k, k \geq 2$, where each $a_j$ is a prime power. By lemma $1$, we may then replace $x_i$ by $k+1$ terms: $a_1, a_2, \ldots , a_k$, and $x_i-(a_1+a_2+ \ldots +a_k)$. (The last term is non-existent if equality holds) This will not decrease the lcm of the numbers, so we may safely assume that all $x_i$ are prime powers (or 1).
For a prime $p$, define $f_p(n)=v_p(g(n))$. Clearly if $f_p(n) \geq 1$, then $p^{f_p(n)}$ must be one of the terms in the partition of $n$ with lcm $g(n)$. (We have already assumed that all terms are $1$, or prime powers)
We want to show that for any positive integer $m$, there are finitely many $n$ s.t. $m \nmid g(n)$. It clearly suffices to show this for $m$ a prime power. ($m=1$ is trivial)
Let $m=p^a$. Suppose that $m \nmid g(n)$. Then $f_p(n) \leq a-1$.
Consider any prime $q \not =p$. If $q \mid g(n)$, then $q^{f_q(n)}$ is a term in the partition. Define $b_q=\lceil \frac{\log{q}}{\log{p}} \rceil$. Then $p^{b_q}>q$.
If $p^{a-1+b_q}+q^{f_q(n)-1} \leq q^{f_q(n)}$, we may replace $q^{f_q(n)}$ by the $3$ terms $p^{a-1+b_q}$, $q^{f_q(n)-1}$, and $q^{f_q(n)}-(p^{a-1+b_q}+q^{f_q(n)-1})$. (The third term is non-existent if equality holds) Now, $v_p(lcm)$ is now equal to $a-1+b_q \geq a$, and $v_q(lcm)$ is at least $f_q(n)-1$. Since $p^{a-1+b_q}q^{f_q(n)-1}>p^{a-1}q^{f_q(n)} \geq p^{v_p(n)}q^{f_q(n)}$, the lcm of the partition has increased, so $g(n)$ is not the largest lcm, a contradiction.
Therefore $p^{a-1+b_q}+q^{f_q(n)-1}>q^{f_q(n)}$. Thus $p^aq \geq p^{a-1+b_q}>q^{f_q(n)}-q^{f_q(n)-1}=(q-1)q^{f_q(n)-1}$, so $f_q(n)<1+\frac{\log{(\frac{q}{q-1}p^a)}}{\log{q}}$.
If $q \nmid g(n)$, then $f_q(n)=0<1+\frac{\log{(\frac{q}{q-1}p^a)}}{\log{q}}$.
Thus if $p^a \nmid g(n)$, then $f_q(n)<1+\frac{\log{(\frac{q}{q-1}p^a)}}{\log{q}}$ for all primes $q \not =p$.
Note that $f_p(n)+1 \leq a<1+\frac{\log{(\frac{p}{p-1}p^a)}}{\log{p}}$.
We proceed to show that if $q$ is sufficiently large (in relation to $p, a$), then $p^a \nmid g(n) \Rightarrow q \nmid g(n)$.
We first prove $2$ lemmas:
Lemma 2: Let $S$ be a finite set of primes, and $q$ be a prime s.t. $q^2 \nmid g(n)$. If $\sum_{s \in S}{s^{f_s(n)+1}} \leq q<\prod_{s \in S}{s}$, then $q \nmid g(n)$.
Proof: If $q \mid g(n)$, then $f_q(n)=1$, so $q$ appears in the partition. We may clearly replace $q$ by the terms $s^{f_s(n)+1}, s \in S$ and $q-\sum_{s \in S}{s^{f_s(n)+1}}$. Since $\prod_{s \in S}{s^{f_s(n)+1}}>\prod_{s \in S}{s^{f_s(n)}}q$, the lcm of the parition has increased as a result, so we get a contradiction. Therefore $q \nmid g(n)$.
Lemma 3: Let $p_i$ denote the $i$th prime. Then for $i \geq 3$, we have $p_{i+1}^2+p_{i+2}^2+p_{i+3}^2<p_{i}p_{i+1}p_{i+2}$.
Proof: By Betrand's postulate, $p_{i+3} \leq 2p_{i+2} \leq 4p_{i+1}$, so $p_{i+1}^2+p_{i+2}^2+p_{i+3}^2<p_{i+1}p_{i+2}+2p_{i+1}p_{i+2}+8p_{i+1}p_{i+2} \leq p_ip_{i+1}p_{i+2}$ for $i \geq 4$. When $i=3$, we clearly have $7^2+11^2+13^2=339<385=5(7)(11)$.
Now, note that for prime $q>p^a$, we have $q-1 \geq p^a$, so $f_q(n)<1+\frac{\log{(\frac{q}{q-1}p^a)}}{\log{q}} \leq 2$. Thus $f_q(n) \leq 1$. Let $c=\max(\pi(p^a), 2) \geq 2$, and consider $q \geq p_{c+1}^2+p_{c+2}^2+p_{c+3}^2$. Let $d$ be the largest positive integer such that $q \geq p_d^2+p_{d+1}^2+p_{d+2}^2$. Clearly $d \geq c+1 \geq 3$, so by the maximality of $d$ and lemma $3$ we have $q<p_{d+1}^2+p_{d+2}^2+p_{d+3}^2<p_dp_{d+1}p_{d+2}$.
Since $q>p_{d+2}>p_{d+1}>p_d \geq p_{c+1}>p^a$, $f_{p_{d+2}}(n), f_{p_{d+1}}(n), f_{p_d}(n), f_q(n) \leq 1$. Therefore $p_d^{f_{p_d}(n)+1}+p_{d+1}^{f_{p_{d+1}}(n)+1}+p_{d+2}^{f_{p_{d+2}}(n)+1} \leq p_d^2+p_{d+1}^2+p_{d+2}^2 \leq q<p_dp_{d+1}p_{d+2}$, so by lemma $2$ we have $q \nmid g(n)$.
Therefore, $p^a \nmid g(n) \Rightarrow q \nmid g(n)$ for $q \geq p_{c+1}^2+p_{c+2}^2+p_{c+3}^2$.
Combining this with the previous bounds on $f_q(n)$, we get:
$$p^a \nmid g(n) \Rightarrow pg(n) \mid \prod_{q \text{prime} \atop q< p_{c+1}^2+p_{c+2}^2+p_{c+3}^2}{q^{\left \lfloor 1+\frac{\log{(\frac{q}{q-1}p^a)}}{\log{q}} \right \rfloor}}$$
This gives
$$g(n)<pg(n) \leq \prod_{q \text{prime} \atop q<p_{c+1}^2+p_{c+2}^2+p_{c+3}^2}{q^{\left \lfloor 1+\frac{\log{(\frac{q}{q-1}p^a)}}{\log{q}} \right \rfloor}}=\prod_{q \text{prime} \atop q \leq p^a}{q^{\left \lfloor 1+\frac{\log{(\frac{q}{q-1}p^a)}}{\log{q}} \right \rfloor}}\prod_{q \text{prime} \atop p^a<q<p_{c+1}^2+p_{c+2}^2+p_{c+3}^2}{q}$$
This clearly implies that
\begin{align} n<\sum_{q \text{prime} \atop q \leq p^a}{q^{\left \lfloor 1+\frac{\log{(\frac{q}{q-1}p^a)}}{\log{q}} \right \rfloor}}+\sum_{q \text{prime} \atop p^a<q<p_{c+1}^2+p_{c+2}^2+p_{c+3}^2}{q} & \leq \sum_{q \text{prime} \atop q \leq p^a}{(\frac{q^2}{q-1}p^a)}+\sum_{q \text{prime} \atop p^a<q<p_{c+1}^2+p_{c+2}^2+p_{c+3}^2}{q} \\ & \leq p^a\sum_{q \text{prime} \atop q \leq p^a}{(q+2)}+\sum_{q \text{prime} \atop p^a<q<p_{c+1}^2+p_{c+2}^2+p_{c+3}^2}{q} \end{align}
We have thus shown that for any positive integer $m$, there exists $n_0$ s.t. $n>n_0$ implies $m \mid g(n)$. In fact, the above bound is easily seen to be $O(m^4)$.
Application to $m=10$: We have that $$2 \nmid g(n) \Rightarrow n<2\sum_{q \text{prime} \atop q \leq 2}{(q+2)}+\sum_{q \text{prime} \atop 2<q<5^2+7^2+11^2}{q}=3837$$
$$5 \nmid g(n) \Rightarrow n<5\sum_{q \text{prime} \atop q \leq 5}{(q+2)}+\sum_{q \text{prime} \atop 5<q<7^2+11^2+13^2}{q}=10261$$
Thus $10 \nmid g(n) \Rightarrow n<10261$.
In fact, we can do much better with a simple refinement. Note that by the above results, $2 \nmid g(n) \Rightarrow q \nmid g(n)$ for $q \geq 5^2+7^2+11^2=195$. Observe that $f_2(n)=0$ and $f_p(n) \leq 1$ for $p \geq 3$. Consider $85 \leq q<195$, then since $$2^{f_2(n)+1}+3^{f_3(n)+1}+5^{f_5(n)+1}+7^{f_7(n)+1} \leq 2^1+3^2+5^2+7^2=85 \leq q<195<2(3)(5)(7)$$, we have by lemma $2$ ($f_q(n) \leq 1$) that $q \nmid g(n)$.
The same argument then gives $$2 \nmid g(n) \Rightarrow n<2\sum_{q \text{prime} \atop q \leq 2}{(q+2)}+\sum_{q \text{prime} \atop 2<q<85}{q}=880$$
Similarly, $5 \nmid g(n) \Rightarrow q \nmid g(n)$ for $q \geq 7^2+11^2+13^2=339$. Observe that $f_5(n)=0$ and $f_p(n) \leq 1$ for $p \geq 5$. Consider $175 \leq q<339$, then since $$5^{f_5(n)+1}+7^{f_7(n)+1}+11^{f_{11}(n)+1} \leq 5^1+7^2+11^2=175 \leq q<339<(5)(7)(11)$$, we have by lemma $2$ ($f_q(n) \leq 1$) that $q \nmid g(n)$.
Now $f_2(n)<\lfloor 1+\frac{\log{2(5)}}{\log{2}} \rfloor=5$ and $f_3(n)<\lfloor 1+\frac{\frac{3}{2}(5)}{\log{3}} \rfloor=3$. Thus $f_2(n) \leq 4, f_3(n) \leq 2$. Consider $113 \leq q<175$, then since $$2^{f_2(n)+1}+3^{f_3(n)+1}+5^{f_5(n)+1}+7^{f_7(n)+1} \leq 2^5+3^3+5+7^2=113 \leq q<175<2(3)(5)(7)$$, we have by lemma $2$ ($f_q(n) \leq 1$) that $q \nmid g(n)$.
The same argument then gives $$5 \nmid g(n) \Rightarrow n<5\sum_{q \text{prime} \atop q \leq 5}{(q+2)}+\sum_{q \text{prime} \atop 5<q<113}{q}=1550$$
Thus $10 \nmid g(n) \Rightarrow n<1550$. The remaining small cases can be easily checked with a computer.