8
$\begingroup$

Does there exist a sequence $a_n$ which consists of every natural number and for each $N$, $\sum\limits_{k=1}^N a_k$ is divisible by $N$?

1 Answers 1

10

Yes.

You start with $3,1$.

Now, you suppose that you have already found the first $2k$ numbers of your sequence.

Put the smallest natural number that has not yet been used in place $2k+2$ and then find a number that has the right rest modulo $(2k+1)(2k+2)$ in place $2k+1$ so that both the sums up to $a_{2k+1}$ and $a_{2k+2}$ have the right divisibility properties.

The first action ensures that all natural numbers are used eventually. The second ones ensures that the divisibility conditions are fulfilled and uses the fact that consecutive integers are relatively prime.

The above construction starts out with:

3,1,14,2,30,4

Edited to add: The condition on the first $2k+1$ numbers tells you that $a_{2k+1}$ has a certain rest modulo $2k+1$, the condition on the first $2k+2$ numbers tells you that it has a certain rest modulo $2k+2$. By the Chinese remainder theorem, you can combine these conditions to a certain rest modulo $(2k+1)(2k+2)$. Since there are infinitely many numbers that have a certain rest and you have only used finitely many at the moment, you can find a number that works.

Example for $a_3=x$:

I have already fixed $3,1,x,2$.

So 3 has to divide $x+4$ and 4 has to divide $x+6$.

Therefore $x$ has rest 2 modulo 3 and rest 2 modulo 4 which is equivalent to being 2 modulo 12. The first such number, 2, has already been taken, so I take the second number $2+12=14$.

  • 0
    @Phira: I entered 3,1,14,2,30,4 into the search box at the Online Encyclopedia of Integer Sequences and it's not there. Maybe you should consider adding it.2011-10-21