mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-02-15, 04:17   #34
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

2×3×5×313 Posts
Default

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

Name:	1.JPG
Views:	43
Size:	231.3 KB
ID:	24320

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

Name:	2.JPG
Views:	40
Size:	216.0 KB
ID:	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).

Last fiddled with by LaurV on 2021-02-15 at 04:56
LaurV is online now   Reply With Quote
Old 2021-02-16, 00:38   #35
mattprim
 
mattprim's Avatar
 
Feb 2021
Salt Lake City, UT

2910 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.

Last fiddled with by mattprim on 2021-02-16 at 01:22
mattprim is offline   Reply With Quote
Old 2021-02-16, 00:50   #36
mattprim
 
mattprim's Avatar
 
Feb 2021
Salt Lake City, UT

2910 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.

Last fiddled with by mattprim on 2021-02-16 at 00:59
mattprim is offline   Reply With Quote
Old 2021-02-16, 00:57   #37
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

19×191 Posts
Default

Quote:
Originally Posted by mattprim View Post
S PariGP has no random number generator.
it has random() and randomprime()
paulunderwood is offline   Reply With Quote
Old 2021-02-16, 01:23   #38
mattprim
 
mattprim's Avatar
 
Feb 2021
Salt Lake City, UT

29 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
it has random() and randomprime()
OK. But the list is faster than the frequent calls.

Last fiddled with by mattprim on 2021-02-16 at 01:26
mattprim is offline   Reply With Quote
Old 2021-02-16, 01:28   #39
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

137608 Posts
Default

Quote:
Originally Posted by mattprim View Post
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.

Last fiddled with by retina on 2021-02-16 at 07:13
retina is offline   Reply With Quote
Old 2021-02-16, 07:09   #40
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

2×3×5×313 Posts
Default

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).

Last fiddled with by LaurV on 2021-02-16 at 07:25
LaurV is online now   Reply With Quote
Old 2021-02-16, 09:29   #41
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·37·127 Posts
Default

I still think that he is fixing his wristwatch with a bread knife.
Batalov is offline   Reply With Quote
Old 2021-02-16, 09:33   #42
mattprim
 
mattprim's Avatar
 
Feb 2021
Salt Lake City, UT

29 Posts
Default

Quote:
Originally Posted by retina View Post
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.

Last fiddled with by mattprim on 2021-02-16 at 09:49
mattprim is offline   Reply With Quote
Old 2021-02-16, 09:50   #43
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

2·3·5·313 Posts
Default

Quote:
Originally Posted by mattprim View Post
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.

Last fiddled with by LaurV on 2021-02-16 at 09:55
LaurV is online now   Reply With Quote
Old 2021-02-16, 12:43   #44
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

116618 Posts
Default

Criterion met
Quote:
Originally Posted by LaurV View Post
- code piece without code tags
See also https://www.mersenneforum.org/showthread.php?t=23996

Last fiddled with by kriesel on 2021-02-16 at 12:48
kriesel is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Searching for m. primes is like playing lottery joblack Lounge 20 2009-01-05 15:18
to be faster at searching mersenne primes flosculus Information & Answers 6 2008-11-10 18:59
searching for Mersenne primes davieddy Math 7 2007-08-21 04:51
A Proposal for searching Recurrence Series Primes Erasmus Factoring 3 2004-05-14 09:26
Need help with math problem re: searching for all primes. daxm Miscellaneous Math 5 2003-07-20 19:32

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

Fri Apr 23 04:14:38 UTC 2021 up 14 days, 22:55, 0 users, load averages: 2.80, 2.27, 1.95

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.