2
$\begingroup$

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.

  • 0
    Do you have even one example? (other than $1,2,3,4,\dots$)2011-05-04
  • 1
    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: http://www.artofproblemsolving.com/Forum/viewtopic.php?t=404273. I was trying to find the general form of this problem.2011-05-04
  • 0
    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?2011-05-04
  • 0
    I've edited the problem. But the case $k=2$ is not very hard and can be solved. I was searching for the solution of generalization of this problem. (and also, can't I ask questions which I don't know their answers? If I can, then what do you mean?)2011-05-04
  • 4
    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.2011-05-04
  • 3
    @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.2011-05-05
  • 0
    OK. Sorry about that. I will post in that way. But have you found anything for the problem? (generalization, I mean)2011-05-05

1 Answers 1

2

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.