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.

Find all such sequences $(x_1, x_2, x_3, ..., x_{63})$ consisting of different positive integers that for $n=1,2,3,...,62$ the number $x_n$ is a divisor of $x_{n+1}+1$ and $x_{63}$ is a divisor of $x_1+1$.

Suppose we let $x_{63}=k$. Then we know $x_1 = k+62$.

Our condition is that the last term is a factor of the first term plus 1. Another way of saying that is that

$\frac{k+62+1}{k}= \frac{k+63}{k}$ is an integer. So we have to find all the integer solutions for the equation

A better way of doing it is noticing that we can rewrite the equation as: $k(n-1)=63$

So we know that there are 6 such sequences as there are 6 factors of 63.

And here is the problem: are the sequences of 62+k, 62+k-1, 62+k-2,... the only ones which can fulfill the requirements? I mean, look: $\{1,3,14,27,14039,...,some\_positive\_integer\}$ also does while not being either descending nor having any particular "step". So are the ones I found really the only ones?

share|improve this question
1  
3,2,1,63,62,61,60,...,6,5,4 or any other cyclic shift? –  Jyrki Lahtonen Oct 7 '11 at 17:38

1 Answer 1

up vote 1 down vote accepted

The answer is "Yes". The only sequences are of the form 63+k,62+k,61+k,...,1+k where $k+1$ divides $k+64$ or some cyclic permutation of such a sequence.

To see this notice that the most one can drop is by 1: Suppose $x_n>x_{n+1}$ (and $x_n$ divides $x_{n+1}+1$). This implies that $x_n\geq x_{n+1}+1$ and $x_n \leq x_{n+1}+1$. Thus $x_n = x_{n+1}+1$.

So once you've increased past $x_j=\ell$, the only way to get back down below $\ell$ (further out in the sequence) is $...,x_{i-2}=\ell+2,x_{i-1}=\ell+1,x_{i}=\ell$ (you must "hit" $\ell$ on the way back down).

Suppose your sequence has two increases: $x_i<x_{i+1},...,x_j<x_{j+1}$. If $x_i < x_j$. then we somehow got "back down" from $x_{j+1}$ to $x_i$. Along the way we must have "hit" $x_j$. This violates our "distinct integer" assumption unless $i=j$ (similarly if $x_j>x_i$). So each sequence can only have one "increase". Everything else is a step down by one.

share|improve this answer
    
Thank you but what do you use "l" for? I mean, I don't get the third paragraph when you get to using l and hitting in while going down. Could you please elaborate? –  Pretender Oct 8 '11 at 8:26
    
Think of putting your sequence in a circle. As you step through the sequence you can either increase or decrease. The only way you can decrease is by 1 (as shown in paragraph 2). What I'm saying in the third paragraph is if you increase say from 5 to 9 then later increase again say to 17 eventually (maybe after you've wrapped back around to the beginning) you'll have to go back down from 17 to 9 to 5. But you can only go down by 1 so you'll have at some point 17,16,...,10,9,8,...,6,5,... But this cannot be since now 9 has appeared twice in your sequence! Therefore only one increase is allowed! –  Bill Cook Oct 8 '11 at 22:25
    
OK, I believe I understand now. Thank you a lot! :) –  Pretender Oct 9 '11 at 16:26

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.