Determining Factors of a 3998-digit NumberDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/