Thread: Riddle Thread

  1. #1
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312

    Riddle Thread

    Number theory in 21 minutes

    I'm a fan of riddles with mathematical or programming background ("one guard always tells the truth, one guard always lies, and the third guard stabs people who ask tricky questions"). Maybe you like those too. Anyway, this is my favorite, solvable by anyone who finished school:

    p^2 - 1 is divisible by 24 if p is a prime number greater than 3.

    Example:
    5^2 - 1 = 1*24
    7^2 - 1 = 2*24
    11^2 - 1 = 5*24

    Why is that?

    Enjoy,
    Philip
    Last edited by CornedBee; 03-28-2009 at 11:34 AM. Reason: Merging
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  2. #2
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459

    Number theory in 21 minutes

    > Why is that?
    Well for one all prime numbers are odd. And we all know given n (an odd number) n - 1 is even. Providing n > 1 (depending on your definition of zero's oddness).

    Other than that, it's just a pattern. You could of course replace 24 with any other number that 24 is divisible by (der).

    Now all you have to do is prove it inductively -- just to make sure
    Last edited by CornedBee; 03-28-2009 at 11:34 AM.

  3. #3
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312

    Number theory in 21 minutes

    Quote Originally Posted by zacs7 View Post
    Well for one all prime numbers are odd.
    Wrong. 2 is an even prime number.

    And we all know given n (an odd number) n - 1 is even.
    Right. So?

    Greets,
    Philip
    Last edited by CornedBee; 03-28-2009 at 11:34 AM.
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413

    Number theory in 21 minutes

    Quote Originally Posted by Snafuist
    Wrong. 2 is an even prime number.
    I think zacs7 forgot the phrase "within the given range" or "greater than 3".
    Last edited by CornedBee; 03-28-2009 at 11:34 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459

    Number theory in 21 minutes

    > 2 is an even prime number.
    And you specified a range > 3. Last time I checked 2 < 3.

    > Right. So?
    What do you mean so? It's a key property of the pattern.
    Last edited by CornedBee; 03-28-2009 at 11:35 AM.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413

    Number theory in 21 minutes

    Quote Originally Posted by zacs7
    What do you mean so? It's a key property of the pattern.
    Right, but honestly I do not see how it proves the property. Could you elaborate?
    Last edited by CornedBee; 03-28-2009 at 11:35 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459

    Number theory in 21 minutes

    I never said it proved it
    Last edited by CornedBee; 03-28-2009 at 11:35 AM.

  8. #8
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262

    Number theory in 21 minutes

    Take n where
    p = 2*n + 1
    p^2 - 1 = (2*n + 1)*(2*n + 1) - 1 = 4*n*n + 2*2*n + 1 - 1
    = 4*n*n + 4*n = 4*(n*n + n)

    So n*n + n = n*(n+1) must be dividable by 6.

    If n is not dividable by 2, then n+1 is. So now we need to proof n*(n+1) is dividable by 3.

    If n is not dividable by 3, and n+1 is not dividable by 3, then n+2 must be. Then:
    (n+2)*2 = 2*n + 4
    must be dividable by 3. And thus
    2*n + 4 - 3 = 2*n + 1
    must be dividable by 3. However, p = 2*n + 1, and p is a prime number so can't be dividable by 3.

    q.e.d.
    Last edited by CornedBee; 03-28-2009 at 11:35 AM.

  9. #9
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312

    Number theory in 21 minutes

    Right, EVOEx!

    Your proof is technically perfect, but it hides the fundamental ideas, so I will present a simpler version:


    From school, we remember that p^2 - 1 == (p-1)(p+1)

    We want to show that (p-1)(p+1) is dividable by 24, i.e. it's dividable by 2^3 and 3 (the prime factors of 24).

    Now have a look at the three consecutive numbers (p-1), p and (p+1). We know that p is a prime > 3, so (p-1) and (p+1) are even. And what's more, if you have two consecutive even numbers, one of them is also dividable by 4. Thus, (p-1)*(p+1) is dividable by 2*4.

    Another simple fact about numbers is that of three consecutive integers, one of them is dividable by 3. This is not p (as p is a prime greater than 3), so it must be either (p-1) or (p+1).

    Hence, (p-1)*(p+1) is dividable by 2*4 and by 3, i.e. 2*3*4, i.e. 24.

    Greets,
    Philip
    Last edited by CornedBee; 03-28-2009 at 11:35 AM.
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  10. #10
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262

    Number theory in 21 minutes

    Heh. That really was a lot easier.
    Last edited by CornedBee; 03-28-2009 at 11:36 AM.

  11. #11
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312

    Riddle #2: one night in the UAE

    This is taken from my exam in "system architecture":

    Consider the number abcabc, where a, b and c are arbitrary digits. abcabc is always dividable by 13:

    123123 = 13 * 9471
    597597 = 13 * 45969
    666666 = 13 * 51282

    Why is that?

    Greets,
    Philip
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  12. #12
    The larch
    Join Date
    May 2006
    Posts
    3,573

    Riddle #2: one night in the UAE

    Code:
    a_number_in_the_form_of(abcabc) =
     = c + 10 * b + 100 * a + 1000 * c + 10000 * b + 100000 * a =
     = 1001 * c  + 10010 * b + 100100 * a = 
     = 1001 * (c + 10 * b + 100 * a) =
     = 13 * 77 * (c + 10 * b + 100 * a)
    Last edited by CornedBee; 03-28-2009 at 11:36 AM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  13. #13
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312

    Riddle #2: one night in the UAE

    Right, anon!

    Or to put it in simpler terms:
    abcabc = 1001*abc, and 1001 is dividable by 13.

    Where do you guys get those byzantine explanations? :P

    Greets,
    Philip
    Last edited by CornedBee; 03-28-2009 at 11:36 AM.
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  14. #14
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262

    Riddle #2: one night in the UAE

    Quote Originally Posted by Snafuist View Post
    Right, anon!

    Or to put it in simpler terms:
    abcabc = 1001*abc, and 1001 is dividable by 13.

    Where do you guys get those byzantine explanations? :P

    Greets,
    Philip
    Actually, that was the proof I wanted to provide before I read the rest of the posts. However, after typing it in my calculator, I found that "10001" wasn't dividable by 13. I always make those kinds of stupid mistakes....
    Last edited by CornedBee; 03-28-2009 at 11:37 AM.

  15. #15
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312

    Riddle #2: one night in the UAE

    I always make those kinds of stupid mistakes....
    Well, you're not alone. My inability to perform mental arithmetic is famous by now...

    Your brother,
    Philip
    Last edited by CornedBee; 03-28-2009 at 11:37 AM.
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Thread Synchronization in Win32
    By passionate_guy in forum C Programming
    Replies: 0
    Last Post: 02-06-2006, 05:34 AM
  2. [code] Win32 Thread Object
    By Codeplug in forum Windows Programming
    Replies: 0
    Last Post: 06-03-2005, 03:55 PM
  3. Win32 Thread Object Model Revisted
    By Codeplug in forum Windows Programming
    Replies: 5
    Last Post: 12-15-2004, 08:50 AM
  4. Simple thread object model (my first post)
    By Codeplug in forum Windows Programming
    Replies: 4
    Last Post: 12-12-2004, 11:34 PM
  5. Problem : Threads WILL NOT DIE!!
    By hanhao in forum C++ Programming
    Replies: 2
    Last Post: 04-16-2004, 01:37 PM