Determining Factors of a 3998-digit Number

Date: 08/11/99 at 01:31:43
From: Brad Goorman 
Subject: Determining Factors of a 3998-digit Number

Dear Dr. Math

I started this problem and I have 3 of the 4 integers needed to 
complete it. Can you help me?

Let N = 111...1222...2, where there are 1999 digits of 1 followed by 
1999 digits of 2. Express N as the product of four integers, each of 
them greater than 1.

Answer:
I first did some experimentation with smaller cases.  This is what I 
found using MAPLE.

> ifactor(1122);
                                         (2) (3) (11) (17)
> ifactor(111222);
                                               2
                                        (2) (3)  (37) (167)
> ifactor(11112222);
                                     (2) (3) (11) (101) (1667)
> ifactor(1111122222);
                                   (2) (3) (7) (41) (271) (2381)

> ifactor(111111222222);
                                      2
                               (2) (3)  (7) (11) (13) (37) (166667)
> ifactor(11111112222222);
                                 (2) (3) (47) (239) (35461) (4649)
> ifactor(1111111122222222);
                       (2) (3) (11) (19) (73) (101) (137) (739) (1187)
> ifactor(111111111222222222);
                                    3
                             (2) (3)  (37) (43) (983) (333667) (3943)
> ifactor(11111111112222222222);
                           (2) (3) (11) (41) (271) (1666666667) (9091)
> ifactor(1111111111122222222222);
                         (2) (3) (7) (1543) (1543067) (513239) (21649)
> ifactor(111111111111222222222222);
                             2
               (2) (3)  (7) (11) (13) (37) (101) (166666666667) (9901)
> ifactor(11111111111112222222222222);
                 (2) (3) (53) (79) (265371653) (328121) (2287) (2221)

Since the number is even, 2 is always one of the factors. I think it 
should be possible to analyze the cases and show that 3 is always a 
factor. I can see why 11 is a factor if the number of 1's is even. In 
the case that I am interested in, maybe I can show that 7 is a factor. 
Then since 2, 3, and 7 are prime numbers, if each one is a factor 
separately, their product must be a factor, and the final factor is 
what is left over. I'm sorry but I can't figure out what the other 
factor is. If you can, would you please help me?

Sincerely,
Brad Goorman

Date: 08/21/99 at 16:44:14
From: Doctor Twe
Subject: Re: Determining Factors of a 3998-digit Number

Hi Brad!

There are some shortcuts to see if a number is evenly divisible by 
certain integers. You've already mentioned one: If the value is even 
(ends in 0, 2, 4, 6, or 8), it is divisible by 2.

Here are some others:

- If the sum of the digits is a multiple of 3 (3, 6, 9, 12...), the 
  number is divisible by 3. (This can be done recursively - that is, 
  if the sum of the digits of the sum of the digits is a multiple of 
  3, the number is divisible by 3, etc.)

- If the value of the last two digits is divisible by 4, the number 
  is divisible by 4. (For example, 7876 is divisible by 4 because 
  76/4 = 19.)

- If the number ends in 5 or 0, it is divisible by 5.

- If the number is divisible by 2 and 3 (as tested by the methods 
  above), it is divisible by 6.

- If the value of the last three digits is divisible by 8, the number 
  is divisible by 8. (For example, 9336 is divisible by 8 because 
  336/8 = 42.)

- If the sum of the digits is a multiple of 9 (9, 18, 27...), the 
  number is divisible by 9. (This can be done recursively - that is, 
  if the sum of the digits of the sum of the digits is a multiple of 
  9, the number is divisible by 9, etc.)

- If the number ends in 0, it is divisible by 10.

- There is a "test" for divisibility by 7 as well, but it would be 
  pretty complicated to apply to your number. It goes like this: 
  Beginning with the leftmost digit, multiply each digit by 3 and add 
  the next digit. Multiply the result by 3 and add the next digit, 
  etc. If the final sum is a multiple of 7, then the original number 
  is a multiple of 7. For example, 8162 is divisible by 7 because 
  [(8*3+1)*3+6]*3+2 = 245, which is 7*35. (You could re-apply the rule 
  to test 245 if you weren't sure.)

- There is a similar rule for 11: Beginning with the leftmost digit, 
  negate each digit (reverse the sign, or multiply it by -1) and add 
  the next digit. Negate the result and add the next digit, etc. If 
  the final sum is a multiple of 11, the original number is a multiple 
  of 11.

Using these shortcuts we can confirm that your number is indeed a 
multiple of 2 (it's even) and 3 (since there are the same numbers of 
1's and 2's in the number, each 'pair' adds to 3). We can also quickly 
see that 4, 5, 8 and 11 won't work. (With 11, the first 1998 1's add 
to 0 using the method; then the next steps would be -(1)+2 = 1, 
-(1)+2 = 1, etc. We can see that this would end in 1.)

I'm not sure of a way to "shortcut the shortcut" for 7's, but if 7 
indeed works, then the final factor is simply N/(2*3*7).

If I come up with another way to figure out the third factor (whether 
or not it's 7), I'll let you know!

- Doctor TWE, The Math Forum
  http://mathforum.org/dr.math/   

Date: 09/13/1999 at 18:49:35
From: Doctor Twe
Subject: Re: Determining Factors of a 3998-digit Number

Hi again, Brad!

Note: For the purposes of this discussion, I'll use the following 
notation: 1..{4}..1  =  111111 (i.e., the number in braces {} is the 
number of repetitions NOT counting the end ones shown).

I thought some more about your problem and came up with more ideas. 
First, 7 is NOT a factor. In order to see why, let's look at a simpler 
example. Suppose that we wanted to see if 7 was a factor of 141,435. 
This is the same as asking if 141,435 is a multiple of 7. Is there 
some value x such that 7*x = 141,435 ?  We can break this into parts. 
We know that 7*2 = 14, so 7*20,000 = 7*2*10,000 = 140,000. Likewise, 
7*200 = 7*2*100 = 1,400.  Finally, we know that 7*5 = 35. Why did we 
pick these values? Because we saw that the number 141,435 started with 
a 14... (which we recognized as a multiple of 7). So:

     141,435 =   140,000 =   7*2*10,000
               +   1,400 = + 7*2*   100
               +      35 = + 7*5*     1

We now know that the top number (7*2*10,000) is a multiple of 7, the 
second number (7*2*100) is a multiple of 7, and the bottom number 
(7*5) is a multiple of 7. Since our original number, 141,435 is the 
sum of these numbers, it, too, must be a multiple of 7. Algebraically, 
7*x+7*y+7*z = 7*(x+y+z).

Using this strategy, we can "remove" the 14 from the front. 141,435 is 
a multiple of 7 only if 1,435 is a multiple of 7. Then we can "remove" 
the next 14. 1,435 is a multiple of 7 only if 35 is a multiple of 7. 
We could do this for larger numbers, too - which we'll need to do for 
the problem you sent us, as follows:

Since 111111 = 15873 * 7, i.e. 111111 is a multiple of 7, thus 
1111110..{n}..0 = 158730..{n}..0 * 7, and is also a multiple of 7. So 
if 1111111..{1991}..12..{1997}..2 (your number N) is divisible by 7, 
then

        1111111..{1991}..12..{1997}..2   (your number N)
     -  1111110........{3990}........0   (a multiple of 7)
        ------------------------------
              1..{1991}..12..{1997}..2

must also be a multiple of 7. Similarly, if 1..{1991}..12..{1997}..2 
is divisible by 7, then

        1111111..{1985}..12..{1997}..2   (the previous step's value)
     -  1111110........{3984}........0   (a multiple of 7)
        ------------------------------
              1..{1985}..12..{1997}..2

must also be a multiple of 7. We can continue to "remove" groups of 
six 1's in this manner. After 333 such removals, we come to the 
conclusion that 12..{1997}..2 must be a multiple of 7.

Since 12222 = 1746 * 7, i.e. 12222 is a multiple of 7, thus 
122220..{n}..0 = 17460..{n}..0 * 7, and is also a multiple of 7. So if 
12..{1997}..2 (the previous step's value) is divisible by 7, then

        122222..{1993}..2   (the previous step's value)
     -  122220..{1993}..0   (a multiple of 7)
        ------------------------------
             2..{1993}..2

must also be a multiple of 7.

Since 222222 = 31746 * 7, ie. 222222 is a multiple of 7, thus 
2222220..{n}..0 = 317460..{n}..0 * 7, and is also a multiple of 7. So 
if 2..{1993}..2 (the previous step's value) is divisible by 7, then

        2222222..{1987}..2   (the previous step's value)
     -  2222220..{1987}..0   (a multiple of 7)
        ------------------------------
              2..{1987}..2

must also be a multiple of 7. We can continue to "remove" groups of 
six 2's in this manner. After 332 such removals, we come to the 
conclusion that 222 must be a multiple of 7. But clearly 222 is not a 
multiple of 7, so neither is your original number N.

Whew!

I discussed your problem with my wife, and she came up with the 
obvious (AFTER you think of it) third factor. She said "wouldn't 
1..{1997}..1 be a factor?" Of course! It goes into the "front half" 
once, and the "back half" twice. So N / 1..{1997}..1 = 10..{1996}..02. 
The fourth factor, then, becomes 10..{1996}..02 / 6.  The division 
isn't too difficult because of the repeated digits in the middle. I'll 
leave it to you to finish it, but write back if you get stuck.

A final note: I didn't check whether or not the third and fourth 
factors are primes. If either one is not prime, there are other 
possible solutions.

Good luck!

- Doctor TWE, The Math Forum
  http://mathforum.org/dr.math/