mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > carpetpool

Reply
 
Thread Tools
Old 2017-11-28, 07:44   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

5×67 Posts
Default Sieve for divisibility sequences

Prior to other existing sieving programs, it would be convenient to have a sieve for divisiblity sequences S(n) (prime n only) which include, but are not restricted to (a^n-b^n)/(a-b), LucasU(a,b,n), and LucasV(a,b,n).

The idea is that there are three arguments to the sieve, S(n) the sequence (already defined), the primes n in the range [a, b], and the sieve limit l, to which S(n) is trial divided by primes of the form 2*k*n+1 (or in some sequences trial divide by primes of the form 2*k*n+-1) with k <= l.

The sieve formats should be similar to that of other programs, such as in perl ntheory, msieve, srsieve, etc:

[S(n),a,b,l,1] to sieve S(n) for prime indices n, in the range [a,b] and divide by prime numbers of the form 2*k*n+1 up to k = l.

[S(n),a,b,l,-1] to sieve S(n) for prime indices n, in the range [a,b] and divide by prime numbers of the form 2*k*n+1 or k*n-1 up to k = l.

For instance, if one chooses to test S(n) = 2^n-1 for odd prime n up to 100, with l = 10000, the input is:

[2^n-1,3,100,10000,1]

and output are the primes:

[19, 31, 61, 67, 89]

because these primes are not divisible by any prime factor of the form 2*k*n+1 with k < 10000. One can write an ABC file (if there are several primes remaining in output) or test them manually if there are not many and or they are small values:

PFGW Version 3.8.3.64BIT.20161203.Win_Dev [GWNUM 28.6]

Primality testing 2^19-1 [N-1, Brillhart-Lehmer-Selfridge]
2^19-1 is prime! (0.0667s+0.1339s)
Primality testing 2^31-1 [N-1, Brillhart-Lehmer-Selfridge]
2^31-1 is prime! (0.1568s+0.1394s)
Primality testing 2^61-1 [N-1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 3
2^61-1 is prime! (0.2173s+0.1997s)
Primality testing 2^67-1 [N-1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 3
Primality testing 2^89-1 [N-1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 3
2^89-1 is prime! (0.3988s+0.1553s)

and find that 2^n-1 is prime for n = 2, 3, 5, 7, 11, 13, 17, 19, 31, 61, 89. The first 6 terms are a trivial result of dividing 2^n-1 by all prime factors of the form 2*k*n+1, with k > l, and 2*l*n+1 > 2^n-1. The others are a result of a primality test after 'sieving'. Other large sequences should work the same way, leaving less primes indices n to test in S(n).
carpetpool is offline   Reply With Quote
Old 2022-02-08, 05:20   #2
sweety439
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

72·73 Posts
Default

Quote:
Originally Posted by carpetpool View Post
and find that 2^n-1 is prime for n = 2, 3, 5, 7, 11, 13, 17, 19, 31, 61, 89. The first 6 terms are a trivial result of dividing 2^n-1 by all prime factors of the form 2*k*n+1, with k > l, and 2*l*n+1 > 2^n-1. The others are a result of a primality test after 'sieving'. Other large sequences should work the same way, leaving less primes indices n to test in S(n).
2^11-1 = 23 * 89 is composite
sweety439 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A great universal divisibility rule JM Montolio A Miscellaneous Math 3 2018-02-27 16:11
Divisibility sequences based on recurrence relations carpetpool Combinatorics & Combinatorial Number Theory 1 2017-12-21 00:42
Sequences >1M and < 5M ugly2dog Aliquot Sequences 21 2015-09-10 07:09
Advantage of lattice sieve over line sieve binu Factoring 3 2013-04-13 16:32
Any interest in all sequences/open sequences? Greebley Aliquot Sequences 6 2012-04-07 10:06

All times are UTC. The time now is 01:35.


Fri Aug 19 01:35:48 UTC 2022 up 23:04, 0 users, load averages: 2.04, 1.73, 1.61

Powered by vBulletin® Version 3.8.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.

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