More divisibility

[bushindo]

This is an extension of Prime's excellent puzzle

What is the smallest 101-plus-digit number consisting of only 4's, 5's, and 7's that is divisible by '7777.....777' (one hundred 7's)?

The solution *must contain* at least one 4, one 5, and one 7.

EDIT: clarified the properties of the required solution

[Rob_Gandy]

I'm assuming it has to have atleast one 4, 5 and 7?

[bushindo]

I'm assuming it has to have atleast one 4, 5 and 7?

That is correct. I'll edit the OP to clarify that point. Thanks.

[Prime]

This looks harder than the puzzle I posted.

divisibility.pdf

[Prime]

Found a roundabout way to display formatted text inside a BD post. Same thing as above, but visible.

[bushindo]

Found a roundabout way to display formatted text inside a BD post. Same thing as above, but visible.

divisibility.gif

You are approaching this from the correct angle

Breaking the 100 7s into 7 * 100 1s is the right first step. As to the analysis above, I recommend trying some small case like 11 or 111. It shouldn't be hard to find the solution in those cases.

[Prime]

I found this interesting 102-digit number: 490000...000077 (“49”, followed by 98 zeros, followed by “77”.) If you multiply that number by 111...111 (one hundred 1-s), the resulting 201-digit number:

54444...4447555...55547 (“5”, followed by 99 “4-s”, followed by “7”, followed by 98 “5-s”, followed by “47”) meets the conditions set forth in the OP, except I cannot guaranty it is the smallest number that does. (I did not find any simple combination of "1-s" and "0-s", which multiplied by all "7-s" would yeild "4-s", "5-s", and "7-s", while avoiding "8-s".)

On a side note. While playing with these numbers I found a simple yet curious divisibility rule, of which I was not aware before. I should try and construct a problem based on it.

[bushindo]

I found this interesting 102-digit number: 490000...000077 (“49”, followed by 98 zeros, followed by “77”.) If you multiply that number by 111...111 (one hundred 1-s), the resulting 201-digit number:

54444...4447555...55547 (“5”, followed by 99 “4-s”, followed by “7”, followed by 98 “5-s”, followed by “47”) meets the conditions set forth in the OP, except I cannot guaranty it is the smallest number that does. (I did not find any simple combination of "1-s" and "0-s", which multiplied by all "7-s" would yeild "4-s", "5-s", and "7-s", while avoiding "8-s".)

On a side note. While playing with these numbers I found a simple yet curious divisibility rule, of which I was not aware before. I should try and construct a problem based on it.

Excellent work so far. Sorry for not responding earlier. I was on a vacation and didn't have access to a computer

The number above indeed satisfies the conditions giving in the OP, but there is a smaller number. The number I have in mind is a 201-digit number, but the 201-th (leftmost) digit is a 4.

I'm interested in seeing a puzzle based on the divisibility rule you found. For what it is worth, I also based this puzzle on a divisibility rule as well.

[bushindo]

I found this interesting 102-digit number: 490000...000077 (“49”, followed by 98 zeros, followed by “77”.) If you multiply that number by 111...111 (one hundred 1-s), the resulting 201-digit number:

54444...4447555...55547 (“5”, followed by 99 “4-s”, followed by “7”, followed by 98 “5-s”, followed by “47”) meets the conditions set forth in the OP, except I cannot guaranty it is the smallest number that does. (I did not find any simple combination of "1-s" and "0-s", which multiplied by all "7-s" would yeild "4-s", "5-s", and "7-s", while avoiding "8-s".)

On a side note. While playing with these numbers I found a simple yet curious divisibility rule, of which I was not aware before. I should try and construct a problem based on it.

Excellent work so far. Sorry for not responding earlier. I was on a vacation and didn't have access to a computer

The number above indeed satisfies the conditions giving in the OP, but there is a smaller number. The number I have in mind is a 201-digit number, but the 201-th (leftmost) digit is a 4.

I'm interested in seeing a puzzle based on the divisibility rule you found. For what it is worth, I also based this puzzle on a divisibility rule as well.

Solution to the puzzle

If we multiply 100 7's with the following number

 58 571 428 571 428 571 428 571 428 571 428 571 428 571 428 
571 428 571 428 571 428 571 428 571 428 571 428 571 428 571 
428 571 428 602

We would get the following 201-digit number

455 555 555 555 555 555 555 555 555 555 555 555 555 555 555 
555 555 555 555 555 555 555 555 555 555 555 555 555 555 555 
555 555 555 747 777 777 777 777 777 777 777 777 777 777 777 
777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 
777 777 777 777 777 777 754

If you look closely at the number above, you might be able to see the divisibility rule used in the construction of this puzzle.

[Prime]

Indeed, this number is a bit smaller than the one I found.

Perhaps, it is easier to evaluate as 410000...000214: "41", 97 zeros, and "214" (which is, clearly, divisible by 7) multiplied by 100 "1"s.

But where is the proof that it is the smallest number that meets the conditions?

Edited March 9, 2013 by Prime

[bushindo]

Indeed, this number is a bit smaller than the one I found.

Perhaps, it is easier to evaluate as 410000...000214: "41", 97 zeros, and "214" (which is, clearly, divisible by 7) multiplied by 100 "1"s.

But where is the proof that it is the smallest number that meets the conditions?

I can't prove that it is the smallest number. The solution that you posed made me realize that my solution is flawed. Originally, I thought I had a divisibility rule for 100 ones, which allowed me to compute the smallest integer within those rules. The number you came up with made me realize that the divisibility rule I had only worked on a subset of the possible divisors.

So, there might be smaller solutions out there. I made a mistake in an earlier post. I should have called that number "the smallest number that I could find" instead of calling it the solution.

[Prime]

Possibly, you have found the smallest number fitting the conditions in the OP. However, a simple proof/solution does not present itself. When designing new puzzles that comes with the territory.

I appreciate invention of new puzzles. It's a different process from uncovering an answer that has been found before. While playing with this problem I came up with some interesting divisibility rules, which could be used to construct riddles, or break public/private key encryption.

Perhaps, this particular puzzle could be simplified by requiring two digits in the product, rather than three.

The point of giving large numbers, like 100 7s, is to force analytical solution, rather than heuristic approach with actual multiplication or division. Let's construct a number consisting of just 5s and 7s, which is divisible by 100 7s.

First, we note that all 7s divided by 7 yields all 1s, which may be easier to work with. Although, we add a new restriction: multiplier must be divisible by 7.
When multiplying 111...111 by a number, the digits of the product are going to be sums of the digits of the multiplier plus carry, if any. For example, take 525 as a multiplier. The rightmost digit of the product is 5, next one is 5+2=7, after that 5+2+5 resulting in 2, then digit 3 will be repeated: 5+2+5+carry(1). At the left edge, the first 5 will drop out resulting in 5+2+carry(1) = 8, then 2 goes away, leaving 5 as the leftmost digit of the product.
However, we want only 5 and 7 as our product digits. If we carry the leftmost 5 outside 100th digit perimeter putting zeros in the middle, the rightmost 5 shall drop out when the leftmost 5 kicks in. That is, 100 1s multiplied by 101-digit multiplier 5000....00025 will result in 5 on the left and right with a whole bunch of 7s in the middle. Unfortunately, 101-digit number 5000...00025 is not exactly divisible by 7 (yields the remainder of 1.)
Building a number divisible by 7 is an interesting task in itself.

Note the sequence of remainders, the powers of 10 yield when divided by 7:
10⁰ ≡ 1 (mod 7)
10¹ ≡ 3 (mod 7)
10² ≡ 2 (mod 7)
10³ ≡ 6 (mod 7)
10⁴ ≡ 4 (mod 7)
10⁵ ≡ 5 (mod 7)

That sequence of six remainders (1,3,2,6,4,5) is periodic. Curiously, pairs of remainders at the intervals of 3 add up to 7: 1+6=3+4=2+5=7. That leads to many marvelous divisibility rules. E.g., any number with same digits at intervals of 3 is divisible by 7, like 532,532.

So let's build a 101-digit number of the form 500...00200...005, which is divisible by 7. We designate the positions in the large number as 012345,012345,... from right to left. Thus the rightmost 5 is in the position 0 and the leftmost 5 is in the position 5, since 101 ≡ 5 (mod 6). The two 5s add up to the remainder 5*1+5*5=30, or remainder of 2 from division by 7. Now, if place digit 2 in the position 3, we add 2*6=12 to the remainder of 2 for a total of 14, which is divisible by 7.
Thus, 101-digit number 500...002005 is divisible by 7 and when multiplied by 100 1s will result in 3 5s on the right, followed by a whole bunch of 7s, and a bunch of 5s on the left.

Now I want to go back to the sequences of remainders from division of powers of 10 by some prime number greater than 5. Those sequences seem to be a kin to the Little Fermat's Theorem.

Number 13 gives a similar sequence, also of a period 6: (1,10,9,12,3,4). Again, pairs of remainders at interval of 3 add up to 13. And so we know, that a number like 532,532 is divisible by 13 in addition to being divisible by 7. For similar reasons that number is divisible by 11, which has its periodic sequence of length 2: (1,10). However, the fact that 532,532 is also divisible by 19 is purely coincidental.
After a quick study of some other prime number periodic sequences, I can come up with some examples, like 227,772 is divisible by 37. Periodic sequence for 37 being: (1,10,26).
Using those sequences one could come up with a multitude of number tricks.

Since we have been running out of the unproved theorems in Number Theory of late, let me introduce this conjecture:

Prove (disprove) that for any prime number P > 5 as described above, its periodic sequence of remainders is a multiple of P.

Edited March 12, 2013 by Prime