mersenneforum.org mtsieve
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2022-10-27, 13:07   #738
rogue

"Mark"
Apr 2003
Between here and the

2·3,527 Posts

Quote:
 Originally Posted by SethTro Did this issue ever get fixed? I think I'm running into it again (but possible a different issue) Code: \$ ./srsieve2 -W1 -p 10 -P 1e8 -n 10 -N 300000 -s "1*9^n-7" srsieve2 v1.6.4, a program to find factors of k*b^n+c numbers for fixed b and variable k and n Sieving with generic logic for p >= 10 Sieve started: 10 < p < 1e8 with 299991 terms (10 < n < 300000, k*9^n-7) (expecting 262492 factors) Sieving with single sequence c=1 logic for p >= 257 BASE_MULTIPLE = 30, POWER_RESIDUE_LCM = 720, LIMIT_BASE = 720 Split 1 base 9 sequence into 132 base 9^180 sequences. Legendre summary: Approximately 2 B needed for Legendre tables ... 518400 bytes used for congruent q and ladder indices 263200 bytes used for congruent qs and ladders Fatal Error: Invalid factor: 1*9^39060-7 mod 1303 = 1297 I'm sieving "(3^n-7)/2" which I think I can hack to avoid d by testing 9^n-7 and disabling the division by 2 test. I'm excited that srsieve2 might be 10-100x faster than my hand coded sieve.
Sorry, but I have not. I am mainly stuck on how to handle terms that are not divisible by the divisor. For example if you had (3^n-1)/5, then how do I handle terms where 3^n-1 is not already divisible by 5. I think that pfgw actually tests floor((3^n-1)/5). The challenge is two-fold. Just because p divides 3^n-1 for some value of n, it doesn't mean that p divides floor(3^n-1)/5 for that same value of n. The converse is also true. p could divide floor(3^n-1)/5, but does not divide 3^n-1. The algorithm behind srsieve2 works by finding factors of 3^n-1 so it cannot find some of the factors that would divide floor((3^n-1)/5).

Given the values you have for k, b, c, and d, 3^n-7 is always even, so always divisible by 2. I could make a change to support sieving sequences meeting these criteria:
• d is prime
• d evenly divides all k*b^n+c terms

I would then need to:
• Remove all terms where k*b^n+c is divisible by d^2
• Skip the discrete log where d = p.

That would mean that all factors found by the discrete log divide both k*b^n+c and (k*b^n+c)/d.

I don't know when I can complete this, but it is the best I can offer at this time.

2022-10-27, 15:40   #739
SethTro

"Seth"
Apr 2019

2·5·72 Posts

Quote:
 Originally Posted by rogue Sorry, but I have not. I am mainly stuck on how to handle terms that are not divisible by the divisor. For example if you had (3^n-1)/5, then how do I handle terms where 3^n-1 is not already divisible by 5. I think that pfgw actually tests floor((3^n-1)/5). The challenge is two-fold. Just because p divides 3^n-1 for some value of n, it doesn't mean that p divides floor(3^n-1)/5 for that same value of n. The converse is also true. p could divide floor(3^n-1)/5, but does not divide 3^n-1. The algorithm behind srsieve2 works by finding factors of 3^n-1 so it cannot find some of the factors that would divide floor((3^n-1)/5). Given the values you have for k, b, c, and d, 3^n-7 is always even, so always divisible by 2. I could make a change to support sieving sequences meeting these criteria: d is prime d evenly divides all k*b^n+c terms I would then need to: Remove all terms where k*b^n+c is divisible by d^2 Skip the discrete log where d = p. That would mean that all factors found by the discrete log divide both k*b^n+c and (k*b^n+c)/d. I don't know when I can complete this, but it is the best I can offer at this time.

I coded my own slower sieve so this is low priority, I'll also play around and see if I can hack mtsieve to work for my specific case.

2022-10-27, 16:39   #740
SethTro

"Seth"
Apr 2019

2×5×72 Posts

Quote:
 Originally Posted by rogue Sorry, but I have not. I am mainly stuck on how to handle terms that are not divisible by the divisor. For example if you had (3^n-1)/5, then how do I handle terms where 3^n-1 is not already divisible by 5. I think that pfgw actually tests floor((3^n-1)/5). The challenge is two-fold. Just because p divides 3^n-1 for some value of n, it doesn't mean that p divides floor(3^n-1)/5 for that same value of n. The converse is also true. p could divide floor(3^n-1)/5, but does not divide 3^n-1. The algorithm behind srsieve2 works by finding factors of 3^n-1 so it cannot find some of the factors that would divide floor((3^n-1)/5). Given the values you have for k, b, c, and d, 3^n-7 is always even, so always divisible by 2. I could make a change to support sieving sequences meeting these criteria: d is prime d evenly divides all k*b^n+c terms I would then need to: Remove all terms where k*b^n+c is divisible by d^2 Skip the discrete log where d = p. That would mean that all factors found by the discrete log divide both k*b^n+c and (k*b^n+c)/d. I don't know when I can complete this, but it is the best I can offer at this time.
I coded my own slower sieve so this is low priority, I'll also play around and see if I can hack mtsieve to work for my specific case (I agree with your analysis of what would need to be done)

I'm surprised that pfgw takes the floor of the division. I have no idea what you should do in that case.

Last fiddled with by SethTro on 2022-10-27 at 17:17

 2022-10-27, 17:17 #741 SethTro     "Seth" Apr 2019 7528 Posts Solved my issue I found the source of my problem by compiling with make DEBUG=yes and using gdb. The code was running from CisOneWithOneSequenceWorker which I eventually parsed in the symbolic domain as "C Is One" instead of just a random identifier. Code: void SierpinskiRieselApp::ValidateOptions(void) { seq_t *seqPtr; ib_CanUseCIsOneLogic = true; Critically this is called AFTER AddSequence resetting ib_CanUseCIsOneLogic Code: void SierpinskiRieselApp::AddSequence(uint64_t k, int64_t c, uint32_t d) { ... uint64_t absc = abs(c); if (absc != 1) ib_CanUseCIsOneLogic = false; I can "fix" the invalid factors issue by commenting out the assignment to true. I suspect you're the person who should figure out the correct fix.
 2022-10-27, 18:44 #742 rogue     "Mark" Apr 2003 Between here and the 2×3,527 Posts AddSequence() should be called before MakeSubsequences(), which where the Helper is created. Is the wrong Helper created? It should be creating GenericSequenceHelper.
2022-10-28, 01:56   #743
SethTro

"Seth"
Apr 2019

49010 Posts

Quote:
 Originally Posted by rogue AddSequence() should be called before MakeSubsequences(), which where the Helper is created. Is the wrong Helper created? It should be creating GenericSequenceHelper.
The flow I'm seeing is

core/main:main calls
ProcessArgs calls
SierpinskiRieselApp::ParseOptions calls
where ib_CanUseCIsOneLogic set false

after that

core/main:main calls
core/App:Run calls
SierpinskiRieselApp::ValidateOptions
which resets ib_CanUseCIsOneLogic = true;
then calls
SierpinskiRieselApp::MakeSubsequences
which creates CisOneWithOneSequenceHelper
when it should be creating GenericSequenceHelper

it feels like ib_CanUseCIsOneLogic = true; should probably be moved to the constructor

Code:
Index: sierpinski_riesel/SierpinskiRieselApp.cpp
===================================================================
--- sierpinski_riesel/SierpinskiRieselApp.cpp    (revision 205)
+++ sierpinski_riesel/SierpinskiRieselApp.cpp    (working copy)
@@ -48,6 +48,8 @@
SetAppMinPrime(3);
SetAppMaxPrime(PMAX_MAX_62BIT);

+   ib_CanUseCIsOneLogic = true;
+
ii_MinN = 0;
ii_MaxN = 0;
it_Format = FF_ABCD;
@@ -233,7 +235,6 @@
void SierpinskiRieselApp::ValidateOptions(void)
{
seq_t     *seqPtr;
-   ib_CanUseCIsOneLogic = true;

if (it_Format == FF_UNKNOWN)
FatalError("the specified file format in not valid, use A (ABC), D (ABCD), P (ABC with number_primes), or B (BOINC)");

Last fiddled with by SethTro on 2022-10-28 at 01:57

 2022-10-28, 03:08 #744 sweety439   "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 368210 Posts Can you update mtsieve to make it be able to sieve the sequence (a*b^n+c)/gcd(a+c,b-1) with gcd(a+c,b-1) > 1 (for a>=1, b>=2, c != 0, gcd(a,c) = 1, gcd(b,c) = 1)? e.g. (113*13^n-5)/12, which has no single known prime or PRP, and is the number 9555...555 with n 5's in base 13, if such prime exists, then the smallest such prime would be a minimal prime (start with b+1) in base b = 13, see this page For this family, one would sieve the sequence 113*13^n-5 for primes not dividing 12, i.e. sieve starting with the prime 5 (and ending with 10^9 or more), and initialized the list of candidates to not include n for which 2 or 3 divides (113*13^n-5)/12 Most of the unsolved families in the "minimal prime problem" require this updating, e.g. the unsolved families in base 19 and the unsolved families in base 21 Last fiddled with by sweety439 on 2022-10-28 at 03:59
 2022-10-28, 12:29 #745 rogue     "Mark" Apr 2003 Between here and the 2×3,527 Posts I see what you are saying. The line in ValidateOptions should be in the constructor. Thanks for finding it.
2022-10-28, 12:37   #746
rogue

"Mark"
Apr 2003
Between here and the

2×3,527 Posts

Quote:
 Originally Posted by sweety439 Can you update mtsieve to make it be able to sieve the sequence (a*b^n+c)/gcd(a+c,b-1) with gcd(a+c,b-1) > 1 (for a>=1, b>=2, c != 0, gcd(a,c) = 1, gcd(b,c) = 1)? e.g. (113*13^n-5)/12, which has no single known prime or PRP, and is the number 9555...555 with n 5's in base 13, if such prime exists, then the smallest such prime would be a minimal prime (start with b+1) in base b = 13, see this page For this family, one would sieve the sequence 113*13^n-5 for primes not dividing 12, i.e. sieve starting with the prime 5 (and ending with 10^9 or more), and initialized the list of candidates to not include n for which 2 or 3 divides (113*13^n-5)/12 Most of the unsolved families in the "minimal prime problem" require this updating, e.g. the unsolved families in base 19 and the unsolved families in base 21
The answer at this time is "no". I stated above the limitations I can add to srsieve2. What you are asking for doesn't meet the criteria that I listed above (d must be prime and d must divide k*b^n+c for all n). It looks like SethTho is going to get that working. More investigation needs to be done to support other conditions. For example I think that pfgw uses floor(), but it might use round() or ceil(). I have to figure that out before doing anything along the lines of what you are asking.

In the interim, if you know C++, you can possibly investigate writing your own sieve based upon the framework.

2022-10-28, 13:36   #747
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

71428 Posts

Quote:
 Originally Posted by rogue The answer at this time is "no". I stated above the limitations I can add to srsieve2. What you are asking for doesn't meet the criteria that I listed above (d must be prime and d must divide k*b^n+c for all n). It looks like SethTho is going to get that working. More investigation needs to be done to support other conditions. For example I think that pfgw uses floor(), but it might use round() or ceil(). I have to figure that out before doing anything along the lines of what you are asking. In the interim, if you know C++, you can possibly investigate writing your own sieve based upon the framework.
Then, can we use mtsieve to sieve the sequence 113*13^n-5 with the primes p>=5 (and initialized the list of candidates to not include n for which 2 or 3 divides (113*13^n-5)/12, i.e. only include the n == 2, 4 mod 6)? Or it will return error as every term is divisible by 12?

Last fiddled with by sweety439 on 2022-10-28 at 13:51

2022-10-28, 15:13   #748
rogue

"Mark"
Apr 2003
Between here and the

2×3,527 Posts

Quote:
 Originally Posted by sweety439 Then, can we use mtsieve to sieve the sequence 113*13^n-5 with the primes p>=5 (and initialized the list of candidates to not include n for which 2 or 3 divides (113*13^n-5)/12, i.e. only include the n == 2, 4 mod 6)? Or it will return error as every term is divisible by 12?
I cannot tell you. I haven't determined the behavior to use yet. That is much easier said than done. I don't know when I am going to look into it.

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

Thu Mar 23 02:15:45 UTC 2023 up 216 days, 23:44, 0 users, load averages: 1.04, 0.92, 0.84

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.

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