Suppose that we have two operations that we can perform on an integer:
Multiply it by any positive integer.
Delete the 0's in its decimal representation.
Beginning with any positive integer can we always obtain a single-digit number after a finite number of operations? For example, beginning with 7, we can multiply by 15 to obtain 105, delete the 0 to get 15, multiply by 2 to get 30, then delete the 0 to end with 3.
There are numbers that cannot be reduced.
In order to answer the given problem, we can consider a related but simpler one.
In base 2, 7, or 111(2) is an analogue of 999 in base 10, i.e. 999(10), being 2^3-1 rather than 10^3-1.
We need to show that the number of 1's in any multiple of 111(2) can never be less than 3. This would be true if, for some n, (2^n+1) mod 7 = 0. But (2^n+1) mod 7 = {3,5,2}:
2^3+1 9 1001 2 7 111
2^4+1 17 10001 3 14 1110
2^5+1 33 100001 5 28 11100
2^6+1 65 1000001 2 63 111111
2^7+1 129 10000001 3 126 1111110
2^8+1 257 100000001 5 252 11111100
and so the pattern repeats.
Now assume that the second 1 was not at the end, but at some other position in the binary number: say 1(a zeroes)1(b zeros). Since no power of 2 is evenly divisible by 7, both 2 and 7 being prime, such a number would have to be powers of 2 times some smaller number 1(a zeroes)1, that would itself have to be evenly divisible by a multiple of 7. But we have shown already that no such number exists.
Accordingly, 111(2) cannot be reduced to any smaller binary number by the process described.
By parity of reasoning the same must be true of base 10 also.
Edited on September 13, 2019, 12:14 am
|
|
Posted by broll
on 2019-09-12 23:55:04 |
Possible solution
