mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > science_man_88

Closed Thread
 
Thread Tools
Old 2018-01-27, 22:04   #12
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·52·79 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
That the residues mod some mersenne in the LL test, are quadratic residues mod the next mersenne.
Reason I think this to be true:

Sqr(A*p+b)= A^2(p^2)+ b^2(1^2)-b mod 2p+1 and two parts of that simplify to quadratic residues. Failure would only happen if the sums/ differences of quadratic residues wasn't a quadratic residue ( guess I may be wrong).
1 is a quadratic residue but 2 is a quadratic nonresidue mod 3.
CRGreathouse is online now  
Old 2018-01-27, 22:14   #13
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
1 is a quadratic residue but 2 is a quadratic nonresidue mod 3.
Yeah, I messed up the sqr to begin with. It was mostly to find a tranform between residues mod different mersennes.
science_man_88 is offline  
Old 2018-01-31, 23:32   #14
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default Superpermutations



Still can't believe the lowest number of instruction needed to have all permutations of n instructions present in a code isn't well known.
science_man_88 is offline  
Old 2018-02-01, 03:29   #15
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×52×79 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
Still can't believe the lowest number of instruction needed to have all permutations of n instructions present in a code isn't well known.
True, but the bounds are pretty tight: n! + (n-1)! + (n-2)! + n-3 <= A180632(n) <= n! + (n-1)! + ... + 2! + 1!.
CRGreathouse is online now  
Old 2018-02-01, 22:02   #16
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
True, but the bounds are pretty tight: n! + (n-1)! + (n-2)! + n-3 <= A180632(n) <= n! + (n-1)! + ... + 2! + 1!.
I see why it's so hard, just annoying. It's hard to brute force when options for endpoint pairs grow by a factor of n^2.
science_man_88 is offline  
Old 2018-02-01, 22:26   #17
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·52·79 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
I see why it's so hard, just annoying. It's hard to brute force when options for endpoint pairs grow by a factor of n^2.
Sure. When you have
\[n^{n! + (n-1)! + (n-2)! + n-3}\]
possibilities to check in the best case, it's hard to reduce the options to something reasonable. Googol to the sixth power and all that.
CRGreathouse is online now  
Old 2018-02-01, 23:28   #18
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Sure. When you have
\[n^{n! + (n-1)! + (n-2)! + n-3}\]
possibilities to check in the best case, it's hard to reduce the options to something reasonable. Googol to the sixth power and all that.
I do see ways to cut down the number to search. Because, you can use symmetries picking (a,b) and (b',a') where apostrophies mean reversed permutations, will not change much at the same length, it can in theory reverse the superpermutation.

Last fiddled with by science_man_88 on 2018-02-01 at 23:46
science_man_88 is offline  
Old 2018-02-02, 02:38   #19
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×52×79 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
I do see ways to cut down the number to search. Because, you can use symmetries picking (a,b) and (b',a') where apostrophies mean reversed permutations, will not change much at the same length, it can in theory reverse the superpermutation.
That cuts it down to a little more than
\[n^{n! + (n-1)! + (n-2)! + n-3}/2.\]

You can do better: reassign the variables so the first one you use is 1, the first one you use other than that is 2, and so on. This cuts it to about
\[n^{n! + (n-1)! + (n-2)! + n-3}/n! \approx n^{n! + (n-1)! + (n-2)! - 3}.\]

But these numbers are huge, we need to do much, much better.
CRGreathouse is online now  
Old 2018-02-02, 03:25   #20
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
That cuts it down to a little more than
\[n^{n! + (n-1)! + (n-2)! + n-3}/2.\]

You can do better: reassign the variables so the first one you use is 1, the first one you use other than that is 2, and so on. This cuts it to about
\[n^{n! + (n-1)! + (n-2)! + n-3}/n! \approx n^{n! + (n-1)! + (n-2)! - 3}.\]

But these numbers are huge, we need to do much, much better.
Only patterns I see is that when the current lengths known n<6 are divided by 3 we get 1 mod 4, 3 mod 4, 1 mod 4, 3 mod 4. Wonder if that holds.

Last fiddled with by science_man_88 on 2018-02-02 at 03:34
science_man_88 is offline  
Old 2018-02-03, 18:49   #21
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

At least we can use derangement math to show as n gets larger about 37% of orderings will have at least 1 permutaion placed correctly.
science_man_88 is offline  
Old 2018-02-04, 03:23   #22
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

. Not sure it wouldn't be solved already, I found a solution for the equation for n=14 just take the coeffcients on 1001 to add to 391 Mod 432 and the coefficient on 432 is 906 mod 1001.

Last fiddled with by science_man_88 on 2018-02-04 at 03:34
science_man_88 is offline  
Closed Thread

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Post 200000 Raman Lounge 19 2016-10-07 06:17
Where to post job ad? xilman Linux 2 2010-12-15 16:39
Post numbers - what now? henryzz Forum Feedback 26 2008-12-24 14:21
Can't post to other forums Unregistered Forum Feedback 27 2007-04-04 04:56
Something that I just had to post/buy dave_0273 Lounge 1 2005-02-27 18:36

All times are UTC. The time now is 14:55.

Fri Sep 25 14:55:30 UTC 2020 up 15 days, 12:06, 1 user, load averages: 1.73, 1.85, 1.71

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.