Recurrent sequence with divisor function is unbounded, but not monotone

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

w

0 users

TOPICS

No tags match your search

M

No tags match your search

M

Recurrent sequence with divisor function is unbounded, but not monotone

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: VJIMC 2024, Category II, Problem 4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

9045 posts

#1 h Apr 14, 2024, 4:08 PM • 2 Y

Y by selberg_atle, yofro

Let $(b_n)_{n \ge 0}$ be a sequence of positive integers satisfying $b_n=d\left(\sum_{i=0}^{n-1} b_k\right)$ for all $n \ge 1$ . (By $d(m)$ we denote the number of positive divisors of $m$ .)
a) Prove that $(b_n)_{n \ge 0}$ is unbounded.
b) Prove that there are infinitely many $n$ such that $b_n>b_{n+1}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3151 posts

yofro

#2 h Sep 4, 2024, 11:59 PM • 1 Y

Y by LozenCHEN

Interesting problem. Hopefully this is correct.

Lemma: Let $N\ge 1$ be fixed. The set of naturals with at most $N$ divisors has natural density $0$ .

Proof sketch: We have the finite union
$\{n\in \mathbb{N}|d(n)\le N\}=\{p\} \cup \{p^2\} \cup \{pq\} \cup \cdots.$ Each of the sets in the union has density $0$ because the primes have density $0$ , so the union has density $0$ .

a) We wish to show $d(a_n)$ is unbounded. Suppose otherwise that it is bounded by $N$ . The set of naturals with at most $N$ divisors has natural density $0$ . But we have $a_{i+1}-a_i\le N$ for all $i$ , so $(a_i)_{i\ge 0}$ has natural density at least $N^{-1}$ , contradiction.

b) Suppose otherwise. Re-index so that $b_n\le b_{n+1}$ for all $n$ . We make note of the well-known bound $d(n)\ll_{\varepsilon} n^{\varepsilon}$ . We can use this to upper bound our $a_n$ . Fix a $\varepsilon>0$ and observe by, say, MVT that $a_{n+1}^{1-\varepsilon}-a_n^{1-\varepsilon}\le d(a_n)(1-\varepsilon) a_n^{-\varepsilon}=o(1)$ . Hence $a_n^{1-\varepsilon}=o(n)$ and so $a_n=o(n^{1+\delta})$ for any $\delta>0$ . In turn, we have $b_n=o(n^{\delta})$ for any $\delta>0$ . Now that we've established that the $b_n$ remain small, we will derive a contradiction by showing that we cannot have the $(b_n)_{n\ge 0}$ sequence remain constant for a long time. In particular, we will show that for all $n$ there are constants $C,\gamma>0$ such that $b_n=b$ has at most $Cb^{\gamma}$ solutions for $n$ . This implies that for all $N>0$ we have $C\sum_{b<f(N)}b^{\gamma}>N$ , where $f(N)=o(N^{\delta})$ . There's a clear contradiction here. We're left with the following lemma, which is the heart of the problem.

Lemma: Let $k$ be sufficiently large. Then the length of the longest arithmetic progression with common difference $k$ and all terms having $k$ divisors is $\le Ck^{\gamma}$ for some $C,\gamma>0$ .

Proof: Find some $t$ with $\gcd(t,k)=1$ and $d(t)>d(k)$ . We will upper bound the smallest such $t$ . Using this $t$ , we may construct a term in any arithmetic progression with length $\gg t$ divisible by $t$ , hence having more divisors than $t$ (and thus $k$ ). It's enough to show that $t=O(k^{\gamma})$ for some $\gamma$ . Let $k=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}$ and let $q_1, q_2, \dots$ be the primes not dividing $k$ (in increasing order). The strategy is to take $t=q_1q_2\cdots q_{\ell}$ for the smallest $\ell$ such that $2^{\ell}>\prod_{j=1}^r (e_j+1)$ . We have $\ell \sim \sum_{j=1}^r \log(e_j+1)$ . We may bound
$t<\frac{(r+\ell)\#}{r\#}<\frac{4^{r+\ell}}{e^r}=(4/e)^r\cdot 4^{\ell},$ so
$\log t<c\left(r+\sum_{j=1}^r \log(e_j+1)\right)$ for some constant $c$ . Note that $\log k=\sum_{i=1}^r e_i\log p_i$ . We have the obvious lower bound $\log k\ge \vartheta(r)=O(r)$ , where $\vartheta(r)$ denotes the Chebyshev function. Since $\log(x+1)=O(x)$ , putting this all together gives us
$\log t\le C\log k$ for some constant $C$ , as desired.

Note: Here $n\#$ is the $n$ th primorial, the product of the first $n$ primes. We use the well-known bounds $e^n\lesssim n\#\le 4^n$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

75 posts

#3 h Apr 27, 2025, 10:47 AM

Y by

yofro wrote:

Interesting problem. Hopefully this is correct.

Lemma: Let $N\ge 1$ be fixed. The set of naturals with at most $N$ divisors has natural density $0$ .

Proof sketch: We have the finite union
$\{n\in \mathbb{N}|d(n)\le N\}=\{p\} \cup \{p^2\} \cup \{pq\} \cup \cdots.$ Each of the sets in the union has density $0$ because the primes have density $0$ , so the union has density $0$ .

a) We wish to show $d(a_n)$ is unbounded. Suppose otherwise that it is bounded by $N$ . The set of naturals with at most $N$ divisors has natural density $0$ . But we have $a_{i+1}-a_i\le N$ for all $i$ , so $(a_i)_{i\ge 0}$ has natural density at least $N^{-1}$ , contradiction.

b) Suppose otherwise. Re-index so that $b_n\le b_{n+1}$ for all $n$ . We make note of the well-known bound $d(n)\ll_{\varepsilon} n^{\varepsilon}$ . We can use this to upper bound our $a_n$ . Fix a $\varepsilon>0$ and observe by, say, MVT that $a_{n+1}^{1-\varepsilon}-a_n^{1-\varepsilon}\le d(a_n)(1-\varepsilon) a_n^{-\varepsilon}=o(1)$ . Hence $a_n^{1-\varepsilon}=o(n)$ and so $a_n=o(n^{1+\delta})$ for any $\delta>0$ . In turn, we have $b_n=o(n^{\delta})$ for any $\delta>0$ . Now that we've established that the $b_n$ remain small, we will derive a contradiction by showing that we cannot have the $(b_n)_{n\ge 0}$ sequence remain constant for a long time. In particular, we will show that for all $n$ there are constants $C,\gamma>0$ such that $b_n=b$ has at most $Cb^{\gamma}$ solutions for $n$ . This implies that for all $N>0$ we have $C\sum_{b<f(N)}b^{\gamma}>N$ , where $f(N)=o(N^{\delta})$ . There's a clear contradiction here. We're left with the following lemma, which is the heart of the problem.

Lemma: Let $k$ be sufficiently large. Then the length of the longest arithmetic progression with common difference $k$ and all terms having $k$ divisors is $\le Ck^{\gamma}$ for some $C,\gamma>0$ .

Proof: Find some $t$ with $\gcd(t,k)=1$ and $d(t)>d(k)$ . We will upper bound the smallest such $t$ . Using this $t$ , we may construct a term in any arithmetic progression with length $\gg t$ divisible by $t$ , hence having more divisors than $t$ (and thus $k$ ). It's enough to show that $t=O(k^{\gamma})$ for some $\gamma$ . Let $k=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}$ and let $q_1, q_2, \dots$ be the primes not dividing $k$ (in increasing order). The strategy is to take $t=q_1q_2\cdots q_{\ell}$ for the smallest $\ell$ such that $2^{\ell}>\prod_{j=1}^r (e_j+1)$ . We have $\ell \sim \sum_{j=1}^r \log(e_j+1)$ . We may bound
$t<\frac{(r+\ell)\#}{r\#}<\frac{4^{r+\ell}}{e^r}=(4/e)^r\cdot 4^{\ell},$ so
$\log t<c\left(r+\sum_{j=1}^r \log(e_j+1)\right)$ for some constant $c$ . Note that $\log k=\sum_{i=1}^r e_i\log p_i$ . We have the obvious lower bound $\log k\ge \vartheta(r)=O(r)$ , where $\vartheta(r)$ denotes the Chebyshev function. Since $\log(x+1)=O(x)$ , putting this all together gives us
$\log t\le C\log k$ for some constant $C$ , as desired.

Note: Here $n\#$ is the $n$ th primorial, the product of the first $n$ primes. We use the well-known bounds $e^n\lesssim n\#\le 4^n$ .

I don't know if I am understanding it correctly, but in your proof of the mail lemma, you are finding a $t=O(k^{\gamma})$ such that $d(t)>d(k)$ . But what you are wishing for to find is a $t$ such that $d(t)>k$ . Also, I don't think this approach will work, as it would imply to find a $t=O(k^{\gamma})$ such that $d(t)>k$ , but as you said $d(n)=n^{o(1)}$ , so for $k$ big enough there does not exist such $t$ .

Correct me if I'm wrong, I might be misunderstanding something.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a