Find all strictly increasing sequences $\{a_k\}_{k=1}^\infty$ of positive integers such that $\frac{a_{nk}}{a_na_k} \in (1,2)$ for any $n,k>1$.


First, I was wondering about the strictly increasing sequences of real numbers such that $\frac{a_{nk}}{a_na_k}=1$ for any integer $n,k\ge 1.$ I believe all such sequences look like $a_k=k^\alpha$ for some $\alpha > 0$ (due to Erdős’ result).

Then I started changing the conditions. What if I try to find all the strictly increasing sequences such that $\frac{a_{nk}}{a_na_k}=2$ for any integer $n,k>1$. We can’t deduce $a_1=1$ in this case. Since $a_1$ never participates in $\frac{a_{nk}}{a_na_k}=2$ anyway, it can be any number smaller than $a_2$. Overall, it seems to me that virtually the same reasoning as for the previous question could be made for this case, so $a_k=k^\alpha$ for some positive $\alpha$. But then from $\frac{a_{nk}}{a_na_k}=2$ we get that $1=2$. So such sequences don’t exist.

Now, what if we try the condition $\frac{a_{nk}}{a_na_k}\in (1,2)?$ If we ignore the monotonicity condition then $a_k=2/3$ would work. So something like $a_k={2\over3} + \frac{\sum_{i=1}^k 1/2^k}{10^{100}}$ is fine. There is a lot of such sequences.

Then let us make $a_k$ positive integers, arriving to our main question.


I failed to find an example of such sequence yet. My intuition tells me that if $\frac{a_{nk}}{a_na_k}>1$ then $\frac{a_{nk}}{a_na_k}$ is not bounded. My hypothesis is that no such sequence exists.


Different examples of such sequences have appeared. The hypothesis is wrong. I still wonder if all these sequences can be described in a nice way though.

  • $\begingroup$ By "increasing" do you mean strictly increasing? $\endgroup$ Feb 11 at 3:02
  • $\begingroup$ @GregMartin yes, strictly increasing. $\endgroup$
    – Aig
    Feb 11 at 3:03
  • $\begingroup$ Such sequences certainly can't be bounded, since $a_2\ge2$ and thus $a_{2^m} > 2^m$ for all $m\ge2$. $\endgroup$ Feb 11 at 3:05
  • 1
    $\begingroup$ @GregMartin I meant $a_{nk}/a_na_k$ is not bounded. $\endgroup$
    – Aig
    Feb 11 at 3:06
  • 1
    $\begingroup$ Consider the greedy sequence, where $a_n$ is chosen to be the smallest integer greater than $a_{n-1}$ such that $a_n/a_da_{n/d} > 1$ for all nontrivial divisors $d$ of $n$. (That sequence isn't in OEIS, fwiw.) Emperically it seems that $a_n/a_da_{n/d}$ is bounded by $1.5$. The largest ratios seem to correspond to certain numbers $n$ that are just greater than powers of $4$. $\endgroup$ Feb 11 at 4:40

1 Answer 1


Let $a_n := n^2-1$. Then $\dfrac{a_{xy}}{a_xa_y}\in(1, 2)$ for $x, y\ge2$. In fact

Proposition. $a_{xy} > a_xa_y$

Proof. $$\begin{aligned} (xy)^2-1 &> (x^2-1)(y^2-1)&\iff\\ x^2y^2-1 &>x^2y^2-x^2-y^2+1&\iff\\ x^2+y^2&>2 \end{aligned}$$ which holds true because $x, y>1.~\square$

Proposition. $a_{xy} < 2a_xa_y$

Proof. $$\begin{aligned} (xy)^2-1 &< 2(x^2-1)(y^2-1)&\iff\\ x^2y^2-1 &<2x^2y^2-2x^2-2y^2+2&\iff\\ 1 &< x^2y^2-2x^2-2y^2+4&\iff\\ 1&<(x^2-2)(y^2-2) \end{aligned}$$ which holds true because $x, y\ge 2.~\square$

  • 1
    $\begingroup$ Yes, $n^\alpha-m$ seems to work for any integer $\alpha \ge 2$ and $m$ small enough. Probably $m$ doesn’t have to be a constant, too. So, there is probably a lot of such sequences, built from different ideas, and they are hard to charactarize in a nice way. $\endgroup$
    – Aig
    Feb 12 at 5:16
  • $\begingroup$ a minor thing, $a_1$ is not a positive integer. $\endgroup$
    – Yimin
    Feb 12 at 6:03
  • 1
    $\begingroup$ @Yimin we can set $a_1$ any positive integer smaller than $a_2$. Since $a_2 = 2^2-1=3$ we can take $a_1=1$ or $2$. This number $a_1$ doesn’t participate in the condition anyway. Btw, a simple example $a_n=n-1$ would work too, if we “ignore” $a_1, a_2, a_3$ in a similar way. $\endgroup$
    – Aig
    Feb 12 at 7:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .