bushindo 14 Report post Posted February 11, 2013 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 Quote Share this post Link to post Share on other sites
0 Rob_Gandy 2 Report post Posted February 11, 2013 I'm assuming it has to have atleast one 4, 5 and 7? Quote Share this post Link to post Share on other sites
0 bushindo 14 Report post Posted February 12, 2013 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. Quote Share this post Link to post Share on other sites
0 Prime 15 Report post Posted February 15, 2013 This looks harder than the puzzle I posted. divisibility.pdf Quote Share this post Link to post Share on other sites
0 Prime 15 Report post Posted February 15, 2013 Found a roundabout way to display formatted text inside a BD post. Same thing as above, but visible. Quote Share this post Link to post Share on other sites
0 bushindo 14 Report post Posted February 15, 2013 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. Quote Share this post Link to post Share on other sites
0 Prime 15 Report post Posted February 16, 2013 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. Quote Share this post Link to post Share on other sites
0 bushindo 14 Report post Posted February 19, 2013 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 computerThe 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. Quote Share this post Link to post Share on other sites
0 bushindo 14 Report post Posted March 9, 2013 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. Quote Share this post Link to post Share on other sites
0 Prime 15 Report post Posted March 9, 2013 (edited) 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 Quote Share this post Link to post Share on other sites
0 bushindo 14 Report post Posted March 11, 2013 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. Quote Share this post Link to post Share on other sites
0 Prime 15 Report post Posted March 12, 2013 (edited) 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^{0} ≡ 1 (mod 7) 10^{1} ≡ 3 (mod 7) 10^{2 }^{}≡ 2 (mod 7) 10^{3} ≡ 6 (mod 7) 10^{4} ≡ 4 (mod 7) 10^{5} ≡ 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 Quote Share this post Link to post Share on other sites
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
Share this post
Link to post
Share on other sites