mersenneforum.org 2° Lepore sieve
 Register FAQ Search Today's Posts Mark Forums Read

2019-05-23, 17:53   #1
Alberico Lepore

May 2017
ITALY

52210 Posts
2° Lepore sieve

this sieve riddles in A + B * log_2 (B)
where A is the number of special numbers generated
and B the number of discards
what do you think?
Attached Files
 2_lepore_sieve.c (3.2 KB, 237 views)

 2019-05-23, 21:39 #2 VBCurtis     "Curtis" Feb 2005 Riverside, CA 22·3·7·67 Posts I think anyone who names something mathematical after themselves should not be taken seriously.
 2019-05-23, 23:34 #3 Alberico Lepore     May 2017 ITALY 2·32·29 Posts I found something really exceptional. Tomorrow I will find the largest prime number ever. Now in Italy it is late, but I leave you one of the formulas valid for 3 + 20 * h 939=(3+20*h)^2+(30+40*k)*(3+20*h) , (236-(26+280*h))/(10*(3+10*h))=k I'm very happy thank you Last fiddled with by Alberico Lepore on 2019-05-23 at 23:38
 2019-05-24, 03:20 #4 CRGreathouse     Aug 2006 5,987 Posts How would you say it differs from a standard sieve of Eratosthenes on arithmetic progressions?
 2019-05-24, 03:35 #5 CRGreathouse     Aug 2006 5,987 Posts Is this claiming that 99, 219, 259, 299, 339, 459, 539, 579, 699, 779, 819, 899, 939, and 979 are prime? Or am I misunderstanding? Code: Fino a che numero? (max 10000): 1000 0 99 99 219 259 299 339 459 459 459 539 539 579 699 779 819 819 819 819 819 899 939 979 p=19 p=59 p=99 p=139 p=179 p=219 p=259 p=299 p=339 p=379 p=419 p=459 p=499 p=539 p=579 p=619 p=659 p=699 p=739 p=779 p=819 p=859 p=899 p=939 p=979
2019-05-24, 09:17   #6
Alberico Lepore

May 2017
ITALY

2·32·29 Posts

Quote:
 Originally Posted by CRGreathouse Is this claiming that 99, 219, 259, 299, 339, 459, 539, 579, 699, 779, 819, 899, 939, and 979 are prime? Or am I misunderstanding? Code: Fino a che numero? (max 10000): 1000 0 99 99 219 259 299 339 459 459 459 539 539 579 699 779 819 819 819 819 819 899 939 979 p=19 p=59 p=99 p=139 p=179 p=219 p=259 p=299 p=339 p=379 p=419 p=459 p=499 p=539 p=579 p=619 p=659 p=699 p=739 p=779 p=819 p=859 p=899 p=939 p=979
p are primes

**************************************************************************************************

building a list (already ordered) I can sift the prime numbers in A by eliminating part B * log_2 (B).
The list is sorted like this
C
6
16
26
36
46
....

Finding the B (waste) C = (B + 5) / 4

Example
(99 + 5) / 4 = 26

the rest are primes
therefore the computational cost is A = p + B

moreover, there is the problem of duplication that I am still studying

P.S.
if you find the method to factorize these special numbers into O (1) you can find very large prime numbers

*********************************************************************************************************************
EDIT: I have solved the problem of duplication

Last fiddled with by Alberico Lepore on 2019-05-24 at 09:21 Reason: EDIT

2019-05-24, 09:23   #7
jnml

Feb 2012
Prague, Czech Republ

3×67 Posts

Quote:
 Originally Posted by Alberico Lepore if you find the method to factorize these special numbers into O (1) you can find very large prime numbers
Any program that reads some input number n is at least O(log n).

2019-05-24, 09:37   #8
lukerichards

"Luke Richards"
Jan 2018
Birmingham, UK

25×32 Posts

Quote:
 Originally Posted by Alberico Lepore p are primes
Quote:
 Originally Posted by Alberico Lepore p=99
99 = 11 * 3 * 3

2019-05-24, 09:53   #9
Alberico Lepore

May 2017
ITALY

2×32×29 Posts

Quote:
 Originally Posted by lukerichards 99 = 11 * 3 * 3
sorry I posted the wrong file
this is correct
Attached Files
 2_lepore_sieve.c (3.2 KB, 232 views)

 2019-05-24, 15:41 #10 Alberico Lepore     May 2017 ITALY 2·32·29 Posts which means particular solutions? https://www.wolframalpha.com/input/?...x+%3D786+mod+x https://www.wolframalpha.com/input/?...x+%3D306+mod+x
 2019-05-25, 16:48 #11 Alberico Lepore     May 2017 ITALY 52210 Posts In some cases it is very simple to factor the sieve numbers into polynomial time. I show you an example N=13899 (N+5)/4=3476 If it is feasible one of the 8 is true so let's say the real one is [(N+5)/4 -[((13+20*h)*3+5)/4]] mod (13+20*h) =0 -> [3476 -[((13+20*h)*3+5)/4]] mod (13+20*h) =0 -> (3465 -15*h) mod (13+20*h) =0 this is when 3465 divides 15 is the case in which it is factorizable in polynomial time (3465/15-h) mod (13+20*h) =0 -> (231 -h) mod (13+20*h) =0 -> 20*(231 -h) mod (13+20*h) =0 -> (4620 -20*h) mod (13+20*h) =0 (4633) mod (13+20*h) =0 GCD(13899,4633)=131 I don't know in which and how many cases this is valid what do you think? Edit: [(N+5)/4 -[((3+20*h)*13+5)/4]] mod (3+20*h) =0 [(N+5)/4 -[((13+20*h)*3+5)/4]] mod (13+20*h) =0 [(N+5)/4 -[((7+20*h)*17+5)/4]] mod (7+20*h) =0 [(N+5)/4 -[((17+20*h)*7+5)/4]] mod (17+20*h) =0 [(N+5)/4 -[((21+20*h)*39+5)/4]] mod (21+20*h) =0 [(N+5)/4 -[((11+20*h)*9+5)/4]] mod (11+20*h) =0 [(N+5)/4 -[((9+20*h)*11+5)/4]] mod (9+20*h) =0 [(N+5)/4 -[((19+20*h)*21+5)/4]] mod (19+20*h) =0 Last fiddled with by Alberico Lepore on 2019-05-25 at 17:35

 Similar Threads Thread Thread Starter Forum Replies Last Post Alberico Lepore Alberico Lepore 43 2018-01-17 15:55 Alberico Lepore Alberico Lepore 2 2018-01-01 21:31 Alberico Lepore Alberico Lepore 48 2017-12-30 09:43 Alberico Lepore Alberico Lepore 61 2017-09-23 21:52 binu Factoring 3 2013-04-13 16:32

All times are UTC. The time now is 12:37.

Sun Jan 29 12:37:39 UTC 2023 up 164 days, 10:06, 0 users, load averages: 0.76, 0.96, 0.97