How to find the sequence?

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

The consecutive elements of the sequence can't be more than 1 smaller compared to the previous as the previous wouldn't be able to be their divisor, then. I mean, this sequence works: $\displaystyle \{62,61,60,...,2,1\}$ because, as a matter of fact, we're still checking divisibility of the same numbers (62 and 61+1 which is 62 and so on) and, as 1 is the 62nd element, it can, of course, divide the first which has to be an integer. As a matter of fact, this should work for every sequence like: $\displaystyle \{k, k-1, k-2,...,1\}$ or even with 2 at the end, supposing k is even. But what else? I'm stuck here.

Re: How to find the sequence?

Hmm... it seems that there are also other possibilites. The last element may be 3 if $\displaystyle x_1+1$ is divisible by 3, 4 if it is divisible by 4 and so on. It seems to be going on infinitely... How should I solve it, then?

Re: How to find the sequence?

Well, you've done a good job so far. Let's formalize what we know a little more:

Suppose we let $\displaystyle x_{63}=k$. Then we know $\displaystyle 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

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

$\displaystyle \frac{k+63}{k}=n$

The question is how to do it. There are finitely many solutions. That should be clear because ultimately the numerator and the denominator will be too close (and thus not be factors) if you proceed too far in either the positive or negative direction. That means trial and error could work if you're patient enough.

A better way of doing it is noticing that we can rewrite the equation as:

$\displaystyle k(n-1)=63$

Find all the pairs of factors, and you will find that this is the same as saying that $\displaystyle k$ must be a factor of 63. Thus we have all the sequences of the form you mentioned whose last term if a factor of 63.

Re: How to find the sequence?

Thank you. But is there any other way to solve the equation you mentioned than plain brute force?

Also, can I write the fact that every element must differ by 1 just out of thin air or I have to prove it somehow? I mean, the problem description doesn't make us work on any monotonic sequence so isn't supposing it's descending by 1 at a time a little like starting from a special case?

Re: How to find the sequence?

Should I just brutally find all the k's using the last equation?

Re: How to find the sequence?

Sorry for not replying earlier... the equation actually allows you to skip the use of brute force. Maybe I didn't make this clear enough. But $\displaystyle k(n-1)=63$, plus our assumptions about $\displaystyle k$ and $\displaystyle n$, means that $\displaystyle k$ and $\displaystyle n-1$ must be integers. Therefore, we KNOW already that $\displaystyle k$ is a factor of 63, without having to do any work.

In terms of the proving that every sequence is of the form you mentioned, I think it's possible, but I haven't thought too deeply about it yet.

Re: How to find the sequence?

Great, thank you. So we know that there are 6 such sequences as there are 6 factors of 63, yes? But can I just leave it like that? I mean, you said that you thought it was possible but is it needed?

Re: How to find the sequence?

Actually, 12, because the negative numbers would also work. I think a proof that only such sequences can work is needed for a good, complete answer. I'll think some more about it.

Re: How to find the sequence?

But the description says "consisting of different positive integers"?

Re: How to find the sequence?

Oh whoops, then yes. Sorry.

Re: How to find the sequence?

OK, thank you.

I'm starting to wonder if the sequences of 62+k, 62+k-1, 62+k-2,... are the only ones which can fulfill the requirements. I mean, look:

$\displaystyle \{1,3,14,27,14039,...,some\_positive\_integer\}$ also does while not being either descending nor having any particular "step". So are the ones we found really the only ones?

Re: How to find the sequence?

This counterexample of mine quite ruined the thinking applied so far for me, didn't it ....?

Re: How to find the sequence?

well, we know that $\displaystyle x_{n+1} = k_nx_n - 1$. so certainly there is no reason to expect $\displaystyle k_n = 1$.

so the only thing left to do is to see if the 2nd condition somehow limits how we can choose the k's.

it should be clear we can't let ALL the k's be greater than 1, or else $\displaystyle x_{63} > x_1+1$ (by quite a bit).

but it could be that the sequence alternates...for example (1,2,1,2,1,...,2,1) would work, as would (1,2,5,4,3,2,1,2,1,2,......,2,1).

without more information, it seems to me there are a LOT of possibilities (as long as we get to a number k ≤ 64 - n on the nth step,

and k = n (mod 2), we can use this construction, and this doesn't exhaust all the possibilities).

however, if the integers used are all distinct, these couldn't be used. i'll need to think for a while to see if that condition precludes all increasing then decreasing sequences.

Re: How to find the sequence?

Quote:

Originally Posted by

**Deveno** but it could be that the sequence alternates...for example (1,2,1,2,1,...,2,1) would work, as would (1,2,5,4,3,2,1,2,1,2,......,2,1).

Nope as the sequences have to be:

Quote:

consisting of different positive integers