Find the maximum determinant for each size Toeplitz matrix For a fixed n, consider the n by n Toeplitz matrices with entries which are either 0 or 1.  The aim is to find maximum determinant over all such Toeplitz matrices.

Task

For each n from 1 upwards, output the maximum determinant over all n by n Toeplitz matrices with entries which are either 0 or 1. There should be one output per n which should have the maximum determinant and also an example matrix that reaches it.

Score

Your score is the largest n your code gets to in 2 minutes on my computer.  To clarify a little, your code can run for 2 minutes in total, this is not 2 minutes per n.

Tie breaker

If two entries get the same n score then the winning entry will be the one that gets to the highest n in the shortest time on my machine. If the two best entries are equal on this criterion too then the winner will be the answer submitted first.

Languages and libraries

You can use any freely available language and libraries you like. I must be able to run your code so please include a full explanation for how to run/compile your code in linux if at all possible.

My Machine The timings will be run on my machine. This is a standard ubuntu install on an AMD FX-8350 Eight-Core Processor.  This also means I need to be able to run your code.

Small answers

For n = 1..10 the outputs should be 1,1,2,3,5,9,32,56,125,315

This sequence is not in OEIS and so the winning entry also gets to propose a new entry there.

Entries so far


n=10 n=11 by Vioz in Python
n=9 by Tyilo in C
n=12 by Legendre in J
n=10 by Tensibai in R
n=14 by SteelRaven in C++
n=14 by RetoKoradi in C++
J

Update: Improved code to search over half the values. Now calculates n=12 comfortably within 120 seconds (down from 217s to 60s).

You will need the latest version of J installed.

#!/usr/bin/jconsole

dim =: -:@&gt;:@#
take =: i.@dim
rotstack =: |."0 1~ take
toep =: (dim (|."1 @: {."1) rotstack)"1
det =: -/ . * @: toep
ps =: 3 : ',/(0 1 ,"0 1/ ,.y)'
canonical =: #. &gt;: [: #. |. " 1

lss =: 3 : 0
  shape =. (2^y), y
  shape $ ,&gt;{;/(y,2)$0 1
)

ls =: (canonical@:lss) # lss
ans =: &gt;./ @: det @: ls @: &lt;: @: +:

display =: 3 : 0
echo 'n = ';y;'the answer is';ans y
)
display"0 (1 + i.13)
exit''




Run this and kill when two minutes are up. My results (MBP 2014 - 16GB of RAM):

┌────┬─┬─────────────┬─┐
│n = │1│the answer is│1│
└────┴─┴─────────────┴─┘
┌────┬─┬─────────────┬─┐
│n = │2│the answer is│1│
└────┴─┴─────────────┴─┘
┌────┬─┬─────────────┬─┐
│n = │3│the answer is│2│
└────┴─┴─────────────┴─┘
┌────┬─┬─────────────┬─┐
│n = │4│the answer is│3│
└────┴─┴─────────────┴─┘
┌────┬─┬─────────────┬─┐
│n = │5│the answer is│5│
└────┴─┴─────────────┴─┘
┌────┬─┬─────────────┬─┐
│n = │6│the answer is│9│
└────┴─┴─────────────┴─┘
┌────┬─┬─────────────┬──┐
│n = │7│the answer is│32│
└────┴─┴─────────────┴──┘
┌────┬─┬─────────────┬──┐
│n = │8│the answer is│56│
└────┴─┴─────────────┴──┘
┌────┬─┬─────────────┬───┐
│n = │9│the answer is│125│
└────┴─┴─────────────┴───┘
┌────┬──┬─────────────┬───┐
│n = │10│the answer is│315│
└────┴──┴─────────────┴───┘
┌────┬──┬─────────────┬────┐
│n = │11│the answer is│1458│
└────┴──┴─────────────┴────┘
┌────┬──┬─────────────┬────┐
│n = │12│the answer is│2673│
└────┴──┴─────────────┴────┘


Total run time = 61.83s.



Just for fun

┌────┬──┬─────────────┬────┐
│n = │13│the answer is│8118│
└────┴──┴─────────────┴────┘


This took approximately 210 seconds on its own.