 mersenneforum.org (https://www.mersenneforum.org/index.php)
-   science_man_88 (https://www.mersenneforum.org/forumdisplay.php?f=140)
-   -   what should I post ? (https://www.mersenneforum.org/showthread.php?t=21914)

 CRGreathouse 2018-01-27 22:04

[QUOTE=science_man_88;478006]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).[/QUOTE]

1 is a quadratic residue but 2 is a quadratic nonresidue mod 3.

 science_man_88 2018-01-27 22:14

[QUOTE=CRGreathouse;478570]1 is a quadratic residue but 2 is a quadratic nonresidue mod 3.[/QUOTE]

Yeah, I messed up the sqr to begin with. It was mostly to find a tranform between residues mod different mersennes.

 science_man_88 2018-01-31 23:32

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.

 CRGreathouse 2018-02-01 03:29

[QUOTE=science_man_88;478952]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.[/QUOTE]

True, but the bounds are pretty tight: n! + (n-1)! + (n-2)! + n-3 <= [url=https://oeis.org/A180632]A180632[/url](n) <= n! + (n-1)! + ... + 2! + 1!.

 science_man_88 2018-02-01 22:02

[QUOTE=CRGreathouse;478967]True, but the bounds are pretty tight: n! + (n-1)! + (n-2)! + n-3 <= [url=https://oeis.org/A180632]A180632[/url](n) <= n! + (n-1)! + ... + 2! + 1!.[/QUOTE]

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.

 CRGreathouse 2018-02-01 22:26

[QUOTE=science_man_88;479026]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.[/QUOTE]

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.

 science_man_88 2018-02-01 23:28

[QUOTE=CRGreathouse;479030]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.[/QUOTE]

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.

 CRGreathouse 2018-02-02 02:38

[QUOTE=science_man_88;479034]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.[/QUOTE]

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.

 science_man_88 2018-02-02 03:25

[QUOTE=CRGreathouse;479049]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.[/QUOTE]

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.

 science_man_88 2018-02-03 18:49

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 2018-02-04 03:23

[YOUTUBE]5SfXqTENV_Q[/YOUTUBE]. 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.

All times are UTC. The time now is 03:07.