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

  • 0
    OK, I believe I understand now. Thank you a lot! :)2011-10-09