For integers $n>1$, define $f(n)$ to be the sum of all postive divisors of $n$ that are less than $n$. Prove that for any positive integer $k$, there exists a positive integer $n>1$ such that $n<f(n)<f^2(n)<\cdots<f^k(n)$, where $f^i(n)=f(f^{i-1}(n))$ for $i>1$ and $f^1(n)=f(n)$.
Problem
Source:
Tags: number theory unsolved, number theory
20.07.2011 19:25
20.07.2011 22:20
Maybe in a similar trend of ideas with http://www.artofproblemsolving.com/Forum/viewtopic.php?f=57&t=417477&p=2353157&hilit=almost#p2353157 ...
25.05.2014 18:38
@mahanmath, can you post a detailed proof? Thanks
11.02.2016 02:08
bump. Does anyone have a solution?
11.02.2016 05:23
I will prove this by induction on k. At first we define S(n) to be the sum of all divisors of n,k=1,choose n=6t,gcd(6,t)=1,easy to see f(n)=S(6t)-6t=S(6)S(t)-6t=12S(t)-6t>6t. for , k,assume there exists, n=u_{k}*t,gcd(u_k,t)=1.for k+1,choose a prime p which does not divide u_k,let u_{k+1} be p^{l-1}u_k.Here p,t satisfy S(n)=S(p^{l-1})S(u_k)S(t),then S(n) is divided by S(p^{l-1}),f(n)+p^{l-1}u_kt is divided by $(u_k)^2.So we can express f(n) in the form w*u_k,also the two are coprime. Then by induction hypothesis,done.
25.02.2018 16:22
I don't have any idea how the solution above works (or if it even works), but here's my solution. We denote the number of divisors of $n$ by $\sigma(n)$, so $f(n) = \sigma(n) - n$ for all $n$. (I might also have $d(n)$ by accident, instead of $\sigma(n)$, but they mean the same thing.) Lemma 1. If $n = 6k$ for some $k$, $gcd(k, 6) = 1$, $k > 1$, then $n < f(n)$. Proof We have $\sigma(n) = \sigma(6) \sigma(k) = 12\sigma(k) > 12k = 2n$, so $f(n) = \sigma(n) - n > n$. Lemma 2. If $n$ is an integer which has a prime divisor $p$ such that $p^2$ does not divide $n$, and $p \equiv 2 \ (mod \ 3)$, then $\sigma(n)$ is divisible by $3$. Proof Let $n = pm$, $gcd(p, m) = 1$. Now, $\sigma(n) = \sigma(p) \sigma(m) = (p+1) \sigma(m)$, and $p+1$ is divisible by $3$. Now, we will choose $n = 6p_1p_2 \ldots p_k \cdot a_0$, where $p_i$ are distinct prime numbers greater than $3$, and $gcd(6p_1p_2 \ldots p_k, a_0) = 1$. We choose $p_i$ in a following way: $p_1 \equiv 2 \ (mod \ 3)$. $p_{i+1} \equiv -1 \ (mod \ p_i^2)$ for all $i \geq 1$. This choice is possible due to Dirichlet. My claim is that $f^t(n)$ is of the form $6p_1p_2 \ldots p_{k - t} a_t$, where $gcd(6p_1p_2\ldots p_{k-t}, a_t) = 1$ whenever $t \leq k$. The proof of this claim is done by induction. $t = 0$ is true by definition (if you are not happy with this, you can prove the claim for $t = 1$ in an exactly same manner as the induction step). Now for the induction step, we assume the claim is true for $t$, and prove it for $t + 1$. $f^{t+1}(n) = f(f^t(n)) = f(6p_1p_2 \ldots p_{k-t} \cdot a_t )= 12\sigma(p_1p_2 \ldots p_{k-t}a_t) - 6p_1p_2 \ldots p_{k-t}a_t = 6(2\sigma(p_1p_2 \ldots p_{k-t}a_t) - p_1p_2 \ldots p_{k-t}a_t) = 6a_{t+1}$. What we have to prove now is that $a_{t+1}$ isn't divisible by $2$ or $3$, and is divisible by $p_i$ but not $p_i^2$ for all $i$. It's easy to see that $a_{t+1}$ is odd, as $p_1p_2\ldots p_{k-t}a_t$ is odd. $a_{t+1}$ also isn't divisible by $3$, as we can apply lemma 2 for the number $p_1p_2\ldots p_{k-t}a_t$ (with the prime divisor $p_1$) to see that $\sigma(p_1p_2\ldots p_{k-t}a_t)$ is divisible by $3$. As $p_1p_2\ldots p_{k-t}a_t$ isn't divisible by $3$, $a_{t+1}$ isn't either. Now, I will prove that $p_i^2$ divides $\sigma(p_1p_2\ldots p_{k-t}a_t)$ for all $1 \leq i < t$. If we look at the prime number $p_{i + 1}$, which is relatively prime to the other factors of the number $p_1p_2\ldots p_{k-t}a_t$, we have $\sigma(p_{i+1}) = p_{i+1} + 1 \equiv 0 \ (mod \ p_i^2)$, due to the choice of $p_i$. As $p_i^2$ divides $\sigma(p_1p_2\ldots p_{k-t}a_t)$, but does not divide $p_1p_2\ldots p_{k-t}a_t$, so $p_i^2$ does not divide $a_{t+1}$. However, $p_i$ divides. The claim I made before is therefore true. Thus, $f^t(n)$ is always of the form $6k$, where $gcd(6, k) = 1$, whenever $t \leq k$. By lemma 1, $f^{t+1}(n) > f^t(n)$ for all $t \leq k$.
22.07.2018 12:31
Really nice problem. But isn't it way too easy for China P3? The main idea is the following general lemma. Lemma : Let $\{p_1, p_2, ..., p_t\}$ be a finite set of primes. Then for any integer $k\geqslant 0$, there exists integer $n>1$ such that $$\nu_{p_i}(f^j(n)) = 1\text{ for every } i=1,2,..,t\text{ and } j =0,1,2,...,k.$$Proof : We induct on $k$, with the obvious base case $k=0$. Now we prove this for $k$ assuming the $k-1$ case. By Dirichlet, pick primes $q_1, q_2,...,q_t$ such that $q_i\equiv -1\pmod{p_i^2}$. By the induction hypothesis on $\{p_1,p_2,...,p_t,q_1,q_2,...,q_t\}$, there exists integer $n>1$ such that $$\nu_{p_i}(f^j(n)) =\nu_{q_i}(f^j(n))= 1\text{ for every } i=1,2,..,t\text{ and } j =0,1,2,...,k-1.$$But this implies that $p_i^2\mid\sigma(f^{k-1}(n))$ so $\nu_{p_i}(f^k(n)) = \nu_{p_i}(f^{k-1}(n)) = 1$, implying the conclusion. Back to the main problem Apply this lemma for $\{2,3\}$, there exists integer $n>1$ such that $$\nu_2(f^i(n)) = \nu_3(f^i(n))=1 \text{ for every } i =0,1,2,...,k.$$Now it suffices to prove that $f^i(n)$ is abundant for $i=0,1,2,...,k$. Let $r = f^i(n)$ and $r=6s$ where $\gcd(s,6)=1$. Hence $$\sigma(r) = \sigma(6)\sigma(s) > 12s = 2r$$hence we are done.
30.06.2023 13:23
12.09.2023 17:25
Obviously $f(n)=\sigma (n)-n$, which leads to the following observation. Claim: There exist several distinct prime numbers $p_1,\dots,p_t$, such that any positive integer $n$ divided by $\prod \limits_{i=1}^{t}p_i$ satisfies $f(n)>n$. Proof of the claim: Note that $$\frac{\sigma(n)}{n}\geq\prod\limits_{p|n}(1+\frac{1}{p})$$and that $\prod\limits_{p \text{prime}}(1+\frac{1}{p})=\infty$ . Thus there exist prime numbers $p_1,\dots, p_t$, such that any positive integer $n$ divided by $p_1p_2\dots p_t$ satisfies $\frac{\sigma (n)}{n}>2$, hence the claim. $\blacksquare$ Now we can prove the crucial conclusion stated as follow: For each positive integer $k$, there exist $k-1$ distinct prime numbers $q_1,q_2,\dots,q_{k-1}$ other than $p_1,\dots, p_{t}$ and $k-1$ positive integers $e_1,e_2,\dots, e_{k-1}$, such that for any positive integer $n$, if $n$ satisfies that $\prod\limits_{i=1}^{t}p_i | n$ and $q_j^{e_j}\Vert n$ for $1\leq j\leq k-1$, then $n<f(n)<\dots<f^{k}(n)$. The proof of this conclusion is given by induction. The base case $k=1$ is simply the claim. Assume the conclusion holds for $k$. Pick a prime number $q_k$ other than $p_1,\dots, p_t$ and $q_1,\dots, q_{k-1}$. Obviously there exists a positive integer $e_k$ such that $$\frac{q_k^{e_k+1}-1}{q_k-1}\equiv 0 \pmod{\prod\limits_{i=1}^{t}p_i\cdot \prod\limits_{j=1}^{k-1}q_j^{e_j+1}}$$If a positive integer $n$ satisfies that $\prod\limits_{i=1}^{t}p_i|n$ and $q_j^{e_j}\Vert n$ for $1\leq j\leq k$, we know that $f(n)>n$ due to the claim. In addition, because $$\sigma (n)=\frac{q_k^{e_k+1}-1}{q_k-1}\cdot A \equiv 0 \pmod {\prod\limits_{i=1}^{t}p_i\cdot \prod\limits_{j=1}^{k-1}q_j^{e_j+1}}$$we know that $f(n)=\sigma(n)-n$ is divided by $\prod\limits_{i=1}^tp_i$, also $\nu_{q_j}(f(n))=e_j$ for $1\leq j\leq k-1$. By induction hypothesis, we have $f(n)<f^2(n)<\dots<f^{k+1}(n)$. Therefore $n<f(n)<\dots<f^{k+1}(n)$. Done! This wraps up the proof. Remark: With the same method, we are able to prove a stronger result: There exist infinitely many positive integers $n$, such that$$\frac{f^{i}(n)}{f^{i-1}(n)}>C$$for any positive constant $C$, $1\leq i \leq k$.