Conference rusure::math

To test for divisibility by 7, 11, and 13: break the number into groups of 
three digits. Start with the rightmost three, subtract the next 3, add the
next 3, subtract the next 3, ..., then factor the final sum.
 e.g. 
1 234 567 890 -> 890
		-567
		+234
		-  1
		----
		 556=4*139,
so 1234567890 is not divisible by any of (7,11,13).

Performing these operations on any of the solutions of the problem will 
produce a result of 0, the only 3-digit number divisible by all 3.

    Very clever !
    
    It took me a minute to figure why that works, which I finally figured
    this way:
    
    n = a*1000^0 + b*1000^1 + c*1000^2 + d*1000^3
    
    where n is a 10-digit number.
    
    Since modular arithmetic is multiplicative (correct terminology??),
    we can say
    
    n (mod 1001) = a*(1000^0 mod 1001) + b*(1000^1 mod 1001) +
        c*(1000^2 mod 1001) + d*(1000^3 mod 1001)
    
    Since 1000 = -1 (mod 1001), we have
    
    n (mod 1001) = a*(1 mod 1001) + b*(-1 mod 1001) +
        c*(-1^2 mod 1001) + d*(1000^3 mod 1001)
    
    so
    
    n (mod 1001) = a - b + c - d (mod 1001)
    
    Someone PLEASE let me know that I wasn't the only one for whom
    Lynn's .1 wasn't obvious immediately !
    
    Anyway, let's see where this gets us.
    
    Shift meanings of letters, and let
    
    n = abcdefghi0
    
    So we set up
    
    		abc
    	      - def
    	      + ghi
    	      -   0
    	        ---
    		  0
    
    So we have
    
    		abc + ghi - def = 0
    
    Hmmm.  How to arrange the 9 digits.  Well, clearly def has to be
    the largest.  Let's throw in some digits, then try to shift them
    around:
    
    		412 + 536 - 978     (you don't see me shifting digits
    					around in my editor!)
    
    That's not right yet.  Besides, I don't want to use TOO much trial
    and error.
    
    We have
    
    		abc
    	      + ghi
    	      -----
    		def
    
    We know that i is 2,4,6, or 8.
    
    And we haven't used the divisible-by-17 fact at all yet.
    
    For the divisibility by 8, last three digits must be a multiple
    of 8, so we have one of:
    
    120,320,520,720,920,
    240,640,840,
    160,360,560,760,960,
    280,480,680
    
    Hence if i is 2, h is 1,3,5,7, or 9.
    If i is 4, h is 2,6, or 8.
    If i is 6, h is 1,3,5,7, or 9.
    If i is 8, h is 2,4, or 6.
    
    Hmmm.  It's a start.
    
    I suppose next, I might consider the divisibility by 16.
    
    /Eric
    

    My apologies 'cause this ain't pretty.  It's not EXACTLY an exhaustive
    search, though.  I've reduced the size of the solution set from 10!
    (=3,628,800) to 706.  At this point, I'm faced with searching each of
    these elements.  Shall I continue with an explanation?  (Or is it too
    obvious or ugly?) 
     

    Getting it down to about 700 is obvious, since the number(s) have to be
    a multiple of 12252240, hence must end in a zero, hence the smallest
    possibility is 1234567890 and the largest 9876543210.
    
    123#0/122#40 = 105
    987#0/122#40 = 806 	so there are about 700 numbers to sieve thru
    			by some other technique...
    
    /Bevin
          
    PS: For those who want to know where 12252240 comes from
    
    it is 16*9*5*7*11*13*17 = all the prime factors of all the numbers
    from 2 to 18...

    RE: .4
    
    Yup, except 123#0/122#40 = 100.76+, thus 101 through 806 are possible
    multipliers.
    
    RE: .3
    
    Please excuse the mistake: I meant to say "set of possible solutions"
    instead of "solution set".
    

Re .2:    

>   So we have
>		abc + ghi - def = 0

    Actually, that's modulo 1001, so 'def' need not be the largest --
    you could have:
		abc + ghi - def = 1001
    but not
		abc + ghi - def = 2002

Re .4:

>   it is 16*9*5*7*11*13*17 = all the prime factors of all the numbers
>   from 2 to 18...

    Actually, it's the least common multiple of all those numbers. 
    The product of the prime factors is a tad smaller.

    Suppose we allow the digits 0 thru 9, *twice*, to form a number,
    and we want to maximize the smallest number that is not a divisor
    of the number formed (that is, we'd also like to include 19 and
    23 as divisors).  Computers *are* allowed for this one.

The following numbers are multiples of 1 thru 18.

2438195760
3785942160
4753869120
4876391520

The following number is a multiple of 1 thru 40.  What is the other such number?

11978852326735694400

The following number is a multiple of 1 thru 60.  What are the other four such
numbers?

145612640987942683537915732800

I've worded the problem in .7 poorly.  Here's a better attempt:

	Compose a 20-digit number that's a permutation of the digits
	0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9 such that the number
	is divisible by the integers 1 through M.  The number should
	be chosen so that M is as large as possible.

    For 10-digit numbers, M is 18.
    
    This is easily verified by checking that none of the four numbers
    are divisible by 19.
    
    On a VAX computer, the numbers are a wee bit too large for standard
    integer arithmetic.  The following dcl procedure helped:
    
$ dd = p1
$ divisor = f$integer (p2)
$ dividend = 0
$ answer = ""
$ lup:
$ next_answer_digit = dividend / divisor
$ gosub append
$ dividend = dividend - next_answer_digit * divisor
$ gosub bring_down
$ goto lup
$ append:
$ answer = answer + f$string (next_answer_digit)
$ return
$ bring_down:
$ if dd .nes. "" then goto more_left
$ write sys$output f$fao ("!AS r. !ZL", answer, dividend)
$ stop
$ more_left:
$ bring_down_digit = f$extract (0,1,dd)
$ dd = dd - bring_down_digit
$ dividend = dividend * 10 + f$integer (bring_down_digit)
$ return

    /Eric

The following numbers are multiples of 1 thru 18.

2438195760
3785942160
4753869120
4876391520

The following numbers are multiples of 1 thru 40.

11978852326735694400
14281655784729933600

The following numbers are multiples of 1 thru 60.

145612640987942683537915732800
735980516778336415989224421600
750216172948394169357865324800
911663437613582849495072572800
951753913839266257041748826400

     All of the divisibility tests mentioned in this topic are
     essentially derived from one rule:

          If a number M is written in base B, and B == b (mod d),
          then M == m (mod d), where m is the same "digit"
          sequence as M interpreted as being in base b.

     By the last part I mean that if M is written as the n
     "digit" sequence a(n-1)...a(1)a(0) base B, so that

          M = a(n-1)B^(n-1) + ... + a(1)B + a(0)

     then m is the same sequence a(n-1)...a(1)a(0) base b:

          m = a(n-1)b^(n-1) + ... + a(1)b + a(0)

     You just have to be flexible in evaluating numbers written
     in different bases.

     Example 1:  Is 21785 divisible by 3?  Well, 21785 is

          2 : 1 : 7 : 8 : 5 base 10     (M = 21785, B = 10, d = 3)

     and since 10 == 1 (mod 3) let b = 1, then m is

          2 : 1 : 7 : 8 : 5 base 1 = 2+1+7+8+5 = 23

     So 21785 == 23 (mod 3) == 2 (mod 3) and therefore 21785 is
     not divisible by 3.  So all along when you thought you were
     just adding up the digits, you were actually evaluating
     numbers in base 1.

     "But you cheated by using ``digits'' >= the base!"  Hey, I
     told you that you had to be flexible!

     Example 2:  Is 2617 octal divisible by 17?  Well, M is 2617
     octal, B is 8, and d is 17.  Doesn't look good.  But it is
     easy to put M into binary -- 010,110,001,111 -- or, since
     there is no law that the commas must be every third place --
     0101,1000,1111 binary -- or 58F hex.  So M is 58F hex, B is
     16, d is 17.  Let b = -1, because 16 == -1 mod 17.  So m is

          5 : 8 : F base -1 = 5-8+F = 12

     and so M == 12 (mod 17) and so is not divisible by 17.

     Example 3:  The divisibility test for base 10 numbers by 11
     is just as in example 2 but with B = 10, d = 11, b = -1.
     143 base 10 converted to base -1 is 1-4+3 = 0, and 143 is
     indeed divisible by 11.

     Example 4:  What is 1987 mod 25?  Well,

          1 : 9 : 8 : 7 base 10 = 19 : 87 base 100.

     B = 100, d = 25, so let b = 0.  So m is

          19 : 87 base 0 = 87

     because 0^n is 0 for n>0, 0^0 = 1, so any number in base 0
     reduces to the last "digit."  So 1987 == 87 (mod 25) == 12
     (mod 25).  You didn't realize that when you looked at a
     decimal number's least significant digit, saw it was even,
     and concluded the number was even, that you were doing an
     evaluation in base 0 (B = 10, d = 2, b = 0)!

     Example 5:  The combined test for 7, 11, and 13 used B = 1000,
     b = -1, d = 7 or 11 or 13.

     Using all of this you can actually derive a tortured test
     for divisibilty (of decimal numbers) by 17.  Since 10^8 == -1
     (mod 17), first split the number into blocks of eight digits
     (rewrite it in base B = 10^8) and alternately add and
     subtract them (convert to base -1).  If the result is a
     little over eight digits, do this again.  For instance,

          M = 27645,81945607,32098661
          m = 27645 - 81945607 + 32098661 = -49819301
          M == m (mod 17)

     Now write m in base 100, and use 100 == -2 (mod 17)

          m = - 49: 81: 93: 01 base 100
          mm = -49 : 81 : 93 : 01 base -2
             = -(49 * (-8) + 81 * (4) + 93 * (-2) + 01 * (1))
             = 392 - 324 + 186 - 1 = 68 + 185 == 100 (mod 17)
               (because 68 and 85 are divisible by 17) == -2 (mod 17)

     So M == -2 (mod 17) or M == 15 (mod 17).  If you are good
     with numbers this may even be faster than doing the long
     division!

     Dan