Ask Me Help Desk

Ask Me Help Desk (https://www.askmehelpdesk.com/forum.php)
-   Mathematics (https://www.askmehelpdesk.com/forumdisplay.php?f=199)
-   -   Hard math problem (https://www.askmehelpdesk.com/showthread.php?t=52942)

  • Jan 7, 2007, 11:56 AM
    mastamilla
    hard math problem
    a buddy of mine likes to post hard math questions on his myspace blog for us to solve. I'm not a math guy but its nice to know the answer so a little help would be great.

    here it is

    Assume x is an integer with many, many digits. In fact, just assume it has a googol digits. What is the minimum number of digits you need to know from x to determine if it is divisible by:

    17?
    40?
    128?
    3125?



    good luck
  • Jan 7, 2007, 12:04 PM
    Capuchin
    Well I can do 40, if the last digit is 0 and the penultimate 2 digits are divisible by 4 then it is divisible by 40.

    i.e.. You need the last 3 digits.

    The other ones I need more time to think about :)
  • Jan 7, 2007, 01:11 PM
    mastamilla
    Well think hard and quick!
  • Jan 7, 2007, 11:08 PM
    dmatos
    128 = 2^7. 10 = (5 x 2).

    To be sure that the number is divisible by 128, you will need the last seven digits. This is because 10^7, and all multiples of 10^7, are divisible by 128.

    Similarly, 3125 = 5^5, so you'll need the last five digits to determine if the number is divisible by 3125.

    17 is a prime number, and will not divide evenly into any multiple of ten. Intuitively, this tells me that you will require all of the digits of the number to determine if it is divisible by 17. Unfortunately, I don't have a rigorous mathematical proof of this.

    BTW - 40 = 5 x 2^3, so you'll need the last three digits, just as Capuchin says.
  • Jan 7, 2007, 11:19 PM
    Capuchin
    I had the same inkling about 17 as dmatos did. If that helps :)
  • Sep 15, 2008, 03:26 PM
    BIGBUG13
    40 : you need to have 3 right digits
    17 : you can't tell and have to see all of it.
    128: you have to have7 the first digits.
    3125:you have to have 5 the first numbers.
    I'm 100% sure.
  • Sep 15, 2008, 04:51 PM
    norma21
    3x+2y=2
    y+8=3x
  • Sep 16, 2008, 01:11 PM
    ebaines
    Quote:

    Originally Posted by BIGBUG13
    40 : you need to have 3 right digits
    17 : you can't tell and have to see all of it.
    128: you have to have7 the first digits.
    3125:you have to have 5 the first numbers.
    I'm 100% sure.

    Interesting problem - I like it, and the solution looks good. However -- no where does the problem state that you are limited to numbers in base 10. So, for example, if the number is given in hexadecimal (base 16), and recognizing that 128 is hexadec 80, you can determine if a number is divisible by 128 with just the last two digits. If the number is given in base 17, the determination of whether its divisible by 17 is trivial.

  • All times are GMT -7. The time now is 12:28 PM.