mersenneforum.org "New" primality test/check
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2017-12-29, 06:53 #78 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 274516 Posts Subjectively, they can feel as if they are still alive for a long time. Ambrose Bierce described that in 'An Occurrence at Owl Creek Bridge'.
2017-12-29, 09:33   #79
gophne

Feb 2017

3·5·11 Posts

Quote:
 Originally Posted by ewmayer Yeah, we heard you the first million-and-six times. Try (n+2) = 2047 = 23*89 in your formula.
Hi ewmayer[B]

You are correct, that is a false positive (prime) result returned by the algorith. There are others as well. If you run the Code that I posted #73, you can identify many more. False positives are not uncommon with Primality algorithms, only the percentage of false positives w.r.t total number of "primes" tested

-Refer Fermat Primality test which have "......21853 pseudoprimes base 2 that are less than 2.5×10^10 (see page 1005 of [4]). This means that, for n up to 2.5×10^10, if 2n−1 (modulo n) equals 1, then n is prime, unless n is one of these 21853 pseudoprimes"......Source https://en.wikipedia.org/wiki/Primality_test

Indications are that this algorithm will have less false positives at 2.5x10^10, currently sitting at +-750 at 10^7 and decreasing trend with increasing magnitude. Interestingly the smallest false positive for the Fermat primality test is also the smallest false positive for this algorithm!!! -341

Last fiddled with by gophne on 2017-12-29 at 09:39 Reason: Adding exponent sign for Fermat Pseudoprime figure

2017-12-29, 09:52   #80
gophne

Feb 2017

3·5·11 Posts

Quote:
 Originally Posted by Batalov A person who walks off a 1km cliff also doesn't understand that he is already dead. But he is. This is exactly what is called a 2-PRP test. 1) It is >350 years old. 2) It is false. Try n+2 == 341. (2^n-1) mod (n+2) = (n+1)/2, then (n+2) is PRIME? Wrong. It is composite. F. Sarrus in 1820 found 341 as one of the first pseudoprimes, to base 2. That was 197 years ago. Try n+2 == 561. (2^n-1) mod (n+2) = (n+1)/2, then (n+2) is PRIME? Wrong. It is composite. Try n+2 == 645. (2^n-1) mod (n+2) = (n+1)/2, then (n+2) is PRIME? Wrong. It is composite.
Hi Batalov

Fermat Primality Test has 21,853 pseudo-primes in 2.5x10^10....refer my post #79 for reference for this figure. Do you consider the Fermat Primality Test fake as well based on your reasoning/reference?

You refer to 3 examples, I have listed (and have provided Code) for 245 false primes up to 1,000,000 (magnitude)

Last fiddled with by gophne on 2017-12-29 at 09:54 Reason: Correct spellin/grammar errors

 2017-12-29, 15:56 #81 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 32·1,117 Posts There is no reason for this self-flagellation to go on. Please meditate in silence. Or ask for your own logorrhea thread. The thread is locked.
 2017-12-29, 23:17 #82 ewmayer ∂2ω=0     Sep 2002 República de California 5×2,351 Posts Briefly reopening the thread for the benefit of our less-mathematical readers who may not see why the test in question is simply a base-2 Fermat pseudoprime test in disguise - start with the OP's version: (2^n-1) == (n+1)/2 mod (n+2) Replace the silly 'n+2' modulus by n, i.e. everywhere in the formula subtract 2 from n: 2^(n-2) - 1 == (n-1)/2 (mod n) Multiply by 2: 2^(n-1) - 2 == (n-1) (mod n) == -1 (mod n) Add 2 to both sides: 2^(n-1) == 1 (mod n) . QED Last fiddled with by ewmayer on 2017-12-29 at 23:17
2017-12-30, 18:36   #83
gophne

Feb 2017

3×5×11 Posts

Quote:
 Originally Posted by ewmayer Briefly reopening the thread for the benefit of our less-mathematical readers who may not see why the test in question is simply a base-2 Fermat pseudoprime test in disguise - start with the OP's version: (2^n-1) == (n+1)/2 mod (n+2) Replace the silly 'n+2' modulus by n, i.e. everywhere in the formula subtract 2 from n: 2^(n-2) - 1 == (n-1)/2 (mod n) Multiply by 2: 2^(n-1) - 2 == (n-1) (mod n) == -1 (mod n) Add 2 to both sides: 2^(n-1) == 1 (mod n) . QED
Hi ewmayer

Thanks for your post.

I don't understand why you say my algorithm is;

(2^n-1) == (n+1)/2 mod (n+2)

I thought it was

(2^n-1) mod (n+2) == (n+1)/2

Retracing your steps would then give

[1] Replacing (n+2) with n

2^(n-2)-1 mod n == (n-1)/2

[2] Multiplying by 2

2^(n-1)-2 mod n == (n-1)

[3] Add 2 to both sides

2^(n-1) mod n == (n+1)

This is different from your result and therefore not the algorith you reduced. Similar, but very different, like 1 is different from 2

Am I mistaken with this? If you would concur it would still mean my algorithm is original.

2017-12-30, 18:42   #84
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

32·1,117 Posts

Quote:
 Originally Posted by gophne Am I mistaken with this? If you would concur it would still mean my algorithm is original.
You are.

Do you always read only the second explanation? First is not enough? It has to be repeated twice?
What Ernst wrote I already spelled out for you two days ago.

2017-12-30, 18:57   #85
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

32·101 Posts

Quote:
 Originally Posted by gophne I don't understand why you say my algorithm is; (2^n-1) == (n+1)/2 mod (n+2)
It's the usual way of writing a congruence equation. Both sides use modular arithmetic. You seem to be assuming only one.

Quote:
 [...] 2^(n-1) mod n == (n+1)
If this is a congruence, then n+1 also has mod n applied, which means it is equivalent to 1, as they said. If you insist it is not, then how exactly could it *ever* be true? The lifted result of x mod n is always in the range 0 to n-1, so clearly it cannot be n+1.

2017-12-30, 19:01   #86
gophne

Feb 2017

101001012 Posts

Quote:
 Originally Posted by Batalov You are. Do you always read only the second explanation? First is not enough? It has to be repeated twice? What Ernst wrote I already spelled out for you two days ago.
Hi Batalov

I respect your opinions as an expert and a Mod. However I have a right to defend myself as well.

Please look at my reply to ewmayer in post #83 and correct me where I am wrong/mistaken.

According to my humble understanding I do not think that the two are the same. Please explain how you can say the two algoriths are the same when ewmayer appears to have tweaked my algorithm, possibly unintentionally. Just juxtapose the two. They are not the same -look at the formulas, not the same as what ewmayer reworked.

But thanks for taking me to task, but I will try to defend my position as I understand -sometimes ignorance is bliss.

I will also see how other users understand the issues, but for now I cannot agree that what ewmayer "re-worked" is the algorithm I posted.

Thanks

Last fiddled with by gophne on 2017-12-30 at 19:03 Reason: grammar

2017-12-30, 19:49   #87
ATH
Einyen

Dec 2003
Denmark

2·17·101 Posts

Quote:
 Originally Posted by gophne I don't understand why you say my algorithm is; (2^n-1) == (n+1)/2 mod (n+2) I thought it was (2^n-1) mod (n+2) == (n+1)/2
The top line is just the usual way of writing modular equations, it means the same thing as you intend.

Quote:
 2^(n-1) mod n == (n+1) This is different from your result and therefore not the algorith you reduced. Similar, but very different, like 1 is different from 2 Am I mistaken with this? If you would concur it would still mean my algorithm is original.

If something is equal to (n+1) mod n, then it is also equal to 1 mod n, and equal to 2n+1 mod n and 3n+1 mod n and so on.

If say n=5:

Then:
31 mod n = 1 because 31=6*n + 1
31 mod n = 6 = n+1 because 31= 5*n + 6
31 mod n = 11 = 2n+1 because 31 = 4*n + 11
and so on.

Last fiddled with by ATH on 2017-12-30 at 19:50

2017-12-30, 21:42   #88
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

32×1,117 Posts

I wrote a ground-breaking new poem and I shall go around telling everyone that I've truly made something out of myself. Here is small bit of it. I have more, much more! --
Quote:
 To be or not to be - that is the question: If it is nobler in the mind to suffer The slings and arrows of outrageous fortune Or to take arms against a sea of troubles And by opposing end them.
Now some people keep telling me that some guy with a spear (never heard of him) already wrote something similar. But it is false. Mine is completely different. His version has some extra commas and the words are not the same; first of all, they are completely unnecessary, and secondly, surely this makes it not the same.

 Similar Threads Thread Thread Starter Forum Replies Last Post preda GpuOwl 2908 2023-01-30 01:25 Chair Zhuang Miscellaneous Math 21 2018-03-26 22:33 wildrabbitt Miscellaneous Math 11 2015-03-06 08:17 ewmayer Math 11 2007-04-23 19:07 James Heinrich Software 2 2005-03-19 21:58

All times are UTC. The time now is 19:05.

Wed Feb 1 19:05:22 UTC 2023 up 167 days, 16:33, 0 users, load averages: 1.16, 1.24, 1.20

Copyright ©2000 - 2023, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔