Distinct Integers with Divisibility Condition

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Distinct Integers with Divisibility Condition

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2017 ELMO Shortlist N3

The post below has been deleted. Click to close.

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

3223 posts

#1 h Jul 3, 2017, 12:47 AM • 2 Y

Y by Adventure10, Mango247

For each integer $C>1$ decide whether there exist pairwise distinct positive integers $a_1,a_2,a_3,...$ such that for every $k\ge 1$ , $a_{k+1}^k$ divides $C^ka_1a_2...a_k$ .

Proposed by Daniel Liu

Z K Y

The post below has been deleted. Click to close.

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

486 posts

#2 h Jul 3, 2017, 4:04 PM • 1 Y

Y by Adventure10

My solution:i will prove that there is no sequence sastisfied the problem
Let $p|C$ and $t=v_p(C)$ and $b_k=v_p(a_k)$
So we need $b_{k+1}.k<=tk+\sum_{i=1}$
Consider sequence $c_n=\sum_{k=1}^{n}\frac{1}{k}$
We can easily prove that $b_n<=[ta_n]+b_1$
But note that there exist m such that for all $n>m$ , $n-b_1>[ta_n]$
Which implies there exist infinitive number i,j: $b_i=b_j$
Let S={(i,j), $b_i=b_j$ }
Consider prime $q=!p$ of C
We found that in S there are infinitive (t,s): $v_p(a_t)=v_p(a_s)$ and $v_q(a_t)=v_q(a_s)$
Continue this with all prime divisor of C we are done

Z K Y

The post below has been deleted. Click to close.

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

4071 posts

#3 h Jul 16, 2017, 8:48 AM • 2 Y

Y by Adventure10, Mango247

My lengthly solution

This post has been edited 3 times. Last edited by ThE-dArK-lOrD, Jun 29, 2018, 8:03 PM

Z K Y

The post below has been deleted. Click to close.

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

1566 posts

#4 h Aug 22, 2020, 5:46 PM • 2 Y

Y by centslordm, PRMOisTheHardestExam

Nice problem. I will give a sketch.

tastymath75025 wrote:

For each integer $C>1$ decide whether there exist pairwise distinct positive integers $a_1,a_2,a_3,...$ such that for every $k\ge 1$ , $a_{k+1}^k$ divides $C^ka_1a_2...a_k$ .

The answer is no. Suppose not for a fixed $C.$ Consider any prime $p.$ Then the problem gives
$k\nu_p (a_{k+1}) \le k\nu_p(C)+\nu_p(a_1)+\dots+\nu_p(a_k).$ Now we have the following key claim which can be proven by simple induction:

Claim: Let $\text{H}_n$ denote the $n$ th harmonic number. Then
$\nu_p( a_n)-\nu_p(a_1) \le \text{H}_n \nu_p(C).$

The key hypothesis we need now is that $a_i$ are pairwise distinct. The claim gives $\nu_p(C)=0 \implies \nu_p(a_n) \le \nu_p(a_1).$ In particular $\nu_p(a_m)$ is eventually constant. So ignore primes for which $\nu_p(C)=0.$ This means we only have a finite set of prime factors to worry about for the sequence now.

The claim clearly gives $\nu_p(a_n/a_1) \le A \log n$ for some constant $A$ and all primes $p.$ Now it is not too hard to see that we can find arbitrarily large intervals over which $\left \lfloor A\log x \right \rfloor$ is constant. Since the set of prime factors of $\{a_k\}$ is finite now, hence by pigeonhole two terms $a_i,a_j$ will have the same $\nu_p$ for all primes $p,$ hence will be equal, a contradiction. $\square$

EDIT: Ok, I finally typed the elaborated version of the sketch: Full Proof

This post has been edited 3 times. Last edited by Wizard_32, Nov 6, 2020, 6:51 AM

Z K Y

The post below has been deleted. Click to close.

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

1051 posts

#5 h Jan 25, 2021, 2:42 PM

Y by

There is no such sequence for any $C$ . For convenience, define $x_n = v_p(a_n)$ for every integer $n$ . Furthermore, define $h_n = \frac{1}{1}+\frac{1}{2}+\dots+\frac{1}{n}$ . Finally, let $S = v_p(C)$ . The pith of the problem lies in the following claim:

Claim: $x_n \leq x_1 + Sh_n$ .

Proof: By strong induction. Remark that the condition tells us $x_n \leq S + \frac{x_1+x_2+\dots+x_{n-1}}{n-1}.$
This claim implies that for any prime $p$ , there exists an arbitrary long sub-sequence of terms $a_i,a_{i+1},\dots,a_j$ such that $\nu_p(a_i) = \nu_p(a_{i+1}) = \dots = \nu_p(a_j)$ for sufficiently large $i$ and $j$ . Note that for primes $p$ in $a_1$ but not $C$ , $\nu_p(a_i) \leq \nu_p(a_1)$ , so there are only a finite number of possible terms with equal $v_p$ for all primes $p \in C$ . Therefore, for sufficiently large $i$ there will be two equal terms, the end.

This post has been edited 1 time. Last edited by mathlogician, Jan 25, 2021, 2:43 PM

Z K Y

The post below has been deleted. Click to close.

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

478 posts

#6 h Sep 20, 2021, 5:47 AM

Y by

tastymath75025 wrote:

For each integer $C>1$ decide whether there exist pairwise distinct positive integers $a_1,a_2,a_3,...$ such that for every $k\ge 1$ , $a_{k+1}^k$ divides $C^ka_1a_2...a_k$ .

Proposed by Daniel Liu

Define $\mathbf{H}_n=1+\frac{1}{2}+.............+\frac{1}{n}$
The condition is equivalent to $k\nu_p(a_{k+1}) \le k \nu_p(C)+\sum_{j=1}^k \nu_p(a_j)$
Claim: $\nu_p(a_n)-\nu_p(a_1) \le\mathbf{H}_n \nu_p(C)$
Proof: Obvious by strong induction.
This implies that $\nu_p(a_j)$ is bounded and when $j$ is sufficiently large we will get $\nu_p(a_j)=\nu_p(a_{j+1}),\forall p \implies a_j=a_{j+1}$ , contradiction.

Z K Y

The post below has been deleted. Click to close.

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

46 posts

#7 h Nov 16, 2021, 5:09 PM

Y by

I'll prove that for no $C$ there exists such a sequence. I'll start with the following claim:

Claim: $v_p(a_{k+1})\leq (1+\frac12 + \cdots +\frac1k)v_p(C) + v_p(a_1)$ for every prime $p$ .

Proof : It's not hard to show this by induction.

We can find arbitrarily large intervals over which $(1+\frac12 + \cdots +\frac1k)v_p(C) + v_p(a_1)$ is constant, but note that $a_{k+1}$ can take only values which are divisors of $a_1C^{X}$ where $X=\lceil (1+\frac12 + \cdots +\frac1k)v_p(C)\rceil$ . Now at some point $d(a_1C^{X})$ is going to be smaller than the length of these intervals because $1+\frac12 + \cdots +\frac1k$ grows very slowly, so the $a_i$ 's can't be distinct over these intervals.

Z K Y

The post below has been deleted. Click to close.

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

657 posts

#8 h Feb 5, 2022, 2:27 PM

Y by

Here's a different proof (we will bound the $v_p$ 's differently without the harmonic number).

We will show for any $C$ , such a sequence does not exist. Assume contrary. Fix $C$ and such a sequence. Call a prime nice if it divides some $a_i$ . Note all nice primes must divide $C \cdot a_1$ , in particular number of nice primes is finite. Fix a $c > 1$ such that $c > v_p(C)$ for all primes $p$ . Fix any nice prime $p$ . Let $b_i = v_p(a_i)$ . Then we know that
$k b_{k+1} \le kc + b_1 + b_2 + \cdots + b_k ~~ \forall ~ k \ge 2 \qquad \qquad (1)$ Intuitively, we will show that $b_i$ 's grow slowly. Call an $i \ge 2$ a peak if $b_i > b_{i-1},\ldots,b_1$ . Let $i_1+1 < i_2 + 1< i_3 + 1 < \cdots$ be all the peaks.

Claim 1: For all $n \ge 1$ we have
$\frac{i_1 + i_2 + \cdots + i_n}{i_n} \le c ~ \iff ~ \frac{i_1 + \cdots + i_{n-1}}{i_n} \le c-1$
Proof: Define $f(m) = (b_m - b_1) + (b_m - 2) + \cdots + (b_m - b_{m-1})~ \forall ~ m \ge 2$ . Note $(1)$ is equivalent to
$\frac{f(k)}{k-1} \ge c \qquad \qquad (2)$ Observe that for any $n \ge 1$ that
$\begin{align*} f(i_{n + 1} + 1) &= \sum_{j=1}^{i_{n+1}}\left( b_{i_{n+1} + 1} - b_j \right) = \sum_{j= i_n + 1}^{i_{n+1}} (b_{i_{n+1} + 1} - b_j) + \sum_{j=1}^{i_n} (b_{i_{n+1} + 1} - b_j) \\ &\ge (i_{n+1} - i_n)(b_{i_{n+1} + 1} - b_{i_n + 1}) + \sum_{j=1}^{i_n} \bigg( (b_{i_{n+1} + 1} - b_{i_{n} + 1}) + (b_{i_n + 1} - b_j) \bigg) \\ &= i_{n+1}(b_{i_{n+1} + 1} - b_{i_n + 1}) + f(i_n + 1) \ge i_{n+1} + f(i_n + 1) \end{align*}$ Now note $f(i_1 + 1) \ge i_1$ . So it follows that
$f(i_n + 1) \ge i_1 + i_2 + \cdots + i_n ~~ \forall ~ n \ge 1$ Plugging $k = i_n + 1$ in $(2)$ and using above implies our claim. $\square$

Claim 2: $\exists$ an $\alpha > 1$ such that $i_k \ge \alpha^{k-1} ~ \forall ~ k \ge c+2$ .

Proof: We will only use each $i_n \ge 1$ and Claim 1 to prove this. Observe $i_1 + \cdots + i_{c+1} > c+1$ , since all of them cannot be $(1)$ (by Claim 1 for $n=c+1$ ). Now choose a very small $\alpha > 1$ such that:
$\begin{align*} i_1 + i_2 + \cdots + i_{c+1} \ge 1 + \alpha + \cdots + \alpha^c \\ \frac{1}{\alpha} + \frac{1}{\alpha^2} + \cdots + \frac{1}{\alpha^c} \ge c-1 \end{align*}$ We show this $\alpha$ works. Suppose for some $t \ge c+1$ it holds that $i_1 + \cdots + i_t \ge 1 + \alpha + \cdots + \alpha^{t-1}$ . We will show $i_{t+1} \ge \alpha^t$ (note this would imply our claim by induction). $k=t+1$ in $(3)$ gives
$i_t \ge \frac{i_1 + \cdots + i_t}{c-1} \ge \frac{1 + \alpha + \cdots + \alpha^{t-1}}{c-1} = \frac{\alpha^t - 1}{(c-1)(\alpha - 1)}$ So it suffices to show
$\begin{align*} \frac{\alpha^t - 1}{(c-1)(\alpha - 1)} \ge \alpha^t \iff (c-1)(\alpha-1) \le \frac{\alpha^t - 1}{\alpha^t} = 1 - \frac{1}{\alpha^t} \iff (c-1)(\alpha -1) + 1 - \frac{1}{\alpha^t} \le 0 \end{align*}$ Indeed,
$\begin{align*} (c-1) (\alpha -1) + 1 - \frac{1}{\alpha^t} &= (\alpha -1) \left( (c-1) - \left( \frac{1}{\alpha} + \frac{1}{\alpha^2} + \cdots + \frac{1}{\alpha^{t-1}} \right) \right) \\ &\le (\alpha -1) \left(c-1 -\left( \frac{1}{\alpha} + \frac{1}{\alpha^2} + \cdots + \frac{1}{\alpha^c} \right) \right) \le 0 \end{align*}$ This proves our claim. $\square$

Claim 3 (Key Result): For large $t$ , all of $b_1,b_2,\ldots,b_{\alpha^t}$ are at most $c(t+1)$ .

Proof: Observe that $b_{i_{n+1} + 1} - b_{i_n + 1} \le c ~ \forall ~ n \ge 1$ . As $b_{i_1 + 1} = b_2 \le b_1 + c$ , so it follows $b_{i_m + 1} \le b_1 + cm ~~ \forall ~ m \ge 1$ Now $i_{t+1} + 1 \ge \alpha^t+1$ , thus all of $b_1,b_2,\ldots,b_{\alpha^t-1}$ are $\le b_{i_t + 1} \le b_1 + tc$ , and $b_1 + tc \le t(c+1)$ for large $t$ . This proves our claim. $\square$

Now let $p_1,p_2,\ldots,p_k$ be all the nice primes, and $\alpha_1,\alpha_2,\ldots, \alpha_k > 1$ be any numbers for which Claim 3 is true. Let $\alpha = \min(\alpha_1,\alpha_2,\ldots,\alpha_k)$ . For a large $t$ , look at the numbers
$a_1,a_2,\ldots,a_{\alpha^t}$ By Claim 3 we know that for any $p_i$ adic valuation of any of these numbers is $\le c(t+1)$ . It follows number of distinct numbers between them is at most
$\bigg(c(t+1) + 1 \bigg)^k$ As all $a_i$ 's are distinct, so this forces
$\bigg( c(t+1) + 1 \bigg)^k \ge \alpha^t \qquad \text{for all large } t$ But this is a contradiction as exponential functions grow faster than polynomial functions. This completes the proof. $\blacksquare$

Motivation: The problem isn't even true if $a_i$ 's are not given to be distinct, so we somehow had to prove that. So we basically had to prove the $v_p$ 's don't grow fast. Now $(1)$ was only interesting for peaks. So it was natural to consider peaks. Now after getting Claim 1, I was sure we only have to use Claim 1 and ignore all other conditions on peaks, which along with $b_{i_{n+1} + 1} - b_{i_n + 1} \le c$ would give us the sequence $\{b_k\}_{k \ge 1}$ doesn't grow fast. So we only had to prove Claim 2. Basically, we conjecture $i_k \ge \alpha^{k-1}$ for all $k$ (for some $\alpha > 1$ ). We then find the sufficient conditions on $\alpha$ for which we can prove this by induction. The two equations in proof of Claim 2 were precisely those. Now we had some problems like it might happen $i_1 = i_2 = 1$ , but that was easy to fix by showing $i_k \ge \alpha^{k-1}$ for large $k$ .

Z K Y

The post below has been deleted. Click to close.

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

5003 posts

#9 h Apr 6, 2022, 1:58 PM • 1 Y

Y by centslordm

The answer is no such $C$ . Let $p$ be some prime, and let $\nu_p(C)=c$ , $x_i=\nu_p(a_i)$ for $i \geq 1$ . Viewing the divisibility condition in $p$ -adic terms only, it is equivalent to
$kx_{k+1} \leq kc+x_1+\cdots+x_k.$ Let $(H_n)$ denote the sequence of harmonic numbers. The crux of the problem is the following:

Claim: $x_n-x_1 \leq cH_{n-1}$ .
Proof: Shifting $(x_i)$ doesn't modify the truth of the condition, so WLOG let $x_1=0$ . We now use strong induction:
$\begin{align*} (n-1)c+x_1+\cdots+x_{n-1}&\leq(n-1)c+c\left(\left(\frac{1}{1}\right)+\left(\frac{1}{1}+\frac{1}{2}\right)+\cdots+\left(\frac{1}{1}+\cdots+\frac{1}{n-2}\right)\right)\\ &=c\left(1+(n-2)+\frac{n-2}{1}+\frac{n-3}{2}+\cdots+\frac{1}{n-2}\right)\\ &=c\left(\frac{n-1}{1}+\frac{n-1}{2}+\cdots+\frac{n-1}{n-2}+\frac{n-1}{n-1}\right)\\ &=c(n-1)H_{n-1}, \end{align*}$ so $(n-1)x_n \leq c(n-1)H_{n-1} \implies x_n \leq cH_{n-1}$ as desired.

The claim implies that $\nu_p(a_n)$ is zero if $p \nmid a_1C$ , $O(1)$ if $p \nmid C$ but $p \mid a_1$ , and $O(\log n)$ otherwise. Suppose there are $a$ distinct primes dividing $C$ and $b$ distinct primes dividing $a_1$ but not $C$ . Then there are $O(1^b(\log n)^a)\sim O((\log n)^a)$ choices for the value of $a_n$ —we have $O(1)$ options for $\nu_p(a_n)$ if $p \mid a_1$ and $p \nmid C$ , and $O(\log n)$ options for $\nu_p(a_n)$ if $p \mid C$ . But $n$ dominates $O((\log n)^a)$ , so by Pigeonhole for sufficiently large $n$ there must exist two non-distinct elements of the sequence: contradiction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

40 posts

#10 h Apr 19, 2022, 8:08 PM • 2 Y

Y by Mango247, Mango247

The anwser is, that there is no sequnce, which satisfies the problem.
Proof:
Now choose any $a_{k+1} < a_{k+2}$ .
First of all we see, that $a_{k+1}^k \mid C^k a_1 a_2 ... a_k$ $\Rightarrow$ $k \cdot v_p(a_{k+1}) \le k \cdot v_p(C) + v_p(a_1) + v_p(a_2) + ... +v_p(a_k)$ $\Rightarrow$ $k \cdot (v_p(a_{k+1} - v_p(C)) \le v_p(a_1) + v_p(a_2) + ... +v_p(a_k)$ $(1)$ . Similarly and because of $a_{k+1} < a_{k+2}$ , we get $(k+1) \cdot (v_p(a_{k+2} - v_p(C)) \le v_p(a_1) + v_p(a_2) + ... + v_p(a_{k+1})$ $(2)$ , for every prime dividing both sides of the equations. Now we calculate $(2) - (1)$ , which is equivalent after some boring basics in arithmetic to $(k+1) \cdot [v_p(a_{k+2}) - v_p(a_{k+1})] \le v_p(C)$ $\Rightarrow$ $v_p((\frac{a_{k+2}}{a_{k+1}})^{k+1}) \le v_p(C)$ $\Rightarrow$ $(\frac{a_{k+2}}{a_{k+1}})^{k+1} \mid C$ $\Rightarrow$ $(\frac{a_{k+2}}{a_{k+1}})^{k+1} \le C$ . But this inequality is not true for a large $k$ , hence we get a contradiction and we are done :ninja:

:ninja:

Z K Y

The post below has been deleted. Click to close.

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

aaabc123mathematics

19 posts

aaabc123mathematics

#11 h Jun 19, 2022, 1:21 AM

Y by

PianoPlayer111 wrote:

{a_{k+1}})^{k+1} \le C $. But this inequality is not true for a large$ k $, hence we get a contradiction and we are done :ninja:[/quote] Why ?If {a_{k+1}})^{k+1} \le C$ . isn't very big ,how can explain the numer is larger than C?

Z K Y

The post below has been deleted. Click to close.

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

2320 posts

oty

#12 h Jun 19, 2022, 3:35 AM

Y by

Nice problem

Z K Y

The post below has been deleted. Click to close.

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

22 posts

#13 h Jul 17, 2023, 3:37 AM

Y by

How do the $\nu_p$ 's grow? Define $S$ as the set of prime divisors of $a_1C$ . Note that the given sequence has no prime factors outside of $S$ . Let prime $p \in S$ be arbitrary. Denote $b_n = \nu_p(a_n)$ for all positive integers $n$ . The given condition rewrites as:
$kb_{k + 1} \leq k\nu_p(C) + b_1 + b_2 + \cdots + b_k.$ Define $s_n = \frac{b_1 + b_2 + \cdots + b_n}{n}$ as the average of the first $n$ elements of our new sequence. Adding $k(b_k + \cdots + b_1)$ to both sides of this inequality and dividing through by $k(k + 1)$ lends us a useful inequality.
$\frac{b_{k+1}+\cdots + b_1}{k+1} \leq \frac{1}{k+1} \nu_p(C) + \frac{b_k + \cdots + b_1}{k}.$ Applying this inequality repeatedly gives us the following inequality.
$s_k \leq \left(\frac{1}{k} + \cdots + \frac{1}{2}\right)\nu_p(C) + s_1.$ Plugging back into the original inequality and bounding the harmonic series gives us:
$b_{k+1} \leq \nu_p(C) + s_k \leq \left(\frac{1}{k} + \cdots + \frac{1}{1}\right)\nu_p(C) + b_1 \leq \ln(k+1) + b_1.$ Something is seriously wrong, and we are very happy about it. Since the above is true for all primes $p$ , there are $O((\ln k)^{|S|})$ different possibilities for the values of $a_1, \dots, a_k$ . Since
$O((\ln k)^{|S|}) < k$ as $k$ approaches infinity, there must exist two terms in the sequence that are equal.

Z K Y

The post below has been deleted. Click to close.

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

198 posts

#15 h Sep 29, 2023, 2:15 PM

Y by

Since $a_{k + 1}^k \mid C^k a_{1}a_{2}\dots a_{k}$ and $C$ is constant, so the set of primes dividing an element in $(a_{n})_{n \ge 1}$ is finite. Let $p$ be a arbitrary prime dividing one of $a_{1}, a_{2}, \dots$ . Then the divisibility condition becomes $k\nu_{p}(a_{k + 1}) \le k\nu_{p}(C) + \nu_{p}(a_{1}) + \nu_{p}(a_{2}) + \dots + \nu_{p}(a_{k})$ . Now consider the following claim:

Claim:
For $n \ge 2$ , we have $\nu_{p}(a_{n}) \le \nu_{p}(a_{1}) + \nu_{p}(C)(\frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{n - 1})$ .

Proof:

Apply strong induction on $n$ . Base case is clear. For the induction step, $\nu_{p}(a_{n + 1}) \le \nu_{p}(C) + \frac{1}{n}(\nu_{p}(a_{1}) + \nu_{p}(a_{2}) + \dots + \nu_{p}(a_{n})) \le \nu_{p}(C) + \nu_{p}(a_{1}) + \frac{1}{n}(\nu_{p}(C)((\frac{1}{1}) + (\frac{1}{1} + \frac{1}{2}) + (\frac{1}{1} + \frac{1}{2} + \frac{1}{3}) + \dots + (\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n - 1}))) = \nu_{p}(a_{1}) + \nu_{p}(C)(\frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{n})$ . $\blacksquare$

Since the set of primes dividing an element in $(a_{n})_{n \ge 1}$ is finite, let $a$ be a number of elements in the set of primes dividing an element in $(a_{n})_{n \ge 1}$ . Then taking large $N$ , we see that there are most $(O(\frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{N})^k) = O((\ln N)^k) < N$ distinct values in $a_{1}, a_{2}, \dots, a_{N}$ , a contradiction. Therefore there are no such $C$ . $\blacksquare$

This post has been edited 1 time. Last edited by thdnder, Sep 29, 2023, 2:24 PM

Z K Y

The post below has been deleted. Click to close.

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

773 posts

#16 h Aug 25, 2024, 10:09 PM

Y by

Subjective Rating (MOHs) $\text{[math]}$

Attachments:

Z K Y

The post below has been deleted. Click to close.

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

cursed_tangent1434

642 posts

cursed_tangent1434

#17 h Apr 21, 2025, 4:16 PM

Y by

The first observation is that the set of all primes dividing some term of $(a_i)$ is finite as any prime dividing $a_i$ for $i >1$ must divide $Ca_1$ by induction due to the given divisibility condition. Now, we prove our key bound.

Claim : For all primes $p \mid Ca_1$ and positive integers $k$ ,
$\nu_p(a_k) \le \nu_p(a_1)+\nu_p(C)\left(\frac{1}{1}+\frac{1}{2}+\dots + \frac{1}{k-1}\right)$
Proof : This is a simple calculation. Note that the condition implies that for all $k \ge 1$ ,
$(k-1)\nu_p(a_k)\le (k-1)\nu_p(C) + \nu_p(a_1)+\nu_p(a_2)+\dots + \nu_p(a_{k-1})$ Now replacing $\nu_p(a_2),\dots , \nu_p(a_{k-1})$ inductively we obtain,
$\begin{align*} \nu_p(a_k) & \le \nu_p(C) + \frac{\nu_p(a_1)+\nu_p(a_2)+\dots + \nu_p(a_{k-1})}{k-1}\\ & \le \nu_p(C) + \frac{\nu_p(a_1)+\nu_p(a_2)+\dots + \nu_p(a_{k-2})}{k-1} + \frac{\nu_p(C)+\frac{\nu_p(a_1)+\nu_p(a_2)+\dots + \nu_p(a_{k-2})}{k-2}}{k-1}\\ &= \nu_p(C) + \frac{\nu_p(C)}{k-1} + \frac{\nu_p(a_1)+\nu_p(a_2)+\dots + \nu_p(k-2)}{k-2}\\ & \vdots\\ & \le \nu_p(C)+\frac{\nu_p(C)}{k-1} + \frac{\nu_p(C)}{k-2}+\dots + \frac{\nu_p(C)}{2} + \frac{\nu_p(a_1)}{2} +\frac{\nu_p(a_1)}{2}\\ &= \nu_p(a_1) + \nu_p(C) \left (\frac{1}{1}+\frac{1}{2}+\dots + \frac{1}{k-1}\right) \end{align*}$ which proves the claim.

Note that we may not have $a_k < k$ for all sufficiently large $k$ . This is because if $a_k <k$ for all $k \ge N$ then for all $k \ge M=\max(a_1,a_2,\dots , a_{N-1})$ , $a_k <M$ but this is a set of $M$ distinct positive integers bounded above by $M-1$ which is a clear contradiction.

However, revisiting our claim, this means for all $k$ the number of distinct positive integers that are possible for $a_1,a_2,\dots , a_k$ is
$\prod_{i=1}^r \left(\left \lfloor \nu_{p_i}(a_1) + \nu_{p_i}(C)H_{k-1}\right \rfloor +1\right) = O\left(\frac{1}{1}+\frac{1}{2}+\dots + \frac{1}{k}\right)^{r} = O(\ln k)^r < k$ for all sufficiently large $k$ where $p_1,p_2,\dots , p_r$ is the set of all primes dividing $Ca_1$ . But this is a contradiction to what we noted above so the desired is impossible for all $C>1$ and we are done.

This post has been edited 1 time. Last edited by cursed_tangent1434, Apr 22, 2025, 9:12 AM
Reason: minor details

Z K Y

The post below has been deleted. Click to close.

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

242 posts

#18 h Apr 21, 2025, 6:45 PM

Y by

We will prove $\boxed{\text{no such sequence exists}}$ .

See that $\text{rad}(a_1a_2 \dots) \mid \text{rad}(a_1C)$ ; hence we can write each $a_i$ as $p_1^{e_1} \dots p_t^{e_t}$ for fixed primes $p_1$ , $\dots$ , $p_t$ ( $t$ is finite).

Claim: $\nu_p(a_n) \le O( \log n)$ for each $p \in \{p_1,\dots,p_t\}$ .
Proof: See that $\nu_p(a_n) \le \nu_p(C)+\frac{\nu_p(a_1)+\dots+\nu_p(a_{n-1})}{n-1}$ By simple induction we have that $\begin{align*} \nu_p(a_n) & \le \nu_p(a_1)+\nu_p(C) \left(1+\dots+\frac{1}{n-1} \right) \le \nu_p(a_1)+ \nu_p(C) \left(1+\int_1^{n-1} \frac{dx}{x} \right) = \nu_p(a_1)+\nu_p(C) \left(1+\log(n-1) \right)=O(\log n) \end{align*}$ As required. $\square$

Now assign a sequence $(\nu_{p_1}(a_n), \dots, \nu_{p_t}(a_n))$ to each $a_n$ . Now fix some large $N$ and look at the number of distinct sequences among $a_1$ , $\dots$ , $a_N$ which is $O(\log N)^t \ll N$ And hence by PHP, two the sequences must coincide and hence their corresponding numbers are same which is a contradiction.

Z K Y

The post below has been deleted. Click to close.

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

114 posts

#19 h May 9, 2025, 1:39 PM

Y by

The main thing is to bound $\nu_p$ for a prime $p$ . The condition gives $k\nu_p (a_{k+1}) \le k\nu_p(C)+\nu_p(a_1)+\dots+\nu_p(a_k)$ Now the key claim is that $\nu_p( a_n)-\nu_p(a_1) \le \text{H}_n \nu_p(C)$ for all integers $n$ where $\text{H}_n$ is the $n$ th harmonic number, which can be proven with simple strong induction. Now this $\nu_p$ can be combined with some analytic estimates to get that the $\nu_p$ of $a_i$ becomes eventually constant for any prime $p\mid C$ and bounded for any prime $p\nmid C$ and these with PHP and polylogarithmic bounds, we get that $a_i$ is not an injective sequence, a contradiction

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a