mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2009-05-21, 03:39   #12
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Suva, Fiji

23·3·5·17 Posts
Default

Some basic stats for lower b

Code:
b   # of prp-3 in series a from 1 to 10000 

1  1645
2  1699
3   612
4   601
5   273
6   143
7    70
8    68
b=1, 3 and 7 demonstrating the prime [2^(b+1)]+1 = 5,17,257 effect

Last fiddled with by robert44444uk on 2009-05-21 at 03:41
robert44444uk is offline   Reply With Quote
Old 2009-05-21, 10:59   #13
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Suva, Fiji

23·3·5·17 Posts
Default

Quote:
Originally Posted by robert44444uk View Post
This looks the key. Shame I did not spot this by observation. So the sieve only has to calculate all the primes in x*2^(b+1)+1, x integer and increasing.
I can't make rhyme or reason regarding the incidence of prime factors in a^(2^b)+(a+1)(2^b). For b =12, i.e 2^b=4096 small prime factors appear as follows. Maybe someone can enlighten on the modular positions and frequency. I know that, if a prime factor p appears in a=A, then it will appear also for for the a values which are Amod[p]. Looking at a modulo order 4096 does not appear to enlighten. Maybe it has to do with primitive roots.

Code:
a     factors

1	114689	
2	286721	1810433
5	270337	737281
6	147457	
7	114689	147457
10	114689	
12	163841	
16	147457	1417217
19	4300801	
28	5308417	
31	114689	
32	5824513	
33	1769473	
36	40961	65537
37	11370497	
40	65537	5726209
42	286721		
44	557057		
45	40961	1097729	
47	40961	147457	
48	3489793		
49	65537		
51	4759553		
52	19701761		
53	286721	14770177	
54	163841		
55	40961		
56	65537		
57	65537		
58	1417217		
60	15900673		
62	2482177	7413761	13664257
63	13066241		
70	163841		
71	114689	5849089	20586497
73	147457	417793	925697
76	65537		
77	188417		
78	114689		
79	40961		
84	286721		
85	188417		
87	147457		
92	286721	9379841	
95	40961	65537	1589249
96	40961

Last fiddled with by robert44444uk on 2009-05-21 at 11:13
robert44444uk is offline   Reply With Quote
Old 2009-05-21, 12:24   #14
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·7·461 Posts
Default

Well, you're talking about the roots of a degree-4096 polynomial modulo the prime, so you'd expect 114689 to appear 4096 times for every 114689 exponents, repeating with period 114689. I don't see any reason for the polynomial to have particularly tractable roots, though obviously if X is a root then p-(X+1) is.
fivemack is offline   Reply With Quote
Old 2009-05-22, 14:00   #15
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Suva, Fiji

23·3·5·17 Posts
Default

This appears to have been studied as a form for small a by Henri Lifchitz - he has some prp listed in his site. There is also at least one prp with exponent 16384 and a few of 8192 and 4096

Last fiddled with by robert44444uk on 2009-05-22 at 14:06
robert44444uk is offline   Reply With Quote
Old 2009-05-25, 04:03   #16
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

115710 Posts
Default

Here is a sieving algorithm I think will work, but I can't find any way to exploit the fact that b=a+1 in a^2^m + b^2^m. Does anyone know a better algorithm?

(By "maximal prime power factor" I mean a factor p^m, m>0, where p is prime but p^{m+1} is not a factor. A list L of length N has elements L[1], L[2], ..., L[N].)

Algorithm to sieve candidates a^2^m + b^2^m for factors k*2^n+1, with m<n fixed, and odd k in k0 <= k < k1:
Code:
Input A,B  /* lists of remaining candidates A[i]^2^m + B[i]^2^m */
Input m, n, k0, k1

Let C be a list of unique elements in the union of A and B
  /* so the length of C could be anywhere from |A|+1 to 2*|A| */

Let S,T be lists (of the same length as A) such that:
  S[i] is the index of A[i] in C (so that A[i] = C[S[i]])
  T[i] is the index of B[i] in C (so that B[i] = C[T[i]])

Let U be the list of unique maximal prime power factors of elements in C
Let V be a list of the same length as U

Let F be a list (of the same length as C) such that:
  F[i] is the list of j such that U[j] is a maximal prime power factor of C[i]
  /* so that F[i][0]*F[i][1]*... = C[i] */
Let G be a list of the same length as F


For each odd k in k0 <= k < k1 such that k*2^n+1 is a probable prime
{
  /* V <-- U^2^m mod k*2^n+1 */
  For j from 1 to |U|
  {
    V[j] <-- U[j]
    Repeat m-1 times
      V[j] <-- V[j]^2 mod k*2^n+1
  }

  /* G <-- C^2^m mod k*2^n+1 */
  For i from 1 to |F|
  {
    G[i] <-- V[F[i][1]]
    For j from 2 to |F[i]|
      G[i] <-- G[i]*V[F[i][j]] mod k*2^n+1
  }

  For i from 1 to |A|
    If G[S[i]] + G[T[i]] = 0 (mod k*2^n+1)
      Report that k*2^n+1 divides A[i]^2^m + B[i]^2^m
}
geoff is offline   Reply With Quote
Old 2009-05-31, 13:24   #17
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Suva, Fiji

23×3×5×17 Posts
Default

Thank you Geoff for your contribution. I have come to an early conclusion that these series are not terribly prime, despite having so few possible prime factors p, as those prime factors crop up with a much higher frequency than 1/p. Given the difficulties of finding a nice quick algorithm to determine amod(p)=0 for a given p, then the sieve approach Geoff suggested may be too slow to be of use.

Do others agree?
robert44444uk is offline   Reply With Quote
Old 2009-06-03, 01:18   #18
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default

Robert, I have uploaded a sieve here. See the README for instructions.
geoff is offline   Reply With Quote
Old 2009-06-03, 12:04   #19
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

22·1,877 Posts
Default

Quote:
Originally Posted by robert44444uk View Post
Thank you Geoff for your contribution. I have come to an early conclusion that these series are not terribly prime,
I told you that some time ago. Such primes will be rare.

A more interesting question is whether there exists values of a for
which there are no primes. If so, what is the density of that set?
R.D. Silverman is offline   Reply With Quote
Old 2009-06-05, 15:29   #20
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Suva, Fiji

23×3×5×17 Posts
Default

Quote:
Originally Posted by geoff View Post
Robert, I have uploaded a sieve here. See the README for instructions.
Thank you Geoff. Been travelling with no internet connection. Just catching up. Will let you know how I get on.
robert44444uk is offline   Reply With Quote
Old 2009-06-05, 17:26   #21
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

37·163 Posts
Default

i accidentally left b=12 running quite a lot longer than i meant to and found:
311^(2^12)+312^(2^12)
2741^(2^12)+2742^(2^12)
3582^(2^12)+3583^(2^12)
5293^(2^12)+5294^(2^12)
are all 3-prp
i expect they are already known
henryzz is offline   Reply With Quote
Old 2009-06-06, 05:55   #22
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Suva, Fiji

23×3×5×17 Posts
Default

Quote:
Originally Posted by henryzz View Post
i accidentally left b=12 running quite a lot longer than i meant to and found:
311^(2^12)+312^(2^12)
2741^(2^12)+2742^(2^12)
3582^(2^12)+3583^(2^12)
5293^(2^12)+5294^(2^12)
are all 3-prp
i expect they are already known
These are the listed prp on the Lifchitz site, all found by H Lifchitz

Code:
Form  digits  date 
2741^4096+2742^4096	14083	10/2002
311^4096+312^4096	10217	10/2002
3508^8192+3509^8192	29043	11/2002
5183^16384+5182^16384	60860	Jan-07
1829^16384+1828^16384	53449	Jan-07
14082^4096+14083^4096	16994	01/2007
12080^4096+12081^4096	16721	01/2007
6289^4096+6290^4096	15560	01/2007
5293^4096+5294^4096	15253	01/2007
3582^4096+3583^4096	14559	01/2007
robert44444uk is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
More NFS@Home 16e Lattice Sieve V5 wu's needed pinhodecarlos NFS@Home 46 2018-03-12 22:43
Advantage of lattice sieve over line sieve binu Factoring 3 2013-04-13 16:32
Sieve needed for k*b1^m*b2^n+1 beyastard Software 55 2009-07-29 12:51
Help needed AntonVrba Math 3 2007-03-06 10:55
Volunteer needed for sieve merging MooooMoo Twin Prime Search 9 2007-01-01 21:13

All times are UTC. The time now is 13:42.


Mon Jan 30 13:42:47 UTC 2023 up 165 days, 11:11, 0 users, load averages: 2.35, 1.93, 1.81

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

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