2
$\begingroup$

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?

  • 1
    3,2,1,63,62,61,60,...,6,5,4 or any other cyclic shift?2011-10-07

1 Answers 1

1

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_ix_i$). So each sequence can only have one "increase". Everything else is a step down by one.

  • 0
    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?2011-10-08
  • 0
    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!2011-10-08
  • 0
    OK, I believe I understand now. Thank you a lot! :)2011-10-09