[seqfan] Re: « King-walking » integers in a square box

[franktaw at netscape.net]

There was considerable discussion about this some months ago.

I got to thinking, what about other bases?

Obviously, for b = 4 (or less), the 2x2 square:

0 1
2 3

produces all non-negative integers.

On the other end, the number of walks of length m on a kxk square is 
bounded by k^2 * 9^n, so for base 10 or more, there are always numbers 
that cannot be obtained.

So what about the intermediate cases, bases 5 through 9? In particular, 
can anyone come up with a box, of any size, which generates all base 5 
integers?

(I will be very surprised if a base 9 solution is possible, but about 
bases 5, 6, 7, and 8 I'm very much in doubt.)

Franklin T. Adams-Watters

> ----------------original message-----------------
> From: "Eric Angelini" Eric.Angelini at kntv.be
> To: "Sequence Fanatics Discussion list" seqfan at list.seqfan.eu
> Date: Fri, 23 Jul 2010 16:50:20 +0200
> -------------------------------------------------
>
>
>>
>> Hello SeqFans,
>> In this 4x5 box one can read all
>> consecutive integers from 0 to 158
>> (included):
>> 5 8 0 7 3
>> 9 6 5 1 8
>> 1 3 2 4 2
>> 4 0 9 7 6
>> (grid submitted by James Dow Allen
>> on rec.puzzles two days ago)
>>
>> The rules are:
>> - an integer is there if it's digits
>> can be walked on by a chess King
>> (one step in 8 directions:
>> 4 straightly, 4 diagonally)
>> - two identical digits (or more) can
>> follow each other (as if the King
>> was jumping on the same square).
>>
>> Example:
>> - the integers 58073, 13997 and 13887
>> are visible below,
>> - the integer 159 is not:
>> 5 8 0 7 3
>> 9 6 5 1 8
>> 1 3 2 4 2
>> 4 0 9 7 6
>> It seems impossible to find such a
>> 4x5 box showing all consecutive in-
>> tegers from 0 to 'n' with 'n' > 158.
>>
>> Here is Giovanni Resta's 158 solution
>> for the same box:
>> 0 3 6 4 2
>> 1 7 5 1 3
>> 4 0 2 8 9
>> 8 9 6 5 7
>> (published on rec.puzzles yesterday)
>>
>> Question:
>> Using the same rules, what would be
>> the highest reachable integer in the
>> successive square boxes 1x1, 2x2, 3x3,
>> 4x4, 5x5, ...
>> This might constitute a seq S for Neil.
>> [S starts 0, 3, 8, ...]