Results 1 to 14 of 14

Math Help - How to find the sequence?

  1. #1
    Junior Member
    Joined
    Sep 2011
    Posts
    33

    How to find the sequence?

    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.

    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: \{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: \{k, k-1, k-2,...,1\} or even with 2 at the end, supposing k is even. But what else? I'm stuck here.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Sep 2011
    Posts
    33

    Re: How to find the sequence?

    Hmm... it seems that there are also other possibilites. The last element may be 3 if 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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2011
    Posts
    13

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

    \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:
    k(n-1)=63

    Find all the pairs of factors, and you will find that this is the same as saying that 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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Sep 2011
    Posts
    33

    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Sep 2011
    Posts
    33

    Re: How to find the sequence?

    Should I just brutally find all the k's using the last equation?
    Last edited by mr fantastic; October 18th 2011 at 03:26 AM. Reason: Deleted begging for help.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Sep 2011
    Posts
    13

    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 k(n-1)=63, plus our assumptions about k and n, means that k and n-1 must be integers. Therefore, we KNOW already that 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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Sep 2011
    Posts
    33

    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?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Sep 2011
    Posts
    13

    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Sep 2011
    Posts
    33

    Re: How to find the sequence?

    But the description says "consisting of different positive integers"?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Sep 2011
    Posts
    13

    Re: How to find the sequence?

    Oh whoops, then yes. Sorry.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Sep 2011
    Posts
    33

    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:
    \{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?
    Last edited by GGPaltrow; September 26th 2011 at 09:27 AM.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Sep 2011
    Posts
    33

    Re: How to find the sequence?

    This counterexample of mine quite ruined the thinking applied so far for me, didn't it ....?
    Last edited by mr fantastic; October 18th 2011 at 03:26 AM. Reason: Deleted begging for help.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,392
    Thanks
    759

    Re: How to find the sequence?

    well, we know that x_{n+1} = k_nx_n - 1. so certainly there is no reason to expect 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 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.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Junior Member
    Joined
    Sep 2011
    Posts
    33

    Re: How to find the sequence?

    Quote Originally Posted by Deveno View Post
    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:
    consisting of different positive integers
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Find the limit of sequence
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: November 12th 2011, 01:24 PM
  2. [SOLVED] Find an example of a sequence
    Posted in the Calculus Forum
    Replies: 1
    Last Post: October 12th 2011, 03:38 PM
  3. Find a sequence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 25th 2011, 04:21 AM
  4. How to find the formula of this sequence:
    Posted in the Algebra Forum
    Replies: 1
    Last Post: December 4th 2008, 01:57 PM
  5. find the value of a in this sequence
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: September 19th 2008, 09:19 AM

Search Tags


/mathhelpforum @mathhelpforum