Thread: November 2019 View Single Post
2019-12-04, 14:22   #84
bsquared

"Ben"
Feb 2007

3,371 Posts

Quote:
 Originally Posted by a1call The names are up. Someone surpassed the open question in less than 2 days. No one designated with a single asterisk which might indicate that all who surpassed got the same result which is unlikely. Congratulations to all who got the answer.
Oleg was kind enough to post his solution and code, which still seem like magic to me.

Of no use whatsoever now, but just before I killed my search programs I found a matrix with determinant 927380637. Still satisfying and a nice ending point.

The search method I used was random hill climbing. Rough pseudocode:

Code:
nov2019():
while (1)
m = create_random_matrix()

d1 = determinant(m)
d2 = d1
do
d1 = d2
m = find_best_swap(m)
d2 = determinant(m)
while (d2 > d1)

find_best_swap(m):
best = determinant(m)
best_m = m
for i=1:81
for j=i+1:81
swap(m[i],m[j])
d = determinant(m)
if (d > best)
best_m = m
swap(m[i],m[j])

return best_m
find_best_swap() benefited greatly from uau's hint because it nearly eliminates the innermost determinant at the cost of a single inverse at the beginning; probably he was doing something similar to the above.

Cheers to all!

I found that for the other matrix type (https://oeis.org/A085000) the search benefits a lot from annealing, where find_best_swap can accept matrices worse than the input with probability decreasing with distance from the input. The challenge matrices did not benefit from this.

Last fiddled with by bsquared on 2019-12-04 at 14:34 Reason: more info