How can one find all increasing sequences $\{a_i\}_{i=1}^{\infty}$ such that $$d(x_1+x_2+\cdots+x_k)=d(a_{x_{1}}+a_{x_{2}}+\cdots + a_{x_{k}}),$$ holds for all $k$-tuples $(x_1,x_2,\cdots,x_k)$ of positive integers, where $d(n)$ is number of integer divisors of a positive integer $n$, and $k \geq 3$ is a fixed integer?

A special case of this problem which was given in this year's Iran Olympiad:

Find all increasing sequences $a_1,a_2,a_3,...$ of natural numbers such that for each $i,j\in \mathbb N$, number of the divisors of $i+j$ and $a_i+a_j$ is equal.

  • $\begingroup$ Do you have even one example? (other than $1,2,3,4,\dots$) $\endgroup$ – Gerry Myerson May 4 '11 at 2:12
  • 1
    $\begingroup$ No, I don't have. Actually, the unique answer should be $a_n=n \forall n$, but I don't know how to show it's the unique sequence. The case $k=2$ was given on Iran Olympiad (second round) 2011. See here: artofproblemsolving.com/Forum/viewtopic.php?t=404273. I was trying to find the general form of this problem. $\endgroup$ – Amir Parvardi May 4 '11 at 9:40
  • $\begingroup$ Well then maybe that would have been a more honest way of stating the question. Why not make it as easy as possible for people to answer, instead of making it hard? $\endgroup$ – Gerry Myerson May 4 '11 at 13:22
  • 4
    $\begingroup$ Why not add a description of your proof for the Olympiad problem and say why you think it does not generalize? The more information you present, the better. $\endgroup$ – Matthew Conroy May 4 '11 at 20:06
  • 3
    $\begingroup$ @Amir, sure, you can ask questions when you don't know the answers, in fact, you're not supposed to ask questions when you do know the answers. But (I think) the right way to ask this question would be to state the Olympiad result, present the general question, and then ask whether the general question has the same answer as the Olympiad question. $\endgroup$ – Gerry Myerson May 5 '11 at 1:18

Well, for $k$ prime you can use the same argument as $k = 2$: You look at the indices $i_p = k^{p-2}$ for $p$ prime. $k * a_{i_p}$ has $p$ factors and must therefore be of the form $q^{p-1}$ for some prime $q$, but since it is divisible by $k$, $q=k$. So we have an infinite sequence of indices for which $a_n = n$, and we can use the fact that the sequence is increasing to prove $\forall n \space a_n = n $.

Non-prime $k$ is a little trickier, but I think you can do something similar.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.