Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Another pattern

  1. May 17, 2005 #1
    This is another puzzle that has to do with modular arithmetic (the other one that did was Picture Puzzle).

    1
    1 2
    1 3 2 4
    1 4 5 2 3 6
    1 6 4 3 9 2 8 7 5 10

    What's the next row?
     
  2. jcsd
  3. May 18, 2005 #2
    Answer in white at bottom and side of possible missing row. Though I'm guessing it's not quite right... though hopefully on the right track.
    Are you missing a row here?

    1
    1 2
    1 3 2 4
    1 4 5 2 3 6
    0 0 0 0 0 0 0 0 - Missing Row??? 1 5 3 7 2 6 4 8
    1 6 4 3 9 2 8 7 5 10
    1 7 8 4 5 11 2 9 3 10 6 12
     
  4. May 19, 2005 #3
    Nope, that's not it.

    No, it's not missing a row. The row lengths are 1, 2, 4, 6, 10, 12, 16, 18...
     
  5. May 19, 2005 #4
    1
    1 2
    1 3 2 4
    1 4 5 2 3 6
    1 6 4 3 9 2 8 7 5 10
    1 7 9 10 5 11 2 8 4 3 6 12 ???

    The only ones I think I have correct for sure are :

    1 7 0 0 0 0 2 0 0 0 6 12

    Is that correct?
     
  6. May 19, 2005 #5
    Yes--those five numbers are are correct. You actually have several of the others correct, too, but you don't have the row.
     
  7. May 19, 2005 #6
    1 7 9 10 5 11 2 8 4 3 6 12

    1
    1 2
    1 3 2 4
    1 4 5 2 3 6
    1 6 4 3 9 2 8 7 5 10
    1 7 3 4 5 11 2 10 9 8 6 12

    How about that?

    I think these ones are correct for sure :

    1 7 3 4 0 11 2 0 0 0 6 12
     
  8. May 19, 2005 #7
    No, not all of those are correct.
     
  9. May 19, 2005 #8

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    1 7 5 4 3 11 2 10 9 8 6 12

    WARNING: Potential answer below.

    The first number is 1
    The last number is the greatest, and is 1 less than the next prime, e.g. the last line of the puzzle went up to 10, which is 1 less than 11. The next prime after 11 is 13, so the new line must go up to 12.
    The second number, s, is such that 2s - 2 is the greatest number.
    All the numbers are arranged such that if you made the list:
    A1 A2 A3 ... An
    where Ai is the position of i in the original list, you'll get back the original list.
    The second last number is half the last number.
    Whatever remains is "reversed." The example below will clarify
    So, the next prime is 13, we start with:

    1 2 3 4 5 6 7 8 9 10 11 12

    7 is the number such that 2*7 - 2 = 12. So 7 must go in the second spot, and by the stuff with that A1 A2, ... we know that 2 must take the place 7 did, so we get:

    1 7 3 4 5 6 2 8 9 10 11 12

    The second last number must be half the last, so 6 and 11 switch places

    1 7 3 4 5 11 2 8 9 10 6 12

    Now the examples that preceeded this didn't really have enough numbers to tell us what to do with the rest of the numbers. The very last line, the one that goes up to 10, has 4 3 instead of 3 4 and 8 7 instead of 7 8, so I figure we just reverse those remaining numbers, so we get:

    1 7 5 4 3 11 2 10 9 8 6 12
     
    Last edited: May 19, 2005
  10. May 19, 2005 #9
    Nice reasoning, AKG--yes, it is important that the length of each line is 1 less than a corresponding prime. But you don't have the answer. The answer is very simple, and has to do with modular arithmetic.

    Also, here is a hint: consider writing the numbers 1 ... n above each line.
     
  11. May 19, 2005 #10
    I think I've got it.

    1
    1 2
    1 3 2 4
    1 4 5 2 3 6
    1 6 4 3 9 2 8 7 5 10
    1 7 5 4 3 11 2 10 9 8 6 12

    What do you think? Want an explanation?
     
  12. May 20, 2005 #11
    1 7 10 9 8 11 2 5 4 3 6 12 ?
     
  13. May 20, 2005 #12

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Oh, I see.

    1 7 9 10 8 11 2 5 3 4 6 12
     
  14. May 20, 2005 #13

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Some remarks:

    Since multiplication modulo n is commutative, that's why the rule:

    All the numbers are arranged such that if you made the list:
    A1 A2 A3 ... An
    where Ai is the position of i in the original list, you'll get back the original list.


    holds. Obviously, the only element x such that x*1 = 1 (mod p) is x=1, which is the rule:

    The first number is 1

    holds. The last number is the number x such that x*(p-1) = 1 (mod p)

    x*(p - 1) = xp - x (mod p)
    = -x (mod p)
    = 1 (mod p)

    so x+1 = 0 (mod p), and clearly p-1 is the only x that satisfies this, which is why

    The last number is the greatest

    holds. I said that the second number was the number such that:

    The second number, s, is such that 2s - 2 is the greatest number.

    The greatest number is just p-1, so

    2s - 2 = p - 1
    2s = p + 1

    so

    2s = 1 (mod p)

    Of course, the second number must be the s that satisfies 2s = 1 (mod p), since the pattern is that the kth number is the one that satisfies xk = 1 (mod p), so this is why that rule holds.

    The last rule that might be right is:

    The second last number is half the last number.

    That would be 0.5(p-1). So, is 0.5(p-1) the unique element that will satisfy

    0.5(p-1)(p-2) = 1 (mod p) ?

    0.5(p-1)(p-2) = 0.5(p² - 3p + 2) (mod p)
    = p(p - 3)/2 + 1 (mod p)

    and (p-3)/2 is a natural number because p-3 is even, which is because p is odd, which is because it's prime. The exception is p=2, but in that case, we wouldn't be talking about the "p-2" position anyways. So (p-3)/2 = n, some natural number

    = pn + 1 (mod p)
    = 1 (mod p)

    as desired.

    The final rule I gave, that the remaining elements are just written backwards, was just wrong anyways.
     
  15. May 20, 2005 #14
    Right, AKG! In other words, the mth row is the ordered list of multiplicative inverses of the integers mod the mth prime, with the 0th element omitted from each list since it has no multiplicative inverse. The reason it's only mod _primes_ is that the integers mod nonprimes are not fields (do not have multiplicative inverses for every nonzero element).
     
  16. May 20, 2005 #15
    :frown:
    I thought for sure I had it; but I reversed some of the numbers I guess. I don't know as much about math as I'd like.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Another pattern
  1. Interesting Pattern (Replies: 10)

  2. Patterns (Replies: 6)

  3. Baking Pan Patterns (Replies: 6)

Loading...