mersenneforum.org Endorsement Prime Numbers finding algorithm
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2017-11-03, 13:14 #1 marouane     Nov 2017 Morocco 7 Posts Endorsement Prime Numbers finding algorithm Hi, Iam looking for endorsement to publish my prime numbers finding algorithm that I've invented about 3 years ago. the algorithm is an optimization to the segmented sieve of Eratosthenes,it finds primes up to N without any repetition of multiples of primes, its time complexity is sublinear. The one who will endorse this research will be my co-author. The algorithm could be found here => http://vixra.org/pdf/1505.0119v2.pdf Thank you
2017-11-03, 13:44   #2
paulunderwood

Sep 2002
Database er0rr

3×1,327 Posts

Quote:
 Originally Posted by marouane Hi, Iam looking for endorsement to publish my prime numbers finding algorithm that I've invented about 3 years ago. the algorithm is an optimization to the segmented sieve of Eratosthenes,it finds primes up to N without any repetition of multiples of primes, its time complexity is sublinear. The one who will endorse this research will be my co-author. The algorithm could be found here => http://vixra.org/pdf/1505.0119v2.pdf Thank you
Quote:
 the composite number 360 can be written as 23 x 32 x 5
That should be 3680.

Quote:
 this is the most efficient way to obtain a large range of primes.In this present
There are many examples of where there is no space after a comma or a full stop. Don't put a space before a comma, before a question mark or a closing ")".

Also make your margins smaller with something like this in the header (before begin document):

Code:
\addtolength{\oddsidemargin}{-.875in}
\addtolength{\textheight}{1.75in}
Run it through a spell checker!

Capitalize at least the first word of the title. Begin every sentence with a capital letter.

(I am not commenting on the validity of this as a new algorithm -- I will leave that to someone else.)

Last fiddled with by paulunderwood on 2017-11-03 at 14:23

2017-11-03, 14:23   #3
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

1,531 Posts

Quote:
 Originally Posted by marouane Hi, Iam looking for endorsement to publish my prime numbers finding algorithm that I've invented about 3 years ago. the algorithm is an optimization to the segmented sieve of Eratosthenes,it finds primes up to N without any repetition of multiples of primes, its time complexity is sublinear. The one who will endorse this research will be my co-author. The algorithm could be found here => http://vixra.org/pdf/1505.0119v2.pdf Thank you
There are multiple issues with your article. The first is that in your last line what you give for S_N is actually negative for N>15. The second is that you can give negative numbers behind the O symbol, though it is far from standard. The third is that your algorithm's complexity is not sublinear.

2017-11-03, 14:50   #4
marouane

Nov 2017
Morocco

78 Posts

Quote:
 Originally Posted by R. Gerbicz There are multiple issues with your article. The first is that in your last line what you give for S_N is actually negative for N>15. The second is that you can give negative numbers behind the O symbol, though it is far from standard. The third is that your algorithm's complexity is not sublinear.
I didn't revise it since years ago, it may contains some errors yes, but the algorithm itself is something new, I am looking for someone who can refine it so that we can publish it in a scientific journal

2017-11-03, 14:51   #5
Dr Sardonicus

Feb 2017
Nowhere

23·233 Posts

Near the end, it says (I cleaned up the expression $p_{n}\le\sqrt{N}$ for the upper limit)

Quote:
 It’s well known that $\frac{N}{2}\sum_{p_{n}=3}^{\sqrt{N}}(\frac{1}p_{n} + 1)\approx N loglogN$
Apart from a missing factor of 1/2, there's a bigger problem: That "+1" in the summation completely swamps the $\frac{1}{p_{n}}$. Adding up the 1's gives $\pi(\sqrt{N})$. Multiplying by the N/2 outside the summation, would appear to give something like N*sqrt(N)/log(N).

2017-11-03, 14:57   #6
marouane

Nov 2017
Morocco

1112 Posts

Quote:
 Originally Posted by Dr Sardonicus Near the end, it says (I cleaned up the expression $p_{n}\le\sqrt{N}$ for the upper limit) Apart from a missing factor of 1/2, there's a bigger problem: That "+1" in the summation completely swamps the $\frac{1}{p_{n}}$. Adding up the 1's gives $\pi(\sqrt{N})$. Multiplying by the N/2 outside the summation, would appear to give something like N*sqrt(N)/log(N).
Thank you,
The computational analysis I did may be wrong, but what do you think about the algorithm itself ?

2017-11-03, 15:56   #7
Dr Sardonicus

Feb 2017
Nowhere

10100111011112 Posts

Quote:
 Originally Posted by marouane Thank you, The computational analysis I did may be wrong, but what do you think about the algorithm itself ?
I am certainly no expert at assessing the amount of computation required, but I did wonder at the first step of the procedure:
Quote:
 To find primes in the interval [a, b] , we must first ﬁnd the primes from 3 up to $\sqrt{b}$, for this, the first thing to do is to use equation 1 to cross off all multiples of 3 up to $\sqrt{b}$.
This would seem to require at least sqrt(b) addressable locations, and a way to tell whether each is "crossed off" as composite. There may be ways around that, I don't know.

In any event, the first step requires you to specify all the primes up to sqrt(b). I don't know the computational cost of doing that, but if b is at all large my guess is, "a lot."

2017-11-03, 16:53   #8
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by Dr Sardonicus I am certainly no expert at assessing the amount of computation required, but I did wonder at the first step of the procedure:This would seem to require at least sqrt(b) addressable locations, and a way to tell whether each is "crossed off" as composite. There may be ways around that, I don't know. In any event, the first step requires you to specify all the primes up to sqrt(b). I don't know the computational cost of doing that, but if b is at all large my guess is, "a lot."
bit accessing might speed it up you can use bits as the elements of an array. also once you find 9 you can just add three to the bit index until you need a whole new set of bits in the array then the pointer would change.

2017-11-03, 22:43   #9
CRGreathouse

Aug 2006

135338 Posts

Quote:
 Originally Posted by Dr Sardonicus I am certainly no expert at assessing the amount of computation required, but I did wonder at the first step of the procedure:This would seem to require at least sqrt(b) addressable locations, and a way to tell whether each is "crossed off" as composite. There may be ways around that, I don't know. In any event, the first step requires you to specify all the primes up to sqrt(b). I don't know the computational cost of doing that, but if b is at all large my guess is, "a lot."
I don't think these are problems. Sure, if you can do with less than sqrt(b) memory that would be great, and it would also be great if you didn't need to sieve up to sqrt(b). But neither is necessarily make-or-break for a sieving algorithm (though I increasingly favor ones using on the order of cube root space over the square root ones).

On the other hand your earlier issue, like the ones R. Gerbicz identified, are pretty bad. I certainly wouldn't endorse a paper in this state. But if I have a chance I'll look over the algorithm.

Last fiddled with by CRGreathouse on 2017-11-03 at 22:44

2017-11-03, 22:57   #10
marouane

Nov 2017
Morocco

7 Posts

Quote:
 Originally Posted by CRGreathouse I don't think these are problems. Sure, if you can do with less than sqrt(b) memory that would be great, and it would also be great if you didn't need to sieve up to sqrt(b). But neither is necessarily make-or-break for a sieving algorithm (though I increasingly favor ones using on the order of cube root space over the square root ones). On the other hand your earlier issue, like the ones R. Gerbicz identified, are pretty bad. I certainly wouldn't endorse a paper in this state. But if I have a chance I'll look over the algorithm.
The issue on the computational analysis is one of the reasons why I posted this thread, I want to find someone who'll look deeply into the algorithm and re-posting a new clean publication

2017-11-04, 01:04   #11
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by marouane The issue on the computational analysis is one of the reasons why I posted this thread, I want to find someone who'll look deeply into the algorithm and re-posting a new clean publication
Euler's sieve can be used at least for smaller values.

a few more typos to fix:
earliar -> earlier
wich -> which

 Similar Threads Thread Thread Starter Forum Replies Last Post Ale Miscellaneous Math 38 2015-11-29 23:27 T.Rex Miscellaneous Math 10 2015-09-01 18:07 T.Rex Miscellaneous Math 13 2015-09-01 13:09 georgelouis@mac Math 41 2011-01-25 21:06 dilip_1bhowmik Miscellaneous Math 22 2009-01-09 23:39

All times are UTC. The time now is 10:02.

Sun Jan 23 10:02:04 UTC 2022 up 184 days, 4:31, 0 users, load averages: 1.18, 1.18, 1.11

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

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