Fun problem, no?
The answer here, I am fairly sure, is that one may always obtain a single digit. However, what follows below is anything but a rigorous proof.
Call the “multiply and remove zeroes operation: *
Consider all i > 10
If we can show that for all i, there is a method to chose a multiplier j such that
i * j < i
or a finite set of j’s such that:
( ( ( ( i * j1 ) * j2 ) * j3 ) … ) ) ) < i
we are done, since successive applications lead downward inexorably to a single digit.
We can see immediately that for all even numbers, i * 5 < i
(i * 5 ) is half i, or less than half i if embedded zeros are removed, in addition to the trailing 0.
Likewise, for all numbers ending in 5, i * 2 < i
(i * 2) is 1/5th i, or less than 1/5th i if embedded zeros are removed, in addition to the trailing 0.
So we are left for finding a method for numbers ending in 1, 3, 7, 9.
I divide such numbers into two groups: fruits: easy to crack, and the nuts: hard to crack. The nuts, in order, are:
11 33 37 99 333
597 999 3333 5997 9999
19999 33333 39997 39999 49997
49999 59997 59999 79999 99999
124999 199997 199999 249999 333333
374999 399997 399999 499997 499999
599991 599997 599999 799999 999999
1249999 1999997 1999999 2499999 3333333
3749997 3749999 3999997 3999999 4999997
4999999 5999991 5999997 5999999 6249999
7999999 9999999 12499999 19999997 19999999
24999999 33333333 37499997 37499999 39999997
39999999 49999997 49999999 59999991 59999997
59999999 62499999 79999999 99999999 . . . .
And onward…
What makes a nut a nut and fruit a fruit? For a fruit,
there is always a single j1 or two j’s j1, j2 that makes i * j < i true.
To separate fruits from nuts I used j2 = 5 if the last digit after applying j1 was even. Else, I did not use a j2.
eg. 23
23 * 87 = 21 (via 2001)
e.g. 19
19 * 16 = 34, 34 * 5 = 17 (via 304, 170)
The nuts are the rest, and they take more than my two steps. Here is a table of i = 11 to 99 labeling "small" on all fruits. (i * j1)* j2 < i
“done” is written when a single digit was achieved in one or two operations (for the fruit). The number of zeroes eliminated after * j1, is given as "#+", e.g., "2+" = 2 zeroes removed, and whether an even value was reached "halve" is labeled, where the half result is also given. "small" means (i * j1) * j2 < i (so it's a fruit). The “nuts” are marked “failed”
top? 101
11 failed
13 x 8 = 104 14 7 1+ zeros halve small done!
17 x 6 = 102 12 6 1+ zeros halve small done!
19 x 16 = 304 34 17 1+ zeros halve small
21 x 5 = 105 15 15 1+ zeros small
23 x 87 = 2001 21 21 2+ zeros small
27 x 4 = 108 18 9 1+ zeros halve small done!
29 x 7 = 203 23 23 1+ zeros small
31 x 968 = 30008 38 19 3+ zeros halve small
33 failed
37 failed
39 x 18 = 702 72 36 1+ zeros halve small
41 x 5 = 205 25 25 1+ zeros small
43 x 7 = 301 31 31 1+ zeros small
47 x 64 = 3008 38 19 2+ zeros halve small
49 x 41 = 2009 29 29 2+ zeros small
51 x 2 = 102 12 6 1+ zeros halve small done!
53 x 2 = 106 16 8 1+ zeros halve small done!
57 x 158 = 9006 96 48 2+ zeros halve small
59 x 12 = 708 78 39 1+ zeros halve small
61 x 5 = 305 35 35 1+ zeros small
63 x 8 = 504 54 27 1+ zeros halve small
67 x 3 = 201 21 21 1+ zeros small
69 x 3 = 207 27 27 1+ zeros small
71 x 986 = 70006 76 38 3+ zeros halve small
73 x 14 = 1022 122 61 1+ zeros halve small
77 x 4 = 308 38 19 1+ zeros halve small
79 x 14 = 1106 116 58 1+ zeros halve small
81 x 5 = 405 45 45 1+ zeros small
83 x 241 = 20003 23 23 3+ zeros small
87 x 7 = 609 69 69 1+ zeros small
89 x 9 = 801 81 81 1+ zeros small
91 x 11 = 1001 11 11 2+ zeros small
93 x 14 = 1302 132 66 1+ zeros halve small
97 x 31 = 3007 37 37 2+ zeros small
99 failed
101 x 1 = 101 11 11 1+ zeros small
But the nuts can be cracked (although my proof is hand-wavy).
Take, for example 11:
(((11 * 9546) * 5) * 18) * 625 = 9
or 5997
(((((5997 * 968) * 35) * 155) * 5176) *3876) * 5 = 9
or take 9999:
((((9999 * 92) * 49) * 625) * 7) * 6 = 9
also
I have been able to crack all nuts i have tried, going to 18 sig digs.
My method is to multiply up, both losing a few zeros, and landing some even digits. Then multiplying this time going down while again losing zeros.
So what is going on here? I am not sure.
The nuts are numbers containing digits like “9”. A number like 9999, multiplied by any number, rarely yields zeroes. Why? - that is the question!
The way to “crack nuts” is to make larger products going up in total digits which can then be worked downward to the lower digits and generate the needed “0” sums for reduction. It is all empirical at this point, but it works.
One of the programs (not the 64 bit one) is here and an example run is here)
Since the solution is "in the queue" I'll bet there is an analytic proof. Also, I wonder if this might be more easily proven in base 2, and then generalized... And I wonder if there are possible applications to binary security keys...
That’s it for now!
Edited on September 11, 2019, 3:13 pm
some efforts
