Hey there! Sign in to join this conversationNew here? Join for free
    • PS Helper
    • Thread Starter
    Offline

    14
    PS Helper
    Long story short, as a result of having too much free time I seem to have found that if a recurrence relation is defined by x_{n+1} = 2x_n + k\ (\mbox{mod 64}) for some 0 \le k < 64, then eventually we reach a pth term whereby x_p = x_{p+1} = \cdots = 64 - k. I found this when playing around with my PIC programmer with 6 LED outputs and repeatedly pressing sequences of buttons which either double, add 10 to or add 1 to a number.

    Now, I've proven that if x_p = 64 - k then x_{p+1} = 64 - k; that was quite simple, because:
    \newline x_{p+1} = 2x_p + k\ (\mbox{mod 64}) = 128 - k\ (\mbox{mod 64}) = 64 - k
    ...so it follows that if such a p exists, then all following terms are equal.

    My problem now is proving that such a p exists for all x (mod 64). Bear in mind that x, p \in \mathbb{Z}, and we can reduce the problem by saying that 0 \le x < 64, since it's all mod 64... my problem is that I've never encountered a method of proof which allows me to show that something exists for all x.

    If any of you could help, I would appreciate it.
    Offline

    12
    ReputationRep:
    Erm, I think this works, but supposing the first term, x_0, is some number x, then can you find a general term for x_i and then by inspecting this, your answer should be clear, it is true for all x and for all k, unless I've made a horrible mistake....
    what I tried...
    We should find that  x_i \equiv 2^{i}x + (2^{i}-1)k \pmod{64}

    And choosing  i = 6, we find that  x_i \equiv 64x + 64k - k \equiv -k \pmod{64}.
    Offline

    4
    ReputationRep:
    well...i'll leave you to it
    • PS Helper
    • Thread Starter
    Offline

    14
    PS Helper
    (Original post by GHOSH-5)
    Erm, I think this works, but supposing the first term, x_1 is some number x, then can you find a general term for x_i and then by inspecting this, your answer should be clear, it is true for all x and for all k, unless I've made a horrible mistake....
    Let's see...

    The general term seems to be \displaystyle 2^n x + k \sum_{r=0}^{n-1} 2^r. I realise that when n \ge 6 the 2^n x term disappears, since 64x = 0 (\mbox{mod 64}), leaving \displaystyle k \sum_{r=0}^{n-1} 2^r, which itself reduces to 63k for n \ge 7... and since 63k (\mbox{mod 64}) = 64k - k (\mbox{mod 64}) = 64 - k (\mbox{mod 64}), voilà!

    Thanks a lot
    Offline

    12
    ReputationRep:
    (Original post by nuodai)
    Thanks a lot
    No worries

    From where did the question come?

    Side note: For an alternate LateX code for '(mod 64)' or whatever, just '\pmod{64}' sorts it out :smile:
    • PS Helper
    • Thread Starter
    Offline

    14
    PS Helper
    (Original post by GHOSH-5)
    No worries

    From where did the question come?
    From programming a PIC microcontroller, bunging it on a circuit board with a few input buttons and 6 output LEDs*, pushing 3 buttons** in succession repeatedly, watching patterns of lights come up and investigating their properties. As you can see, I'm very cool :yes: I have yet more to investigate... I wonder if I can generalise any results for x_{n+1} = Ax_n + B \pmod C (and I'm guessing that this will have something to do with whether A divides C or not; either way, I'm going to bed now).

    *The LEDs represent integers modulo 64
    **One button doubles the number, another adds 10, another adds 1
    Offline

    12
    ReputationRep:
    (Original post by nuodai)
    From programming a PIC microcontroller, bunging it on a circuit board with a few input buttons and 6 output LEDs*, pushing 3 buttons** in succession repeatedly, watching patterns of lights come up and investigating their properties.
    Sounds quite clever actually. I wondering exactly why you chose the three buttons to have those specific functions though...
    I wonder if I can generalise any results for x_{n+1} = Ax_n + B \pmod C (and I'm guessing that this will have something to do with whether A divides C or not; either way, I'm going to bed now).
    I think you'll be able to find some more results if you rather consider common factors between A and C, rather than just if one divides another, but that could be horribly wrong :tongue: Interesting idea though definitely :smile:
    Offline

    0
    ReputationRep:
    Were am I? Why does my head hurt? Who's ravaged my orifices with mathematical equations during the summer?!
    • PS Helper
    • Thread Starter
    Offline

    14
    PS Helper
    Damn trying to sleep.

    (Original post by GHOSH-5)
    Sounds quite clever actually. I wondering exactly why you chose the three buttons to have those specific functions though...
    There are actually 4 buttons, but only 3 are relevant here. The idea was to have something that could convert decimal numbers to binary. Obviously there was a limit since there are only 6 LEDs, so there was no need for a hundreds button, so I just had a tens and units button. I also had a button which counts up from 0 to 63 in binary, and the double button came just because I wanted to use the 4th button for something, and that seemed appropriate. Whilst messing around with it to see if it worked, I discovered that 2x + 10 + 1 (i.e. pressing the three buttons in succession) always led to the cycle 42-52-53, so I tried it with just 2x + 10 and got 44-54, and with 2x + 10 + 1 + 1 I got 40-50-51-52 and so on.

    (Original post by GHOSH-5)
    I think you'll be able to find some more results if you rather consider common factors between A and C, rather than just if one divides another, but that could be horribly wrong :tongue: Interesting idea though definitely :smile:
    I think you might be right... further investigation pending.
    Offline

    12
    ReputationRep:
    (Original post by nuodai)
    The idea was to have something that could convert decimal numbers to binary.
    That makes sense.
    • PS Helper
    • Thread Starter
    Offline

    14
    PS Helper
    Right, back to work!

    If x_{n+1} = Ax_n + B \pmod C, and we let x_0 = x, then \displaystyle x_n = A^n x + B\sum_{r=0}^{n-1} A^r \pmod C. So, if we have p such that x_p = x_{p+1}, then:
    \newline \displaystyle A^p x + B\sum_{r=0}^{p-1} A^r = A^{p+1} x + B\sum_{r=0}^{p} A^r \pmod C

    Comparing coefficients tells us that A^p = A^{p+1} \pmod C and \displaystyle A^p = 0 \pmod C, meaning that A^{p+1} = 0 \pmod C and so on. As a sidenote, it must follow that A^p = kC, so if we take A, C \in \mathbb{Z}, it means that \dfrac{A^p}{k} = C \Rightarrow A\cdot \dfrac{A^{p-1}}{k} = C \Rightarrow A|C, which is thus a necessary condition for this to occur.

    So, if A|C, we end up with \displaystyle x_p = B\sum_{r=0}^{p-1} A^r \pmod C, which is independent of x, meaning that the starting value does not matter (except for deciding the value of p, which will be lower if x|C than if x \nmid \!\ C).

    If A \nmid \!\ C, we reach a contradiction when we get to the point where A^p = 0 \pmod C, so if this is the case there does not exist p such that x_p = x_{p+1}. However a case may arise where a sum of subsequent powers of A will be zero. For example:
    \newline 3^0 + 3^1 + 3^2 = 3^1 + 3^2 + 3^3 = \cdots = 3^p + 3^{p+1} + 3^{p+2} = 0 \pmod {13}

    In such cases, the sequence of terms will form a cycle. In general, if \displaystyle \sum_{r=0}^{n-1} A^{p+r} = 0 \pmod C, then:
    \newline \displaystyle A^{p+n-1} = -\sum_{r=0}^{n-2} A^{p+r} \pmod C\ (*)\newline

A^{p-1} = -\sum_{r=0}^{n-2} A^{p+r} \pmod C\newline

(*)\ \Rightarrow A^{p-1} = A^{p+n-1} \pmod C\newline

\Rightarrow \boxed{A^p = A^{p+n} \pmod C}
    ... so after the pth term, we get a cycle of period n

    Furthermore, it seems that for all A,C \in \mathbb{Z} then there exist integers n,p such that \displaystyle \sum_{r=0}^{n-1} A^{p+r} = 0 \pmod C (assuming this isn't wrong, how can I prove this?!), meaning that all recurrence relations of the form x_{n+1} = Ax_n + B \pmod C eventually lead to a cycle [and it would make little sense if they didn't lead to a cycle...]

    I have a feeling that at least 50% of this is either wrong or uses flawed logic (I have probably assumed things I should prove, or abused modular arithmetic), so help me out if that's the case.
    Offline

    17
    ReputationRep:
    It's trivial that x_{n+1} = Ax_n + B \pmod{C} leads to a cycle: there are only C possible values for x_n, and so by the pigeonhole principle, after at most C+1 steps, you end up with x_m, x_n with x_m = x_n\, (m > n). It's obvious (and easy to prove) that this implies the sequence repeats.
    • PS Helper
    • Thread Starter
    Offline

    14
    PS Helper
    (Original post by DFranklin)
    It's trivial that x_{n+1} = Ax_n + B \pmod{C} leads to a cycle: there are only C possible values for x_n, and so by the pigeonhole principle, after at most C+1 steps, you end up with x_m, x_n with x_m = x_n\, (m > n). It's obvious (and easy to prove) that this implies the sequence repeats.
    Yes, it seems a lot more obvious now :p: Thanks.
 
 
 
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • Poll
    Would you like to hibernate through the winter months?
    Useful resources

    Make your revision easier

    Maths

    Maths Forum posting guidelines

    Not sure where to post? Read the updated guidelines here

    Equations

    How to use LaTex

    Writing equations the easy way

    Student revising

    Study habits of A* students

    Top tips from students who have already aced their exams

    Study Planner

    Create your own Study Planner

    Never miss a deadline again

    Polling station sign

    Thinking about a maths degree?

    Chat with other maths applicants

    Can you help? Study help unanswered threads

    Groups associated with this forum:

    View associated groups
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

    Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

    Quick reply
    Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.