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

A number of 10 digits is build up in the following way

  1. Aug 21, 2008 #1
    A number of 10 digits is build up in the following way:

    The first digit is divisible by one.
    The first two digits are divisible by two.
    The first three digits are divisible by three.

    What is the number if 0,1,...,10 can only be used once?

    I can reason that the last digit is 0 and the fifth is 5. How can I find the other ones?
  2. jcsd
  3. Aug 21, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    Re: divisors

    The tenth digit is divisible by 10, so it must be 0. The ninth digit must be divisible by 9, so it must be 9 or 0, but 0 is taken. This should give the answer readily.
  4. Aug 21, 2008 #3
    Re: divisors

    No! The first nine digits are divisible by nine. So this tells us (a1+a2+...+a9)|9.
  5. Aug 23, 2008 #4
    Re: divisors

    That is true, but also every set a1+a2+a3 and a4+5 + a6 , and a7+a8 +a9 must be divisible by 3, every even digit is divisible by 2 the set a3 a4 is divisible by 4 and the set a6,a7,a8 is divisible by 8 and a1a2a3a4a5a6a7 is divisible by 7. That is all the information you need. It figures that both a4 and a8 must be a 2 or 6 since a3 and a7 are odd. Therefore a2 and a6 are each divisible by 4.
  6. Aug 24, 2008 #5
    Re: divisors

    a4 and a8 can be 2,4,6 or 8 right? So if I understand correctly this becomes an integer programming problem?
  7. Aug 24, 2008 #6
    Re: divisors

    That is not what I said. "a4 and a8 must be a 2 or 6 since a3 and a7 are odd" This is because a2,a4,a6 and a8 must each be even so there is no even number left to fit in a3/a7. It is a simple logic problem but you have to try looking at possibilities one at a time. If A8 is a 6 then A7 must be a 9 or 1 to make a6a7a8 divisible by 8 If A7 is a 9 then A9 must be a 3 to make a7+a8+a9 divisible by 3. Also from what I said earlier A4 must be a 2 and a6 must be a 8 to make a4+a5+a6 divisible by 3. This leaves only an 4 to fit in a2. You keep trying possibilities but logic helps speed up the process by narrowing the options. If you run out of possibilities first then you backtrack until you can try a different option that wasn't tried before.
  8. Sep 10, 2008 #7
    Re: divisors

    I read this problem in a different way, that fragments of the number had to satisfy the divisibility requirements. For example, take a ten digit number like 9654873120, where each digit is only used once. Note that 0 is divisible by one, and 20 is divisible by two. 120 is divisible by three, and 3120 is divisible by four. 73120 is divisible by 5, 873120 is divisible by six, 4873120 is divisible by seven, etc.

    It was easy to show from the constraints that the rightmost digit had to be zero, that the next digit had to be even, and even that the leftmost digit had to be a nine. Beyond that, there seemed like a lot of variation was possible, since the criteria mainly affected the least significant digits. For example, the four digit fragment being divisible by 4 only affected the rightmost two digits, and the eight digit fragment being divisible by eight only affects the rightmost three digits, etc. So it seemed time for a little program to see if there were any solutions of the problem stated this way.

    For a ten digit sequence, I was a bit surprised to find there were 202 possible answers. I has expected either many more or much fewer. That would have been more aesthetic, but the universe seems to enjoy disregarding my notions of how it should behave. Good thing too, I suppose.

    I just modified the program to check the problem as it seems to have been commonly interpreted, that the sum of the rightmost digits must be divisible by the number of digits, and for that there are no solutions.
    Last edited: Sep 10, 2008
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook