The New Sudoku Players' Forum

[r.e.s.]

A maniacal pencil-marking sudoku addict decided to erase the pencil-marks in a gloriously roundabout way,
using a very simple method that deletes a string of digits in a sequence of steps ...

Code: Select all

On the n-th step (n = 1, 2, 3, ...):
  If the rightmost digit in the string is 0, delete it,
  otherwise replace it with n copies of the next-smaller digit.

For example, '3' is erased in 14 steps:

Code: Select all

Step  String
----  --------
      3
   1  2
   2  11
   3  1000
   4  100
   5  10
   6  1
   7  0000000
   8  000000
   9  00000
  10  0000
  11  000
  12  00
  13  0
  14  -

Tragically, that sudoku addict succumbed during an orgy of erasing brought on by a '4', which required 22,539,988,369,406 steps.

Which is less than a tittle compared to what a '5' would have required ...

Consider googolplex-digit sudoku -- ordinary sudoku, but with a grid that's googolplex x googolplex instead of 9 x 9.
(A googolplex is 10^(10^100) -- that is, 1 followed by a googol of 0's, where a googol is 1 followed by a hundred 0's.)
Let G be the total number of googolplex-digit sudoku puzzles.

Erasing the digit '5' requires enormously more than G steps!

[udosuk]

Interesting... Looks like this action is easier to perform in a quaternary system (i.e. where only 0,1,2,3 exist)...

A brief check confirms that the following table:

Code: Select all

no. #steps to erase
0     1
1     2
2     4
3    14
10    4
11    6
12   10
13   30
...
100   6

But it's an impressive task to work out the #steps for 4... Using a program probably?

[r.e.s.]

Using a program probably?

No, I contrived the string-erasing algorithm just to exhibit a family of recursively-defined Ackermann-type functions.
(The base of the numeral system is arbitrary, so every non-negative integer is a possible digit.)

Rather than post the details, I've put them <here> for anyone interested.

Briefly:
The number of steps needed to erase '4' is (2^39)*41-2, but for '5' it's more difficult to express:
the number of steps needed to erase '5' is greater than 2^^x (an exponential tower of x 2's), where x > 2^(2^101).
(In contrast, I calculate the number of googolplex-digit sudoku puzzles to be far less than 2^^13.)

PS:
All of your results agree with the formulas given in the text file.

[udosuk]

Code: Select all

num  #steps to erase
  0  1
  1  2
  2  4
  3  14
  4  22539988369406
 10  4
 11  6
 12  10
 13  30
 14  45079976738814
 20  14
 21  38
 22  222
 23  557054
 24  2^22539988369407*22539988369409-2
 30  22539988369406
 31  2^3842565881941820373286881591295*3842565881941820373286881591297-2
100  6
101  8
102  12
103  32
104  45079976738816
110  10
111  14
112  22
113  62
114  90159953477630
120  30
121  78
122  446
123  1114110
124  2^22539988369408*22539988369409-2
130  45079976738814
131  2^3842565881941820373286881591296*3842565881941820373286881591297-2
200  38
201  94
202  510
203  1179646
204  2^22539988369408*22539988369410-2
210  222
211  1150
212  26622
213  70866960382
214  2^45079976738815*45079976738817-2
220  557054
221  22539988369406
222  2^223*225-2
223  2^557055*557057-2
224  2^(2^22539988369407*22539988369409-1)*(2^22539988369407*22539988369409+1)-2
230  2^22539988369407*22539988369409-2
231  2^(2^3842565881941820373286881591295*3842565881941820373286881591297-1)
      *(2^3842565881941820373286881591295*3842565881941820373286881591297+1)-2
300  2^3842565881941820373286881591295*3842565881941820373286881591297-2
301  2^(2^(2^223*225-1)*(2^223*225+1)-1)*(2^(2^223*225-1)*(2^223*225+1)+1)-2

[r.e.s.]

Those look right. Here's a concise summary ...

Code: Select all

Let [Xk]n be the number of steps remaining to erase the string 'Xk' occurring on step n.
Then [Xk]n (n >= 0, k >= 0) is given by the recursion relations

[Xk]n = [X][k]n   (associating from the right)
 [k]n = [k-1]^(n+1)(n+1)   (k > 0)
 [0]n = n+1

This gives some simple formulas for small single-digit strings:

[0]n = n+1
[1]n = 2*(n+1)
[2]n = 2^(n+1)*(n+3)-2.

For example, to erase '123' given at step 0 ...

[123]0
= [1][2][3]0
= [1][2][2]1
= [1][2](2^(1+1)*(1+3)-2)
= [1][2]14
= [1](2^(14+1)*(14+3)-2)
= [1]557054
= 2*(557054+1)
= 1114110.