All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Shrinkable numbers (Posted on 2011-04-05) Difficulty: 3 of 5
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?

No Solution Yet Submitted by Jer    
Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer solution Comment 3 of 3 |

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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information