mersenneforum.org November 2019
 Register FAQ Search Today's Posts Mark Forums Read

2019-11-27, 20:04   #78
SmartMersenne

Sep 2017

32×11 Posts

Quote:
Originally Posted by SmartMersenne

Quote:
 Originally Posted by Kebbaj I sit on the ground and I look at this: 930 174 030.
Do you mean this is the highest you found?
You never replied to this one. If this is good, it may be the highest determinant ever found.

2019-11-27, 20:30   #79
uau

Jan 2017

23×11 Posts

Quote:
 Originally Posted by SmartMersenne You never replied to this one. If this is good, it may be the highest determinant ever found.
There was a comment from the puzzle author that it was not enough to get the award for best solution found.

 2019-11-28, 18:04 #80 yae9911     "Hugo" Jul 2019 Germany 31 Posts To support the end stage of the challenge a bit, it certainly does not hurt to provide some more information. None of this is directly suited to solving the problem, but you can then classify how good your own results are. Some time ago the question was discussed, which determinant values can be reached with Latin squares, which would not be permissible if the puzzle definition is interpreted restrictively. The few determinant values greater than 920000000 are the following ones: 920271375, 920606715, 921397680, 923005125, 923209245, 924220125, 926679285, 929587995. All were found by stupidly performing all possible 9! symbol permutations in the list of the 2393407 9x9 Latin squares listed with title "Isotopy classes with nontrivial groups" on Brendan Mc Kay's Latin Squares web page. This gives 1747706 distinct absolute determinant values, which is still not the full list. If you are patient and have fast web access, then you can download and view a 36 MB pdf file Occurrence Counts that gives you an idea of the distribution of determinants. Determinants > 900000000 are extremely rare. The best determinant < 929587995 of a non-Latin square known to me is 927006660, found by Hermann Jurksch outside of the challenge. The record setting determinant value found in the challenge is > 933000000. Last fiddled with by LaurV on 2019-11-29 at 02:41 Reason: added spoiler
 2019-11-29, 02:37 #81 LaurV Romulan Interpreter     Jun 2011 Thailand 222318 Posts Very nice info, thank you for sharing it. So, I am hopeless this time... [ I have to add this puzzle to the list of the "unsolved puzzles from 'ponder this' which I would like to solve in the future, if I have time and got a better idea", probably when I will retire, if any. By unsolved I mean "by myself". Up to now, this list has three items, included the current one. It doesn't mean that I solved all the others, the most of them were too simple or too uninteresting, and few were out of my league... But this seems to be the first and only item in this list which is not definitively solved (i.e. a better solution may exist, which is not known yet), the others had an exhaustive search and a final answer by their solvers or by the puzzle promoter. ] Edit: I edited your post to add spoiler to the score, that astronomic number may discourage some guys here Last fiddled with by LaurV on 2019-11-29 at 02:43
2019-12-02, 14:47   #82
bsquared

"Ben"
Feb 2007

D4B16 Posts

Quote:
 Originally Posted by yae9911 The best determinant < 929587995 of a non-Latin square known to me is 927006660, found by Hermann Jurksch outside of the challenge.
The best I found was 926612865. It feels like it would eventually find 927M+ if I let it run longer, but given the other results it doesn't seem of interest to do so.

On another computer running sequence A085000(7) I've now found 25+ examples of determinant 762150368499, nothing larger. After finding the improved lower bound to A085000(8) I have stopped running it. Would it be of interest to keep looking for larger determinants there?

 2019-12-04, 13:20 #83 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2·17·59 Posts 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.
2019-12-04, 14:22   #84
bsquared

"Ben"
Feb 2007

65138 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

2019-12-04, 14:29   #85
uau

Jan 2017

23·11 Posts

Quote:
 Originally Posted by a1call The names are up. Someone surpassed the open question in less than 2 days.
The results don't tell that. Stars can be added to names later, and the timestamp is not changed. So if you submit the worst possible passable solution at the start of the challenge, and improve it at the last second of the challenge, you'll have your name on the list with an early timestamp and a star.

2019-12-04, 15:01   #86
yae9911

"Hugo"
Jul 2019
Germany

31 Posts

@uau: With the suggestion that Oleg's first solution was not yet optimal, you are probably right, because I received an E-mail from IBM's puzzlemaster Oded dated Nov 12, 2019, 10:22 AM, in which he reported that now the problem was solved. I guess I will not reveal any secrets or anything private now if I quote this:
Quote:
 ... I'm happy to tell you that I just got, from Oleg, a solution to the open problem: 941568327 594632187 859214736 437981526 368197254 175829634 682473951 716746491 223355889 Note that it has some nice properties.

 2019-12-04, 15:19 #87 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 29·127 Posts The best I found were several above 921e6 (a couple 922e6), but still below 923e6, but I was partly infatuated with the 929e6 latin square and started using it for a starting matrix. I also tried using the 921/922e6 squares, too. At one point I had over 175 cores running. Better programming skills were definitely a necessity - something I hopefully did advance a little. . . Congrats to all! Last fiddled with by EdH on 2019-12-04 at 15:19
2019-12-04, 15:27   #88
yae9911

"Hugo"
Jul 2019
Germany

31 Posts

Quote:
 Originally Posted by a1call No one designated with a single asterisk which might indicate that all who surpassed got the same result which is unlikely.
Once it was clear that the "**" problem had been solved, it was planned to give the submitters of record setting solutions an additional "*". Apparently, however, all submitted "**" solutions reached the same target value.
A proof that this solution is really optimal now is out of reach, but I will risk taking this value as the next entry A301371(9), similar to the inclusion of A085000(7) that has received multiple confirmations, including those from b2.

 Similar Threads Thread Thread Starter Forum Replies Last Post Batalov Puzzles 5 2018-12-03 13:31 Batalov Puzzles 3 2017-12-08 14:55 Xyzzy Puzzles 1 2016-12-06 16:41 R. Gerbicz Puzzles 3 2015-12-01 17:48 Xyzzy Puzzles 1 2014-12-02 17:40

All times are UTC. The time now is 01:47.

Wed Apr 14 01:47:57 UTC 2021 up 5 days, 20:28, 1 user, load averages: 2.64, 2.11, 1.95