Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question

1 Answer 1

up vote 10 down vote accepted

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$.

share|improve this answer
    
where is waranty that i could find such number? –  Savinov Evgeny Oct 21 '11 at 12:34
    
@SavinovEvgeny: The Chinese remainder theorem: $2k+1$ and $2k+2$ are relatively prime. –  Brian M. Scott Oct 21 '11 at 12:40
    
Ok, I know that they are relatively prime. But i cant understand how I should use this fact now. Can you explain? –  Savinov Evgeny Oct 21 '11 at 12:42
1  
@SavinovEvgeny: en.wikipedia.org/wiki/Chinese_remainder_theorem gives a constructive algorithm to solve the problem –  Ross Millikan Oct 21 '11 at 13:39
    
@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. –  Michael Hardy Oct 21 '11 at 15:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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