[seqfan] Help on a base-n numbers on grid sequence.

[Scott Shannon]

Just wondering if anyone would have some ideas of how to find the missing values in this sequence. I have values n=2,3,7,8,9… but not n=4,5,6 , and I believe these three missing values are extremely difficult to find using a brute force approach as the search tree probably becomes enormous. I’ve tried different approaches to speed up the search, working on and off over some months, but I’ve about given up. I started this hoping it would be a sequence for the OEIS but without the third number I don’t think it qualifies!
The idea is in base-n you place on a 2D grid each successive digit, starting at 0 and cycling back to 0 after digit n-1, so that each digit is orthogonally adjacent to a previously placed digit.  The digits are placed so that at each digit placement you have to create the number k (which is read/created in base-n), where k is made from a straight row or column of adjacent digits which can be read in any direction, and where k starts at 0 and increments by one at each placement. You have to create k even if it already exists on the grid. The sequence is… for base n, what is the largest number k that can be created? Obviously the first n numbers in base-n are simple as just placing the initial single digit creates the number, but that also means there are many ways these initial digits can be placed.
As we are confined to the 2D grid it turns out for n>=7 the answer is easy as the two previously placed ‘1’ digits get surrounded by other digits so the maximum is strictly limited to the number where the final free square around these ‘1’ digits is used. For base-7 the maximum is k=12 , which is created by placing digits 0,1,2,3,4,5,6,0,1,2,3,4,5  . To create k=13 would require putting the next digit 6 next to a ‘1’ digit, but two 1 digits are now totally surrounded so the sequence ends. This pattern holds for all bases n>=7 with the only difference being that in each higher base one more digit can be placed, so for n>=7 we have that k = a(n) = n + 5.
The base-2 and base-3 cases can be brute-force search found fairly quickly with an efficient algorithm. For base-2 we have k = a(2) = 8, and for base-3 its k = a(3) = 39 .  See the images below for example answers my program found – I’m of course assuming my code is correct here! There are many different final configurations that result with these maximum k values, so the images are just one example.
Now the hard part…. base-4, base-5, and base-6.  So far the largest k values, hence lower bounds, for these bases I have found are:  a(4) >= 78, a(5) >= 32, a(6) >= 41.  A very quick check for the base-4 case in my program it produces around 3 or so available positions on average for each digit when it found k values of around 70, so that could imply the number of paths that would need to be checked for a brute force exhaustive search is of the order 3^70. Obviously way too large for the sort of brute force algorithm I’m using (which I feel is quite efficient already) so I’m now struggling to find better values for these missing three bases. I didn’t let my program run for days and days so it could be fairly easy to find values one or two more than my current upper limits, but proving those are the maximum possible values would appear to be very difficult.
For those who would like to write their own code to have a go at this sequence note that one needs to consider that a digit can be placed *between* two existing digits to form the number k. So if in base-4 the grid was 1-2-  -3-1 then a digit 0, for example, could be placed in the middle to form any of 20_4=8, 120_4=24, 203_4=35, 302_4=50, 30_4=12, 130_4=28, and so on.
In summary the current sequence :   8, 39, >=78, >=32, >=41, 12, 13, 14, 15 …..
Any ideas here would be appreciated!
Scott S


Base 2  :  k = 8
Grid:
                 1
        1  0  1  0  0  0
                1
                0
Numbers created (placement order starting at 0):
                   7
         5   0  1   2   4   8
                   3
                   6

 -----------------------------------

Base 3  :  k = 39
Grid:
                 2
            1   2   2
       2   1   2   0   0   2
       1   0   0   1   0   2   1
       0   1   1   1   2   1   1
       0   2   0   1   0   0   0
                 1   2   2   0   0
                 1   0   2   2

Numbers created:

                      26
               37    8    38
       23     7     2    12    18    17
       28     9     0      1      3     11    34
       39   10   19     4      5     16    22
       33   32   30   13      6     21    27
                      25   14    20    24    36
                      31   15    35    29


Base 7  :   k = 12
Grid:

       6   4   5
       3   2   3
            0   1   0
            5   1   4
                 2

Numbers created:

         6     4     5
         3     2   10
                0      1     7
              12     8    11
                       9

----------------------------------

Best result so far for Base 4  :   k>=78
Grid:
                      3
                      2   2
     1        2    1   3    1         2
     0   3   0    1   2    0   3   3   1   3
0   3   3   2    2   3    1   0   3   2   1
2   1   3   1    0   1    1   2   1   2   0   1
3   1   3   0    3   0    1   1   2   2   1
     0   2   2    0   0    3   0   3   3   0
     3   2   0    1   3    0   0   0   1   2
     2                          2   1   0   0   2

Numbers created:

                             59
                             46   70
       77          34   37   39     69          62
       76   63   24   33   30    20   35   31    61   71
56   47   11   10    2    7     13     8     19   42    57
54   29   15   17    0    1       5     6     25   38    68   73
55   53   51   12    3    4     21     9    22    26    41
       40   14   18   32   16   23   36    27    43    60
       75   58   72   49   67   28   64    44    45   74
       78                                 50   65    48    52   66