Perl Weekly Challenge 149: Largest Square

    f(2)="1"
    f(4)="3201"
    f(10)="9814072356"
    f(12)="B8750A649321"

This is sequence A287298 in The On-Line Encyclopedia of Integer Sequences.

First thing we should notice that the OEIS only lists entries up to base 22, while skipping the entry for 21.

Perhaps this is really hard to calculate? The OEIS shows an example program (in Python):

from gmpy2 import isqrt, mpz, digits
def A287298 (n): # assumes n <= 62
    m  = isqrt (mpz ('' . join (digits (i, n) for i in range (n - 1, -1, -1)), n))
    m2 = m ** 2
    d  = digits (m2, n)
    while len (set (d)) < len (d):
        m  -= 1
        m2 -= 2 * m + 1
        d   = digits (m2, n)
    return int (m2)

Ouch! This starts by creating the largest number in the give base without repeats. Starting with the integer square root of that number, it checks whether its square does not contain any repeats. If not, it subtracts 1 from the square root, and checks the square for repeats again. Rinse and repeat until there is a winner. (There will always be a square number without repeats, as 1 is such a square in any base).

For most bases up to 20, this goes reasonably fast, but base 17 already requires more than 2 billion checks. (Base 21 requires at least 77 trillion checks — and counting).

This is too slow to run each time we want to find the largest square without repeats in a base. Instead, we will make use of the preprocessed values:

• We get the values of bases up to 20 from the list on OEIS for sequence A287298.
• We get the value for base 22 from the entry for A287298.
• We let the above Python program run for a while, and derive the values for bases 23, 24 and 25:
  • \(20837313275713865979999662611449_{23} = \rm{MLKJEFG5IC1D9H8042AB376}\)
  • \(1331214423741263089885099589776609_{24} = \rm{NMLKJ2BD0639GFE7C8IH5A41}\)
  • \(88663641996555130440258540215016516_{25} = \rm{ONMLKD8CJE2H47F6395I0B1AG}\)

The values we get, either from the OEIS, or the output of the above Python program are in decimal. To convert this to the appropriate base, we make use of bc (here $value is the value we want to convert to base $base):

my $value_in_base = `echo "obase=$base; $value" | bc`

This works fine for bases up to 16, where bc uses letters A to F.

For bases exceeding 16, bc uses a different system: then each digit in base b is represented by two digit decimal number less than b; the two digit numbers separated by spaces. To complicate things further, for larger bases, this resulting representation may exceed the default line width of bc. So, we use the following code to get our numbers in the appropriate base:

my @chars = (0 .. 9, 'A' .. 'Z');
$ENV {BC_LINE_LENGTH} = 1000;

my $value_in_base = `echo "obase=$base; $value" | bc`
                  =~ s/ ([0-9]{2})/$chars [0 + $1]/egr
                  =~ s/\n//r;

Find the full preprocessing program on GitHub.

Writing a program which is nothing more than a lookup table is trivial:

my @A287298;

$A287298 [ 2] =                         "1";
$A287298 [ 3] =                         "1";
$A287298 [ 4] =                      "3201";
$A287298 [ 5] =                      "4301";
$A287298 [ 6] =                    "452013";
$A287298 [ 7] =                   "6250341";
$A287298 [ 8] =                  "47302651";
$A287298 [ 9] =                 "823146570";
$A287298 [10] =                "9814072356";
$A287298 [11] =               "A8701245369";
$A287298 [12] =              "B8750A649321";
$A287298 [13] =              "CBA504216873";
$A287298 [14] =            "DC71B30685A924";
$A287298 [15] =           "EDAC93B24658701";
$A287298 [16] =          "FED5B39A42706C81";
$A287298 [17] =          "GFED5A31C6B79802";
$A287298 [18] =        "HGF80ADC53712EB649";
$A287298 [19] =       "IHGFD3408C6E715A2B9";
$A287298 [20] =      "JIHG03DAC457BFE96281";
$A287298 [22] =    "LKJIG5D14B9032FHAC867E";
$A287298 [23] =   "MLKJEFG5IC1D9H8042AB376";
$A287298 [24] =  "NMLKJ2BD0639GFE7C8IH5A41";
$A287298 [25] = "ONMLKD8CJE2H47F6395I0B1AG";

say $A287298 [$_] // "Too hard to calculate" while <>;

Find the full program on GitHub.