mersenneforum.org what should I post ?
 Register FAQ Search Today's Posts Mark Forums Read

2018-01-27, 22:04   #12
CRGreathouse

Aug 2006

3×1,993 Posts

Quote:
 Originally Posted by science_man_88 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.

2018-01-27, 22:14   #13
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts

Quote:
 Originally Posted by CRGreathouse 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.

 2018-01-31, 23:32 #14 science_man_88     "Forget I exist" Jul 2009 Dumbassville 20C016 Posts 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.
2018-02-01, 03:29   #15
CRGreathouse

Aug 2006

3·1,993 Posts

Quote:
 Originally Posted by science_man_88 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!.

2018-02-01, 22:02   #16
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts

Quote:
 Originally Posted by CRGreathouse 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.

2018-02-01, 22:26   #17
CRGreathouse

Aug 2006

3×1,993 Posts

Quote:
 Originally Posted by science_man_88 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.

2018-02-01, 23:28   #18
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by CRGreathouse 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

2018-02-02, 02:38   #19
CRGreathouse

Aug 2006

3×1,993 Posts

Quote:
 Originally Posted by science_man_88 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.

2018-02-02, 03:25   #20
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by CRGreathouse 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

 2018-02-03, 18:49 #21 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26×131 Posts 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.
 2018-02-04, 03:23 #22 science_man_88     "Forget I exist" Jul 2009 Dumbassville 838410 Posts . 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

 Similar Threads Thread Thread Starter Forum Replies Last Post Raman Lounge 19 2016-10-07 06:17 xilman Linux 2 2010-12-15 16:39 henryzz Forum Feedback 26 2008-12-24 14:21 Unregistered Forum Feedback 27 2007-04-04 04:56 dave_0273 Lounge 1 2005-02-27 18:36

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

Thu Jan 27 11:01:17 UTC 2022 up 188 days, 5:30, 1 user, load averages: 1.04, 1.27, 1.28