Let $\sigma(x)$ denote the sum of divisors of natural number $x$, including $1$ and $x$. For every $n\in \mathbb{N}$ define $f(n)$ as number of natural numbers $m, m\leq n$, for which $\sigma(m)$ is odd number. Prove that there are infinitely many natural numbers $n$, such that $f(n)|n$.
Problem
Source: Serbia Additional TST 2012, Problem 2
Tags: floor function, limit, inequalities, number theory proposed, number theory
19.05.2012 17:28
This might help: $\sigma(n)$ is odd if and only if the power of every odd prime dividing $n$ is even. See the attachment for the proof. Peace. Faustus. EDIT: Added the proof.
Attachments:
19.05.2012 20:45
* $\sigma(n)$ is odd if and only if the power of every odd prime dividing $n$ is even, so the number $m$ is of form $x^2, 2x^2.$ Hence $ f(n)=\lfloor{\sqrt{n} \rfloor}+\lfloor{\sqrt{\frac{n}{2}} \rfloor}.$ Now just take $n=2x^2+1=y^2$ until $n=y^2+2y$ and for at least one $n$ $ f(n)=\lfloor{\sqrt{n} \rfloor}+\lfloor{\sqrt{\frac{n}{2}} \rfloor}= y+x|n.$
20.05.2012 22:23
Djile wrote: Let $\sigma(x)$ denote the sum of divisors of natural number $x$, including $1$ and $x$. For every $n\in \mathbb{N}$ define $f(n)$ as number of natural numbers $m, m\leq n$, for which $\sigma(m)$ is odd number. Prove that there are infinitely many natural numbers $n$, such that $f(n)|n$. Let $d$ be an arbitrary divisor of $n$. Then, \[\sigma(n)=\sum_{d|n}d\] Thus, if the number of divisors of $n$ is odd for odd $n$, so is $\sigma(n)$. Also, since perfect squares have an odd number of divisors and even divisors does not contribute to the parity of $\sigma(n)$, we can conclude that $\sigma(2x^2)$ and $\sigma(x^2)$ have odd parity. Thus, the number of numbers having odd sum of divisors less than $n$ is $f(n)=\lfloor \sqrt n\rfloor+\lfloor\sqrt{\frac n2}\rfloor$. Now, we need $f(n)|n$. Let $\lfloor \sqrt n\rfloor=x$ or $x^2\le n\le (x+1)^2$. Now, we need a divisor $d$ of $n$ greater than $x$ for which $d=x+\lfloor\sqrt{\frac n2}\rfloor$. Now, since we are given the freedom of choosing $n$, we can have an infinite $n$ certainly. For example, the one SCP gave above.
26.05.2012 20:36
A funny fact about this problem is that we don't need exact formula for $f(n)$. $\frac{n}{f(n)} \rightarrow \infty$ is sufficient. One can take, for instance, $g(n)=1234 f(n)-n$ and $g(1)>0$ and for sufficiently large $n$ have $g(n)<0$, but $g(n+1) +1 \geq g(n)$, so there exists $k$ such that $g(k)=0 \Rightarrow 1234f(k)=k$ .
26.05.2012 22:02
Indeed, clearly $(f(n))_{n\geq 1}$ is non-decreasing (with $f(1) = 1$, $f(2) = 2$, $f(3) = 2$, etc.). And indeed, as defined, $f(n)$ counts the numbers of the form $2^k\ell^2$ ($k\geq 0$, $\ell \geq 1$) between $1$ and $n$, thus $\lim_{n\to \infty} \dfrac {f(n)} {n} = 0$. By a beautiful lemma, if a sequence $(a_n)_{n\geq 1}$ made of positive integers is non-decreasing, and $\lim_{n\to \infty} \dfrac {a_n} {n} = 0$, then the sequence $\left (\dfrac {n} {a_n} \right )_{n\geq 1}$ contains infinitely many positive integers; more than that, it contains all positive integers! See http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1373775&sid=5aa13734ddd9d4470ad5b047ad8bf62f#p1373775, Problem 1 at the 2008 Stars of Mathematics competition, for another application of it.
31.05.2012 01:28
I have been asked for a proof of this lemma, so here it is. Proof. Let $m$ be a positive integer. We have $\dfrac {1} {a_1} \leq 1 \leq m \leq \dfrac {N} {a_N}$ for some positive integer $N$, since $\displaystyle \lim_{n\to \infty} \dfrac {n} {a_n} = \infty$. Let $n$ be the least integer from $\{1,2,\ldots,N\}$ such that $m \leq \dfrac {n} {a_n}$. Assume strict inequality occurs. Since then $\dfrac {n-1} {a_{n-1}} < m$, we have $n - 1 < ma_{n-1} \leq ma_n < n$, the sequence $(a_n)_{n\geq 1}$ being non-decreasing. Therefore $n - 1 \leq ma_{n-1} - 1 \leq ma_n - 1 \leq n - 2$, absurd. Therefore we have equality, i.e. $m = \dfrac {n} {a_n}$.
31.05.2012 21:04
Bah, I've already posted a sketch of proof of this lemma in my previous post .
25.09.2019 21:33
I think this was inspired by the same version replaced $f(n)$ by $\pi (n)$.