## How NOT to erase pencil-marks!

Anything goes, but keep it seemly...

### How NOT to erase pencil-marks!

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!
r.e.s.

Posts: 337
Joined: 31 August 2005

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 erase0     11     22     43    1410    411    612   1013   30...100   6`

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

Posts: 2698
Joined: 17 July 2005

udosuk wrote: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.
r.e.s.

Posts: 337
Joined: 31 August 2005

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-2100  6101  8102  12103  32104  45079976738816110  10111  14112  22113  62114  90159953477630120  30121  78122  446123  1114110124  2^22539988369408*22539988369409-2130  45079976738814131  2^3842565881941820373286881591296*3842565881941820373286881591297-2200  38201  94202  510203  1179646204  2^22539988369408*22539988369410-2210  222211  1150212  26622213  70866960382214  2^45079976738815*45079976738817-2220  557054221  22539988369406222  2^223*225-2223  2^557055*557057-2224  2^(2^22539988369407*22539988369409-1)*(2^22539988369407*22539988369409+1)-2230  2^22539988369407*22539988369409-2231  2^(2^3842565881941820373286881591295*3842565881941820373286881591297-1)      *(2^3842565881941820373286881591295*3842565881941820373286881591297+1)-2300  2^3842565881941820373286881591295*3842565881941820373286881591297-2301  2^(2^(2^223*225-1)*(2^223*225+1)-1)*(2^(2^223*225-1)*(2^223*225+1)+1)-2`
udosuk

Posts: 2698
Joined: 17 July 2005

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+1This 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.
r.e.s.

Posts: 337
Joined: 31 August 2005