Searching Mersenne Primes with Mathematica

[LaurV]

So, your output, after I fixed the alignment of the printing, to have it in a nice format for easy reading:


And the output after I fixed the math too (k is still limited to 1023, otherwise even more factors will pop up).


Do you see any difference? Can you explain why some classes always seems to repeat more often that the other classes? Can you see why you missed a lot of factors at all, and for some exponents you "accidentally" found much larger factors which fit in another class? (therefore, doing more "work" - here quotes are used because all this trouble, albeit extremely slow, still takes only few microseconds). I will let you figure out what change I made.

Remark that this method is, as said, extremely slow, it will only find out extremely small factors, and anyhow, who the hack needs trivial factors for over-10G expo range? We have headache enough to test those under 1G (Gimps range).

[mattprim]

Originally Posted by LaurV

Man, after reading your tongue twisting post #29, I am glad my teachers/professors were not like you. Well, most of them in fact; there are always exceptions.

You even don't understand what is wrong in your Mathematica algorithm. You have a series of numbers which are limited in value (the number of modular classes), and in which every term is obtained by applying a fixed, deterministic function to the previous term. \(s_0=c,\ s_n=f(s_{n-1})\). In this case, because you have an infinite number of terms, and only finite number of values, some value will repeat after a while. And if the same deterministic function is applied to the same value, you will get the same result, which means you will always get in a loop after a while. What Lucas says, is that if you take the initial value to be some specific value (like 4, 10, etc), and the function to be \(f(x)=x^2-2\) then the loop happens exactly after p iterations, and it is a loop of length 1 (i.e. it only looks like 2, 2, 2, 2...., the "fixed point") if and only if Mp is prime.

For example, if you do LL test for M9=2^9-1, you will get the string of values 4, 14, 194, 331, 205, 121, (331, 205, 121), (331, 205, 121), .... Here the loop is 3 in size.
For M11 you get repetition after 61 iterations, and the loop has size 60 (i.e. you get the value 14 again after 61 steps).
For M7, the string is 4, 14, 67, 42, 111, 0, 125, 2, 2, 2, 2,.... You enter in a fixed point loop after exactly 7 iterations.
Note that for a prime, zero appears in the string at exact position p-1 (i.e. after p-2 iterations).

However, for a composite Mp, zero may never appear, or it may appear later, or it may appear earlier. There is nothing in the mathematics involved there, to say which one it is, for any composite Mp.

What you are doing in that program, you test if the residue is zero at every iteration.

If you are not convinced, read the Mathematica syntax again, for Do-Loop. So, your program will display "prime" for all primes, and will display "composite" for the composites where zero appears later, or never. Which is right.

However, if you have a composite where 0 appears earlier in string, your program will display "prime" and continue to run the rest of the iterations, until p-2, without displaying anything else, because the result will never be zero again (it enters 2, 2, 2... loop). So, your program output is no different, in this case, for the output in the correct "prime" case. Therefore, it is wrong, it can give false positives.

My question was if you can prove that this case is never possible. Of course, that was a rhetoric question, I am sure you can't.

Moving to your precedent post (#29), the TF line of code you provide is also wrong.
It does find a lot of factors, as you claim, but it only finds about 1/96 of all the factors in range. The other about 95/96 of the factors, you will miss. Yes, there should be another 95/96 of the factors which your code is missing. Can you tell why?
Hint: because the offset in the vector depends on the modularity of p to 420, you need to rotate that vector accordingly, for each p. As it is, you test the right 96 classes ONLY for 1/96 of all possible primes p in range, and for the other 95/96 of primes, you only test few classes accidentally.

The LL test is so simple numerically that you can write your own code if you do not thrust mine. It is only more difficult to prove it works especially if you do not want to step out of the integer number space. All these problems are tied to the Last (Great) Fermat Theorem (that a^n+b^n can never be c^n for n>2) which is very difficult to prove and was proven only recently.
I rewrote here "my" code in Mathematica with the loop over the exponents. It returns the right values of the primes https://en.wikipedia.org/wiki/Mersenne_prime with exponents below 2000 so it works:

Do[
Mp = 2^p - 1;
s = 4;
Do[s = Mod[(s*s - 2), Mp];
If[s == 0, Print["PRIME"]; Print[p]], {i, 0, p - 2}], {p, 1, 2000}];

PRIME

3

PRIME

5

PRIME

7

PRIME

13

PRIME

17

PRIME

19

PRIME

31

PRIME

61

PRIME

89

PRIME

107

PRIME

127

PRIME

521

PRIME

607

PRIME

1279

Indeed the iteration is done Modulo Mp so s is not growing giant but it works. If s original is 4 then without the Modulo s after p iterations it would be enormously above Mp which is already giant for nontrivial searches only to check if it is its devisor.
I say "my" code not my code because it is so simple anyone who has some knowledge of math and Mathematica can write it.

[mattprim]

Originally Posted by LaurV

So, your output, after I fixed the alignment of the printing, to have it in a nice format for easy reading:
Attachment 24320

And the output after I fixed the math too (k is still limited to 1023, otherwise even more factors will pop up).
Attachment 24321

Do you see any difference? Can you explain why some classes always seems to repeat more often that the other classes? Can you see why you missed a lot of factors at all, and for some exponents you "accidentally" found much larger factors which fit in another class? (therefore, doing more "work" - here quotes are used because all this trouble, albeit extremely slow, still takes only few microseconds). I will let you figure out what change I made.

Remark that this method is, as said, extremely slow, it will only find out extremely small factors, and anyhow, who the hack needs trivial factors for over-10G expo range? We have headache enough to test those under 1G (Gimps range).

Sorry I did not write this one by myself. Someone sent it to me to show me how many Mersennes can be excluded fast. I think the loop over k here is not continuous but has quasi-random steps from the list to add some Monte Carlo. PariGP has no random number generator.

[paulunderwood]

Originally Posted by mattprim

S PariGP has no random number generator.

it has random() and randomprime()

[mattprim]

Originally Posted by paulunderwood

it has random() and randomprime()

OK. But the list is faster than the frequent calls.

[retina]

Originally Posted by mattprim

I rewrote here "my" code in Mathematica with the loop over the exponents. It returns the right values of the primes https://en.wikipedia.org/wiki/Mersenne_prime with exponents below 2000 so it works.

From that test all you know is that it works for exponents below 2000. You still haven't proven anything with the mathematics.

Read up about quadratic residues.

[LaurV]

I think this guy is trolling. Like, a 7, on a 0 to 10 scale. He doesn't reply to any question, deliberately ignores all the explanation, even if it is done "children level", even after quoting the whole text completely, insists in his mistakes, deliberately write bullshit pieces of code (or to test us?) which he claims to be big inventions, and when caught, blames somebody else. Not my gun, someone else gave it to me, sorry I shot you all... Writing complicate phrases with a lot of technical terms which are irrelevant (irrational bullshit relaed to LL test, and monte carlo, related to TF, haha), just to look "documented". Posting long list of insignificant and small values (repeatedly). Typical troll behavior. Unless he is very young and just learning his stuff, or very stupid, or both. My days of applying Hanlon's Razor for him are gone. I tried my best to explain him what mistakes he does, but it seems he doesn't learn. Out of here.

I would propose the following: One week ban if he posts any of the following:
- code piece without code tags
- output of the code (lists of small, irrelevant numbers, with lots of spaces) without code tags
- any definitive claim about any software or hardware tool, without previous research (like "pari doesn't have this function").
- any pompous result realized by himself ("look, I proved this number is composite", followed by a test that takes microseconds).

[Batalov]

I still think that he is fixing his wristwatch with a bread knife.

[mattprim]

Originally Posted by retina

From that test all you know is that it works for exponents below 2000. You still haven't proven anything with the mathematics.

Read up about quadratic residues.

You can find sever proofs of the LL test. Here is for example the paper from Turkey: https://cs.uwaterloo.ca/journals/JIS...lli/kucuk3.pdf with the references to other papers with various methods. Some like the one in the paper are quite cumbersome.
The code I posted:

Do[
Mp = 2^p - 1;
s = 4;
Do[s = Mod[(s*s - 2), Mp];
If[s == 0, Print["PRIME"]; Print[p]], {i, 0, p - 2}], {p, 1, 2000}];

runs below 1 minute to early 1950's results but you can compile and run Mathematica in parallel even on IBM Sequoia https://en.wikipedia.org/wiki/Sequoia_(supercomputer) supercomputer https://www.rankred.com/fastest-supe...-in-the-world/ to sweep the loop much higher even to find the bigger than from 2018. It has 1572864 cores and can also do FFT parallelly partitioning it among them.

[LaurV]

Originally Posted by mattprim

You can find sever [sic] proofs of the LL test.

Yes, but what you have implemented is NOT the LL test. The irony is that you are not even able to see the difference
Edit: probably somebody gave you this code too, same as before, and you have no clue what you are talking about.

[kriesel]

Criterion met

Originally Posted by LaurV

- code piece without code tags

See also https://www.mersenneforum.org/showthread.php?t=23996