A shrinkable number is one that can be reduced to a single digit by the following process:
Create a new number where each digit is the absolute difference between consecutive digits.
Repeat until you have a single digit.
No digit is allowed to be a zero at any point in the process.
Examples:
7624 is shrinkable. It reduces to 142 which reduces to 32 which reduces to 1.
4131 is not shrinkable because it reduces to 322 which reduces to 10 which contains a zero.
Your goal is to create the smallest possible n digit shrinkable number for n = 2, 3, 4, ...
Is there a shrinkable number for any value of n?
The lowest shrinkable numbers with given numbers of digits are as follows:
12
124
1248
12492
124921
1249216
12712912
139219216
The program tries, but fails, to extend the found sets, including ones not listed here as they are not the lowest for a given length, but fails to find any continuations that work, even for just one more digit, so this is the limit of the size that n can be: n = 9.
DECLARE SUB fill (col!)
CLEAR , , 25000
DIM SHARED dig(20, 20), accomp(20)
CLS
fill 1
SUB fill (col)
FOR i = 1 TO 9
succ = 0
dig(1, col) = i
FOR r = 2 TO col
dig(r, col - r + 1) = ABS(dig(r - 1, col - r + 1) - dig(r - 1, col - r + 2))
IF dig(r, col - r + 1) > 0 THEN
IF r = col AND accomp(col) = 0 THEN
accomp(col) = 1
FOR j = 1 TO col
PRINT dig(1, j);
NEXT
PRINT
END IF
IF r = col THEN succ = 1
ELSE
succ = 0: EXIT FOR
END IF
NEXT
IF col = 1 OR succ = 1 THEN
fill col + 1
END IF
NEXT i
END SUB
There are 17,620 maximal-length shrinkable numbers altogether, where maximal-length means that no extra digit from 1 through 9 can be appended to the right without producing a zero somewhere in the list of differences. Each contiguous subset of a maximal shrinkable is also shrinkable. For example 1248 is one such maximal-length shrinkable. Obviously 248 is also shrinkable. That 1248 itself is maximal, we can see from
1 2 4 8 1 1 2 4 8 2 1 2 4 8 3 1 2 4 8 4 1 2 4 8 5 1 2 4 8 6 1 2 4 8 7 1 2 4 8 8 1 2 4 8 9
1 2 4 7 1 2 4 6 1 2 4 5 1 2 4 4 1 2 4 3 1 2 4 2 1 2 4 1 1 2 4 0 1 2 4 1
1 2 3 1 2 2 1 2 1 1 2 0 1 2 1 1 2 2 1 2 1 1 2 3
1 1 1 0 1 1 1 1 1 0 1 1 1 1
0 0 0 0 0
where we see that no matter what digit is appended to the right, a zero is reached. (Digits could, however, be appended to the left, as in 25491248. There are 13,284 shrinkable numbers that cannot be extended on either the right or the left)
That doesn't mean that the subset 248 will also fail to be extensible on the right, as evidenced by 24819836:
2 4 8 1 9 8 3 6
2 4 7 8 1 5 3
2 3 1 7 4 2
1 2 6 3 2
1 4 3 1
3 1 2
2 1
1
24819836 itself is maximal; no digit can extend it. Starting with the new extension and then going down and to the left, successive trials for that digit with its concomitant trail of differences would be: 1,5,2,0; 2,4,1,1,1,0; 3,3,0; 4,2,1,1,1,0; 5,1,2,0; 6,0; 7,1,2,0; 8,2,1,1,1,0; 9,3,0. Actually this only proves that it's not extensible on the right. It also happens not to be extensible on the left as well--it's not just the 1 on the left that would spoil it--any digit would.
One thing that can be seen is that, since continuing with the same digit as previous leads to an immediate zero, it's also true that extending with numbers higher that that matching number repeat the differences from symmetrically opposite that matching number. This could have some bearing on why 9 is the maximum size shrinkable number, for those seeking a more concise proof that 9 is the greatest possible length.
For the record, the largest shrinkable number is 971891894. The smallest shrinkable number that cannot be extended either on the right or the left is 2685.
|
|
Posted by Charlie
on 2011-04-05 18:18:26 |
computer solution
