3816547290

A Special Number: the only one in which

3 is divisible by 1,
38 is divisible by 2,
381 is divisible by 3,
3816 is divisible by 4,
38165 is divisible by 5,
381654 is divisible by 6,
3816547 is divisible by 7,
38165472 is divisible by 8,
381654729 is divisible by 9,
3816547290 is divisible by 10.

How would one go about finding 3816547290? It's not easy to google for it. You have two basic options:

The High Road: Mathematical deduction

This isn't the "fun" way. I will use basic, accessible language to walk you through one method for finding the answer.

Some Definitions and Rules

D(i)

Let's call each digit of the number D(i), where i is the position from the left, starting at one.

In 3816547290, D(2)=8, for example.

I will also use D(i,j,k) as shorthand for "the ordered set of D(i), D(j), D(k)."

N(i)

N(i) will mean all the digits from the beginning up to position i.

N(2)=38, for example.

Using this language, you can restate the problem by saying that N(i) must be divisible by i for all i=1..10.

I will also use N(i,j,k) as shorthand for "the ordered set of N(i), N(j), N(k)."

division by 3

If a number is divisible by three, then the sum of its digits is divisible by three.

N(3)
is divisible by three if
D(1) + D(2) + D(3)
is divisible by three, for example.

division by 2^n

A number is divisible by 2^n if its last n digits are divisible by 2^n.

7777772 is divisible by 2 because its last (2^1, n=1) 1 digit is divisible by 2.
7777712 is divisible by 4 because its last (2^2, n=2) 2 digits are divisible by 4.
D(2) is divisible by 2 if N(2) is divisible by 2.
D(4) is divisible by 4 if N(3)*10+N(4) is divisible by 4.

The First Half of the Problem

  1. All multiples of ten end in 0. For N(10) to be divisible by 10, the last digit D(10) must be 0.
  2. All multiples of five end in 0 or 5. N(5) has to be divisible by five, and we can only use each digit once, so D(5)=5.

    Already we have eliminated two of the ten digits: 1234567890.

  3. All multiples of two must be even. N(2,4,6,8) have to be divisible by multiples of 2, so they have to be even. If D(2,4,6,8,10) are all even, that means that the other digits have to be odd.

    There are now two subsets to consider: {2,4,6,8} for D(2,4,6,8) and {1,3,7,9} for D(1,3,7,9).

  4. N(4) is divisible by 4. From the "division by 2^n rule", above, D(3)*10 + D(4) has to be divisible by 4.

    For the possible scenarios 1_, 3_, 5_, 7_, 9_, there are only two only possible digits you can put in the blanks to make any of these numbers divisible by four: 2 and 6. (This is because any odd number times ten will only have one multiple of two, the 2 in 2*5. The remainder modulus four will always be 2, so you must pick a D(4) whose remainder is -2 modulus four.)

    D(4) must be either 2 or 6.

    N(3), N(6), and N(9) are all divisible by multiples of 3. From the "division by 3" rule, above, we know that D(1)+D(2)+D(3) is divisible by 3, as are D(1)+D(2)+D(3)+D(4)+D(5)+D(6) and D(1)+D(2)+D(3)+D(4)+D(5)+D(6)+D(7)+D(8)+D(9). We can eliminate subsections of these equations divisible by three to generate new rules:

    D(1)+D(2)+D(3)
    D(1)+D(2)+D(3)+D(4)+D(5)+D(6)
    D(1)+D(2)+D(3)+D(4)+D(5)+D(6)+D(7)+D(8)+D(9)
    

    Now, we know D(4) is either 2 or 6, and we know D(5) is 5, so finding out that D(4)+D(5)+D(6) must be divisible by three limits fairly tightly what D(6) can be.

    If D(4) is 2, D(4)+D(5)+D(6)=7+D(6), and D(6) must be even. There is only one even number that would make 7 + D(6) divisible by three: 8. D(4,5,6) would then be "258".

    If D(4) is 6, D(4)+D(5)+D(6)=11+D(6), and D(6) must be even. There is only one even number that would make 11 + D(6) divisible by three: 4. D(4,5,6) would then be "654".

    Let's try both possibilities.

If the middle digits are "258"

The number now looks like ___258___0.

  1. N(8) is divisible by 8, so according to the "division by 2^n" rule, D(6)*100+D(7)*10+D(8)=8*100+D(7)*10+D(8) must be divisible by eight. 8*100=800 is divisible by eight, so it can be eliminated, leaving us 8*100+D(7)*10+D(8).

    With our assumption that the middle digits are "258", the only even digits remaining that D(8) could be are 4 and 6. For the possible scenarios 1_, 3_, 7_, 9_, no blank can be filled in with 4 to make a number divisible by eight, so D(8)=6.

    Since we used up 6, D(2) must be the only even digit left: 4.

  2. There are four blanks left: _4_258_6_0. We determined earlier that D(7)+D(8)+D(9) must be divisible by three. The only odd numbers for D(7,9) to satisfy D(7)+6+D(9) are 3 and 9.

    Let's generate all the possible answers and test each one, where D(7,9) are 3 or 9.

     D(7)=3, D(9)=9
    1472583690  -- N(8) not divisible by 8
    7412583690  -- N(7) not divisible by 7
    
     D(7)=9, D(9)=3
    1472589630  -- N(7) not divisible by 7
    7412589630  -- N(7) not divisible by 7
    

It makes sense that the N(7) test fails, because we haven't examined that digit at all in the process. Let's try the other possibility.

If the middle digits are "654"

Well, if there's an answer, this possibility will lead us to it. The number now looks like ___654___0.

  1. As before, N(8) is divisible by 8, so D(6)*100+D(7)*10+D(8)=4*100+D(7)*10+D(8) must be divisible. 400 is divisible by eight, so we can eliminate it: 4*100+D(7)*10+D(8).

    D(8) can only be 2 or 8, because we've used the other even digits. For 1_, 3_, 7_, 9_, an 8 can never fill in any blank to make a number divisible by eight, so D(8)=2.

    Since we've used up all the other even digits, D(2)=8.

  2. There are four blanks left: _8_654_2_0. For D(7)+D(8)+D(9)=D(7)+2+D(9) to be divisible by three, where D(7,9) are odd numbers, D(7,9) can be 1 and 3, 3 and 7, or 7 and 9. Let's try each possibility.
      Trying 1 and 3
     D(7)=1 D(9)=3
    7896541230 -- N(7) not divisible by 7
    9876541230 -- N(7) not divisible by 7
    
     D(7)=3 D(9)=1
    7896543210 -- N(7) not divisible by 7
    9876543210 -- N(7) not divisible by 7
    
      Trying 3 and 7
     D(7)=3 D(9)=7
    1896543270 -- N(7) not divisible by 7
    9816543270 -- N(7) not divisible by 7
    
     D(7)=7 D(9)=3
    1896547230 -- N(7) not divisible by 7
    9816547230 -- N(7) not divisible by 7
    
      Trying 7 and 9
     D(7)=7 D(9)=9
    1836547290 -- N(7) not divisible by 7
    3816547290 -- THE ANSWER
    
     D(7)=9 D(9)=7
    1836549270 -- N(7) not divisible by 7
    3816549270 -- N(7) not divisible by 7
    
It wasn't easy, but we found out the "scholarly" way, and we know we've found the only one. Now let's turn to the way of the impatient.

The Low Road: Brute Force

You might just consider trying all the permutations instead. It's quite time-intensive, but works. The method below tries all 10!, or ca. 3.6 million, possibilities. This sample Perl session took several (real) minutes to run on a fairly fast computer:

tcsh% time perl
#!/usr/local/bin/perl
my @possibilities = permutations(0..9);

foreach my $possibility (@possibilities) {
  print "$possibility\n" if works( $possibility);
}

sub permutations {
  my (@a) = @_;

  return $a[0] if @a==1;
  my @ret;

  for ( my $i=0; $i < @a; $i++) {
    push @ret, map $a[$i].$_, permutations( @a[ grep $_!=$i, 0..@a-1 ] );
  }
  return @ret;
}

sub works {
  my $num = shift;

  foreach (my $i=1; $i <= 10; $i++) {
    return 0 unless ( (substr $num, 0, $i ) % $i == 0 );
  }
  return 1;
}
__END__
3816547290
494.520u 9.480s 12:45.64 65.8%  0+0k 0+0io 0pf+0w

The first line returns our answer; the second shows how long it took. Since only one answer was returned, we know there's only one solution.

All you're missing now is the division rule for seven...

Log in or register to write something here or to contact authors.