mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2019-11-27, 20:04   #78
SmartMersenne
 
Sep 2017

2×43 Posts
Default

Quote:
Originally Posted by SmartMersenne View Post

Quote:
Originally Posted by Kebbaj View Post
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.
SmartMersenne is offline   Reply With Quote
Old 2019-11-27, 20:30   #79
uau
 
Jan 2017

79 Posts
Default

Quote:
Originally Posted by SmartMersenne View Post
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.
uau is offline   Reply With Quote
Old 2019-11-28, 18:04   #80
yae9911
 
yae9911's Avatar
 
"Hugo"
Jul 2019
Germany

31 Posts
Default

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
yae9911 is offline   Reply With Quote
Old 2019-11-29, 02:37   #81
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×7×11×29 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2019-12-02, 14:47   #82
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13·257 Posts
Default

Quote:
Originally Posted by yae9911 View Post

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?
bsquared is offline   Reply With Quote
Old 2019-12-04, 13:20   #83
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

7×277 Posts
Default

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.
a1call is offline   Reply With Quote
Old 2019-12-04, 14:22   #84
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13·257 Posts
Default

Quote:
Originally Posted by a1call View Post
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!

[edit]
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
bsquared is offline   Reply With Quote
Old 2019-12-04, 14:29   #85
uau
 
Jan 2017

10011112 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
uau is offline   Reply With Quote
Old 2019-12-04, 15:01   #86
yae9911
 
yae9911's Avatar
 
"Hugo"
Jul 2019
Germany

31 Posts
Default

@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.
yae9911 is offline   Reply With Quote
Old 2019-12-04, 15:19   #87
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

5·13·53 Posts
Default

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
EdH is offline   Reply With Quote
Old 2019-12-04, 15:27   #88
yae9911
 
yae9911's Avatar
 
"Hugo"
Jul 2019
Germany

31 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
yae9911 is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 23:36.

Wed Nov 25 23:36:51 UTC 2020 up 76 days, 20:47, 3 users, load averages: 1.06, 1.14, 1.23

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.