Fun with number base systems

[Randy Olsen]

One Dr. Maximilian F. Hasler beat me to this, and probably others as well, yet at the same time I was pleased with having a result returned by OEIS when I searched for "1,16,112249", and I have not found it mentioned previously among the Superpermutators discussions.

The search I did represents the first three minimal superpermutations (n = 1 through n = 3) if you interpret them as base n+1 numbers and convert to base 10.

The OEIS page also has the n = 4 result, plus in the Comments section has one example for n = 5, since we have to confront minimal superpermutation non-uniqueness.

https://oeis.org/A332090

The n = 4 result and n = 5 example result are rather long numbers, but I took to counting the digits.

The n = 4 result is a number with 23 digits, and the n = 5 result is a number with 119 digits.

If we go back and look at n = 1 through n = 3 for this OEIS sequence: The n = 1 result is a one-digit number, the n = 2 result is a two-digit number, and the n = 3 result is a six-digit number.

So one may compare 

1, 2, 6, 23, 119 

to n! up to n = 5:

1, 2, 6, 24, 120  

This got me thinking about how base 10 suffices to nicely "encode" these minimal superpermutations (and thus n! permutations) in a number with less than or equal to n! digits.  (Should I say "fewer than or equal to" for proper English if I am counting digits?)

Ah, but something definitely has to give by n = 9 because whatever a minimal superpermutation is for n = 9, it has to respect the known bounds, and the n = 9 result in this OEIS A332090 would just be the minimal superpermutation itself, so there is no compression afforded by base 10.  We'd already be reading a minimal superpermutation for n = 9 as a base 10 number.

In fact, something already gives by n = 6 per my calculations, because we can use the bounds and best-known results to say something about how many digits the entries for OEIS A332090 would have:

The n = 6 result would have 737 or so digits (taking the base 10 log of 7, then multiplying by 872, yields 736.925...)

Even using the lower bound of 867 just gets you down to 732 or 733 digits.

The n = 7 result might have 5334 or so digits (as log(8)*5906 = 5333.649...)

The n = 8 result might have 44088 or so digits (from log(9)*46202, where I have used my prediction for the n = 8 minimal superpermutation length, but using the upper bound of 46205 would get you 44090 or 44091 digits)

Anyway, these numbers of digits are well above the n! values for n = 6, 7, and 8: those being 720, 5040, and 40320, respectively.

So I would like to ask, and partially answer here, a modified question: 

For each n, what base suffices to encode a minimal superpermutation, read as a base n+1 number, into a value having a number of digits less than or equal to n! ?

These are my findings:

For n = 1, base 2 obviously suffices.

For n up to 2, base 5 suffices.

For n up to 3, base 7 suffices.

For n up to 4, base 9 suffices.

For n up to 5, base 10 suffices.

Then, if I am doing my logarithm calculations correctly (I would certainly appreciate if someone confirms or refutes),

For n up to 6, base 11 suffices.

For n up to 7, base 12 suffices.

For n up to 8, base 13 suffices.

We could ask other questions such as what bases would suffice to encode down to digits less than or equal to (n-1)!, or (n-2)!, or n, and I would have some interest in those answers, but we would get into rather high bases very quickly.

In other news, the Numberphile channel on YouTube posted a "Tower of Hanoi" video a few days ago that I just watched.  It is of course not the minimal superpermutation problem, but I enjoyed the parallels such as hearing a sequence put to music like was done for the unveiling of that n = 7 superpermutation of length 5906.