mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2017-11-03, 13:14   #1
marouane
 
marouane's Avatar
 
Nov 2017
Morocco

7 Posts
Lightbulb 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
marouane is offline   Reply With Quote
Old 2017-11-03, 13:44   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·7·281 Posts
Default

Quote:
Originally Posted by marouane View Post
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{\evensidemargin}{-.875in}
\addtolength{\textwidth}{1.75in}
\addtolength{\topmargin}{-.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
paulunderwood is offline   Reply With Quote
Old 2017-11-03, 14:23   #3
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·3·11·23 Posts
Default

Quote:
Originally Posted by marouane View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2017-11-03, 14:50   #4
marouane
 
marouane's Avatar
 
Nov 2017
Morocco

7 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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
marouane is offline   Reply With Quote
Old 2017-11-03, 14:51   #5
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

19×269 Posts
Default

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).
Dr Sardonicus is offline   Reply With Quote
Old 2017-11-03, 14:57   #6
marouane
 
marouane's Avatar
 
Nov 2017
Morocco

710 Posts
Talking

Quote:
Originally Posted by Dr Sardonicus View Post
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 ?
marouane is offline   Reply With Quote
Old 2017-11-03, 15:56   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

117678 Posts
Default

Quote:
Originally Posted by marouane View Post
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 find 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."
Dr Sardonicus is offline   Reply With Quote
Old 2017-11-03, 16:53   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.
science_man_88 is offline   Reply With Quote
Old 2017-11-03, 22:43   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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
CRGreathouse is offline   Reply With Quote
Old 2017-11-03, 22:57   #10
marouane
 
marouane's Avatar
 
Nov 2017
Morocco

7 Posts
Smile

Quote:
Originally Posted by CRGreathouse View Post
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
marouane is offline   Reply With Quote
Old 2017-11-04, 01:04   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by marouane View Post
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
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
This simple algorithm incomplete can only calculate prime numbers? Ale Miscellaneous Math 38 2015-11-29 23:27
OEIS - (2^n-5)/3 - n odd - LLT-like algorithm for finding PRPs T.Rex Miscellaneous Math 10 2015-09-01 18:07
OEIS - 2^n-5 - LLT-like algorithm for finding PRPs T.Rex Miscellaneous Math 13 2015-09-01 13:09
New method of finding large prime numbers georgelouis@mac Math 41 2011-01-25 21:06
New Prime-Finding Algorithm Discovered! L00K HERE! dilip_1bhowmik Miscellaneous Math 22 2009-01-09 23:39

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


Mon Nov 29 03:05:27 UTC 2021 up 128 days, 21:34, 0 users, load averages: 1.22, 1.15, 1.12

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.