PrimeGrid
Please visit donation page to help the project cover running costs for this month

Toggle Menu

Join PrimeGrid

  1. Read our rules and policies.
  2. Download, install and run the BOINC software used by PrimeGrid.
  3. When prompted, enter the URL:
    http://dev.primegrid.com/
  4. Select which subprojects to run via the PrimeGrid Preferences.

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise

Advanced search

Message boards : General discussion : Sieving: is each prime only considered as factor of one composite?

Post to thread Subscribe Sort
Author Message
Profile BurProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Feb 20
Posts: 332
ID: 1241833
Credit: 22,611,276
RAC: 0
321 LLR Gold: Earned 500,000 credits (538,216)Cullen LLR Amethyst: Earned 1,000,000 credits (1,169,946)ESP LLR Gold: Earned 500,000 credits (636,842)Generalized Cullen/Woodall LLR Silver: Earned 100,000 credits (212,232)PPS LLR Gold: Earned 500,000 credits (883,715)PSP LLR Gold: Earned 500,000 credits (663,928)SoB LLR Silver: Earned 100,000 credits (217,346)SR5 LLR Gold: Earned 500,000 credits (531,229)SGS LLR Amethyst: Earned 1,000,000 credits (1,042,382)TRP LLR Gold: Earned 500,000 credits (561,429)Woodall LLR Gold: Earned 500,000 credits (781,741)321 Sieve Ruby: Earned 2,000,000 credits (2,107,153)PPS Sieve Amethyst: Earned 1,000,000 credits (1,045,010)AP 26/27 Ruby: Earned 2,000,000 credits (2,470,273)GFN Turquoise: Earned 5,000,000 credits (7,129,018)PSA Silver: Earned 100,000 credits (244,815)
Message 143609 - Posted: 24 Sep 2020 | 7:02:34 UTC

I do some manual sieving with sr2sieve and it seems like every potential factor is only tested until one composite is found that it divides. Then that factor/composite pair is logged and the next potential factor is considered.

Is it like that? If so, why? :) It's not unlikely that one prime is the factor of more than one candidate in the sieve.
____________
Primes: 1281979 & 12+8+1979 & 1+2+8+1+9+7+9 & 1^2+2^2+8^2+1^2+9^2+7^2+9^2 & 12*8+19*79 & 12^8-1979 & 1281979 + 4 (cousin prime)

ID: 143609 | Report as offensive    Reply Quote
Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1378
ID: 306875
Credit: 21,623,822
RAC: 0
Found 1 prime in the 2020 Tour de Primes321 LLR Gold: Earned 500,000 credits (529,293)Cullen LLR Gold: Earned 500,000 credits (611,298)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Turquoise: Earned 5,000,000 credits (9,594,179)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Silver: Earned 100,000 credits (145,419)SGS LLR Silver: Earned 100,000 credits (105,212)TRP LLR Silver: Earned 100,000 credits (342,501)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve Silver: Earned 100,000 credits (175,037)PPS Sieve Bronze: Earned 10,000 credits (10,113)AP 26/27 Bronze: Earned 10,000 credits (12,129)GFN Amethyst: Earned 1,000,000 credits (1,674,106)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 143610 - Posted: 24 Sep 2020 | 7:24:32 UTC

No, it would not work like that. But what are you sieving, and why does it seem to you that the sieve will miss cases where one p eliminates more than one candidate? Especially in the beginning, when the p are small, it should be a frequent occurrence that one p is found to divide more than one candidate. /JeppeSN

ID: 143610 | Report as offensive    Reply Quote
Profile BurProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Feb 20
Posts: 332
ID: 1241833
Credit: 22,611,276
RAC: 0
321 LLR Gold: Earned 500,000 credits (538,216)Cullen LLR Amethyst: Earned 1,000,000 credits (1,169,946)ESP LLR Gold: Earned 500,000 credits (636,842)Generalized Cullen/Woodall LLR Silver: Earned 100,000 credits (212,232)PPS LLR Gold: Earned 500,000 credits (883,715)PSP LLR Gold: Earned 500,000 credits (663,928)SoB LLR Silver: Earned 100,000 credits (217,346)SR5 LLR Gold: Earned 500,000 credits (531,229)SGS LLR Amethyst: Earned 1,000,000 credits (1,042,382)TRP LLR Gold: Earned 500,000 credits (561,429)Woodall LLR Gold: Earned 500,000 credits (781,741)321 Sieve Ruby: Earned 2,000,000 credits (2,107,153)PPS Sieve Amethyst: Earned 1,000,000 credits (1,045,010)AP 26/27 Ruby: Earned 2,000,000 credits (2,470,273)GFN Turquoise: Earned 5,000,000 credits (7,129,018)PSA Silver: Earned 100,000 credits (244,815)
Message 143654 - Posted: 25 Sep 2020 | 6:53:17 UTC - in response to Message 143610.

I'm using sr2sieve to sieve Proth with large k (far out of PG's range) and 1E5 <= n<= 4E6.

It seemed to me like that because I never saw that a factor turned up more than once. Now that I write it, it sounds a bit stupid... So I either just missed it or it happens rarely, but each prime is tested against all candidates?

I guess it just happens very rarely, just now I found about 400 composites with 4E12 prime factors. that means only one in 1E10 primes was actually a factor. So the chance that one prime factors more than one candidate is very low in that range.
____________
Primes: 1281979 & 12+8+1979 & 1+2+8+1+9+7+9 & 1^2+2^2+8^2+1^2+9^2+7^2+9^2 & 12*8+19*79 & 12^8-1979 & 1281979 + 4 (cousin prime)

ID: 143654 | Report as offensive    Reply Quote
Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1378
ID: 306875
Credit: 21,623,822
RAC: 0
Found 1 prime in the 2020 Tour de Primes321 LLR Gold: Earned 500,000 credits (529,293)Cullen LLR Gold: Earned 500,000 credits (611,298)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Turquoise: Earned 5,000,000 credits (9,594,179)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Silver: Earned 100,000 credits (145,419)SGS LLR Silver: Earned 100,000 credits (105,212)TRP LLR Silver: Earned 100,000 credits (342,501)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve Silver: Earned 100,000 credits (175,037)PPS Sieve Bronze: Earned 10,000 credits (10,113)AP 26/27 Bronze: Earned 10,000 credits (12,129)GFN Amethyst: Earned 1,000,000 credits (1,674,106)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 143680 - Posted: 25 Sep 2020 | 18:01:06 UTC - in response to Message 143654.

I'm using sr2sieve to sieve Proth with large k (far out of PG's range) and 1E5 <= n<= 4E6.

It seemed to me like that because I never saw that a factor turned up more than once. Now that I write it, it sounds a bit stupid... So I either just missed it or it happens rarely, but each prime is tested against all candidates?

I guess it just happens very rarely, just now I found about 400 composites with 4E12 prime factors. that means only one in 1E10 primes was actually a factor. So the chance that one prime factors more than one candidate is very low in that range.


You are absolutely correct! /JeppeSN

ID: 143680 | Report as offensive    Reply Quote
Post to thread

Message boards : General discussion : Sieving: is each prime only considered as factor of one composite?

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2022 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 0.09, 0.15, 0.08
Generated 26 May 2022 | 11:40:30 UTC