I think this is a bash but I couldn't complete a proper proof (Note : I couldn't complete a proof in one hour since this was posted)

Nice but not that difficult. We want to prove that for each N, if L(N)≤0 then K(N)≤0 and we do so with the following claim. For every N, consider A={1,2,3,...,N}. Define A_i for every natural i as follows: if k an element of A let K=p1^a1*p2^a2*...*p_r^a_r. Now k belongs to A_i if a1+a2+...+a_r=i. Finally, we claim that |A_i|>|A_i+1|. This claim is not hard to prove once you understand what it actually means. The reader should now make sure he understand the claim and why it is trivial. Now we show what we were asked for. Define A and A1,A2,... as defined in the claim. Now we can say that our goal is to prove that the sum |A2|+|A3|+...≥0 which is a direct consequence of our claim hence we are done. Sorry for not getting into details but those details are rather trivial and I highly belive the reader can figure them out on his own

Sorry if i'm dumb but @above I don't think your claim is trivial. In fact L(n) can be positive for some n and with that n, it implies we can not have A(i)>A(i+1) for all i, do you use the condition "L(n)<=0" while proving your claim?

Mikeglicker wrote: Nice but not that difficult. We want to prove that for each N, if L(N)≤0 then K(N)≤0 and we do so with the following claim. For every N, consider A={1,2,3,...,N}. Define A_i for every natural i as follows: if k an element of A let K=$p_1^{a_1}*p_2^{a_2}*...*p_r^{a_r}.$ Now k belongs to A_i if $a1+a2+...+a_r=i.$ Finally, we claim that $|A_i|>|A_{i+1}|.$ This claim is not hard to prove once you understand what it actually means. The reader should now make sure he understand the claim and why it is trivial. Now we show what we were asked for. Define A and A1,A2,... as defined in the claim. Now we can say that our goal is to prove that the sum |A2|-|A3|+...≥0 which is a direct consequence of our claim hence we are done. Sorry for not getting into details but those details are rather trivial and I highly belive the reader can figure them out on his own I have tried this,... and Im not sure if $|A_2|\ge |A_3|$ is true. Even if it is, it is the key of the problem and not "trivial".

Right, it isn't that trivial.... I just thought to myself that this claim is easy and didn't bother with details, but it actually quite hard. I will try proving it.

Mikeglicker wrote: Nice but not that difficult. We want to prove that for each N, if L(N)≤0 then K(N)≤0 and we do so with the following claim. For every N, consider A={1,2,3,...,N}. Define A_i for every natural i as follows: if k an element of A let K=p1^a1*p2^a2*...*p_r^a_r. Now k belongs to A_i if a1+a2+...+a_r=i. Finally, we claim that |A_i|>|A_i+1|. This claim is not hard to prove once you understand what it actually means. The reader should now make sure he understand the claim and why it is trivial. Now we show what we were asked for. Define A and A1,A2,... as defined in the claim. Now we can say that our goal is to prove that the sum |A2|+|A3|+...≥0 which is a direct consequence of our claim hence we are done. Sorry for not getting into details but those details are rather trivial and I highly believe the reader can figure them out on his own Unfortunately I don't think $|A_i| \geq |A_{i+1}|$ is true in general. I wrote a program and found the first counterexample for $i=1$ is $N=26$ where $|A_1|=9 < 10 = |A_2|$ and for $i=2$ is $N=15526$ where $|A_2| = 3986 < 3987 = |A_3|$. Interestingly, actually all $15526 \leq i \leq 10^9$ satisfy $|A_2| < |A_3|$ , other than $i = 15529$ where $|A_2| = |A_3|$.

Any solution?

It seems really hard...

ducktility wrote:

I think this is a bash but I couldn't complete a proper proof (Note : I couldn't complete a proof in one hour since this was posted) Solution: Run a program and make sure $K(n)>0$ for all $n\le 906150256$. That is clearly cheating but I think this might be unsolvable.

Does anyone have the offical solution? Or at least a hint

My in contest solutions uses induction to prove there exists more prime numbers and composite numbers with odd number of factors than composite numbers with even number of factors in some bound for $(a+1,b)$ if $\lambda(a+1)=-1$, and similarly for $\lambda(a+1)=1$, except the other way around.

Yay, this is my first problem ever on a contest!

@above could you give me a bigger hint ? i tried but still got nowhere

Bigger hint: Obviously, we need only to show $K(n) \ge 0$. To do this, as I said, divide all composite numbers from $1$ to $n$ depending on their least prime divisor, then in each such group prove that the sum of $\lambda$ from numbers of this group is $\ge 0$ by dividing numbers in each group by their prime divisor, and try dealing using induction on the numbers which remain.

Mikeglicker wrote: Nice but not that difficult. We want to prove that for each N, if L(N)≤0 then K(N)≤0 and we do so with the following claim. For every N, consider A={1,2,3,...,N}. Define A_i for every natural i as follows: if k an element of A let K=p1^a1*p2^a2*...*p_r^a_r. Now k belongs to A_i if a1+a2+...+a_r=i. Finally, we claim that |A_i|>|A_i+1|. This claim is not hard to prove once you understand what it actually means. The reader should now make sure he understand the claim and why it is trivial. Now we show what we were asked for. Define A and A1,A2,... as defined in the claim. Now we can say that our goal is to prove that the sum |A2|+|A3|+...≥0 which is a direct consequence of our claim hence we are done. Sorry for not getting into details but those details are rather trivial and I highly belive the reader can figure them out on his own That's pretty much how I solved the problem, but I think there's a more intuitive way to present this. Instead of using the power form of the prime factorisation, divide it in the form of prime factors. So 20 = 5 * 2 * 2 and not 5 * 2^2. Now we can note that 20 has 3 Factors in this definition. Let A_n be the number of numbers less than some SUFFICIENTLY LARGE upper limit n (at least n<=100). If we prove that {A_2+A_4+A_6+...}=A_even > A_odd = {A_3+A_5+A_7+...}. That is very much intuitive as Mikeglicker says. Adding more factors causes numbers to become larger, and so fewer of them are < n. Thus, A_1>A_2>A_3>A_4>... Hence A_even>A_odd. L(n) may not always be <0 since A_1 or the number of prime numbers<n tips the scale in many situations. However, with K(n), that does not happen. Mathfun5's computation seems to support this pretty much. Hope the explanation is clear. I am not in the habit of using mathematical notation to concisely express the ideas, but nevertheless, it should be understandable.

mshtand1 wrote: Bigger hint: Obviously, we need only to show $K(n) \ge 0$. To do this, as I said, divide all composite numbers from $1$ to $n$ depending on their least prime divisor, then in each such group prove that the sum of $\lambda$ from numbers of this group is $\ge 0$ by dividing numbers in each group by their prime divisor, and try dealing using induction on the numbers which remain. Tell me if I am wrong.Do you mean to say the following: We group the composite numbers upto $n$ the way you described.Then, say in the group of prime $p_i$ the numbers are $p_i*2,\cdots ,p_i*\lfloor \frac{n}{p_i} \rfloor$. Since, $L(\lfloor\frac{n}{p_i}\rfloor) \le 0$.Then the sum of $\lambda (x)$ where $x$ belongs to this group will be $\ge 0$ or something like that.

yayitsme wrote: mshtand1 wrote: Bigger hint: Obviously, we need only to show $K(n) \ge 0$. To do this, as I said, divide all composite numbers from $1$ to $n$ depending on their least prime divisor, then in each such group prove that the sum of $\lambda$ from numbers of this group is $\ge 0$ by dividing numbers in each group by their prime divisor, and try dealing using induction on the numbers which remain. Tell me if I am wrong.Do you mean to say the following: We group the composite numbers upto $n$ the way you described.Then, say in the group of prime $p_i$ the numbers are $p_i*2,\cdots ,p_i*\lfloor \frac{n}{p_i} \rfloor$. Since, $L(\lfloor\frac{n}{p_i}\rfloor) \le 0$.Then the sum of $\lambda (x)$ where $x$ belongs to this group will be $\ge 0$ or something like that. No, you won't have in each group the numbers as you said, because in such case we would count $\lambda$ from some numbers several times. Actually, in group with the smallest prime divisor $p_i$ will be the numbers $p_i \cdot x_1, p_i \cdot x_2, ..., p_i \cdot x_k$, where $x_1, x_2, ..., x_k$ are numbers from the interval $[2; n]$, which aren't divisible by none of the first $i$ primes $p_1, p_2, ..., p_i$. And after this you are on the right way.

Let $C$ denote the set of all composite numbers from $1$ to $n$, and $s(x)$ denote the smallest prime divisor of $x$. Furthermore, let $p_1, p_2, \cdots$ denote the set of all primes $p_i$ in increasing order, so $p_1=2, p_2=3,$ etc. Then, dividing all composite numbers from $1$ to $n$ based on their smallest prime divisor, and using $\lambda(x)$ is a completely multiplicative function (i.e. $\lambda(ab) = \lambda(a) \lambda (b)$ for all $a,b \in \mathbb{N}$), we have \begin{align*} K(n) = \sum_{x \in C}^n \lambda(x) &= \sum_{i=1} \sum_{y > 1, s(y) \geq p_i}^{\lfloor n/p_i \rfloor} \lambda(p_i) \lambda(y) \\ &= - \sum_{i=1} \sum_{y > 1, p_j\nmid y \forall 1\leq j < i}^{\lfloor n/p_i \rfloor} \lambda(y) \end{align*}So it suffices to show that $\sum_{y > 1, p_j\nmid y \forall 1\leq j < i}^{\lfloor n/p_i \rfloor} \lambda(y) \leq 0$ for all $i$. Let $f(i, A) = \sum_{y > 1, p_j\nmid y \forall 1\leq j < i}^A \lambda(y)$. Claim: $f(i, A) \leq 0$ for all $i,A.$ Moreover, $f(i, A) \leq -1$ if $A \geq p_i$ (i.e. there is at least one summand). Proof: We proceed by induction on $i:$ For $i=1:$ If $A = 1$ then $f(1,A) = 0,$ and if $A \geq p_1 = 2$ then $f(1, A) = L(A) - 1 \leq -1$, since $L(x) \leq 0$ for all $2 \leq x \leq n.$ Now suppose the claim is true for $i=k$, and we wish to show the claim is true for $i=k+1$. We proceed by cases on $A$: Case 1: $A < p_{k+1}$ Then there are no summands in $f(k+1,A)$, so the sum is trivially $0$. Case 2: $p_{k+1} \leq A < p_{k+1}^2$ Then, all summands of $f(k+1,A)$ are primes, because the smallest composite summand for $i=k+1$ is $p_{k+1}^2 > A$ (note that $1$ is never a summand by definition). So $f(k+1,A) = -s$, where $s$ is the number of summands. Since there is at least one summand $($namely $p_{k+1}), f(k+1,A) \leq -1.$ Case 3: $ A \geq p_{k+1}^2$ Then $A \geq p_k^2 \Rightarrow \frac{A}{p_k} \geq p_k \Rightarrow \lfloor A/p_k \rfloor \geq p_k \Rightarrow f(k,\lfloor A/p_k \rfloor) \leq -1.$ Also $A \geq p_k \Rightarrow f(k,A) \leq -1$. Now we find that \begin{align*} f(k+1, A) = \sum_{y > 1, p_j\nmid y \forall 1\leq j < k+1}^A \lambda(y) &= f(k, A) - \sum_{y > 1, p_j\nmid y \forall 1\leq j < k, p_k \mid y}^A \lambda(y) \\ &= f(k, A) - \sum_{z = 1, p_j\nmid y \forall 1\leq j < k}^{\lfloor A/p_k \rfloor} \lambda(p_k) \lambda(z) \\ &= f(k, A) + \sum_{z = 1, p_j\nmid y \forall 1\leq j < k}^{\lfloor A/p_k \rfloor} \lambda(z) \\ &= f(k, A) + f(k, \lfloor A/p_k \rfloor) + 1\\ &\leq -1 -1 +1 \leq -1 \end{align*}which finishes the inductive step and thus the claim. $\blacksquare$ Finally, by taking $A = \lfloor n/p_i \rfloor,$ we have $\sum_{y > 1, p_j\nmid y \forall 1\leq j < i}^{\lfloor n/p_i \rfloor} \lambda(y) = f(i, \lfloor n/p_i \rfloor) \leq 0$ for all $i$, finishing the proof.

mathfun5 wrote:

Actually this also allows the claim to be strengthened to $K(n) \geq \pi(\sqrt{n})$

Can anyone post the official solution

Clearly we see here that the given function is in fact lioville function whose property can be very easily applied here to give direct solution

Can you post the official solution?

Official solution: Firstly, note that for any number $n$ and for any prime $p$, $ \lambda (np) = - \lambda (n)$. Let $p_1 = 2 < p_2 <... < p_k < N$ be all primes up to $N$. We will show the following lemma: Claim. Let $L_i(n)$ be the sum of $\lambda (x)$ over all integers from 1 to $n$ not divisible by any of $p_1, p_2, . . . , p_i$. Then for any $p_{i+1} \le n \le N, L_i(n) \le 0$. Proof. By induction on $i$. This is true for $i = 0$ from the statement. Suppose that this is true for some $k$. Let’s prove this for $k + 1$. Consider any $n$ with $p_{k+2} \le n \le N$. Note that $L_{k+1}(n) = L_k(n) - ( - L_k(\dfrac{n}{p_{k+1}})) = L_k(n) + L_k(\dfrac{n}{p_{k+1}})$: the sum of $\lambda (x)$ over $x$ coprime with $p_1, p_2, . . . , p_{k+1}$ is equal to the sum of $\lambda (x)$ over $x$ coprime with $p_1, p_2, . . . , p_k$ minus the sum of $\lambda (x)$ over numbers coprime with $p_1, p_2, . . . , p_k$ but divisible by $p_{k+1}$. The last term is precisely $ - L_k(\dfrac{n}{p_{k+1}})$. Now, if $n \ge p_{k+1}^2$, then we get $L_{k+1}(n) = L_k(n) + L_k(\dfrac{n}{p_{k+1}}) \le 0 + 0 = 0$ straight away. Otherwise, if number is coprime with $p_1, p_2, . . . , p_{k+1}$, and is less then $p_{k+1}^2$, it has to be prime, so $L_{k+1}(n) = 1 - $ number of primes between $p_{k+2}$ and $n$, so $L_{k+1}(n) \le 0$ in this case too. Lemma is proved. Now, let’s use it to prove our statement. Note that $K(n) = \sum\limits_{p_i \le n} - (L_{i-1}(\dfrac{n}{p_i}) - 1)$. Indeed, we just divide composite numbers into groups by their smallest prime divisors, the sum of $\lambda (x)$ over composite $x$ whose smallest prime divisor is $p_i$ is $ - (L_{i-1}(\dfrac{n}{p_i} - 1)$ as they are just numbers from 1 to $\dfrac{n}{p_i}$ coprime with $p_1, p_2, . . . , p_{i-1}$, multiplied by $p_i$. −1 comes as we exclude $p_i$. Every term in this sum is nonnegative: $L_i(x) \le 1$ for any $i, x \le N$. Indeed, if $x \ge p_{i+1}$, by lemma we have $L_i(x) \le 0$, else we just have $L_i(x) = \lambda (1) = 1$. Therefore, the entire sum is nonnegative, $Q.E.D.$