20061107, 10:10  #1 
Jan 2006
Hungary
2^{2}·67 Posts 
Which sieve to use for n^n1?
Hi all.
I am curious how I can test a lot of numbers with the form: n^n1 Is there a sieve that can handle this? The best I can do is Proth.exe but then I have to change the base by hand for every candidate. Can I create an input file that lets me change the base? I managed PRP tests on n*n^n1 with LLR. Is there a way that I can alter ABC $a*$b^$a$c into something that forms n^n1? I've tried ABC $a^$b$c but that fizzles. Thought anyone? Thanks a bunch, Willem. 
20061107, 10:30  #2 
Sep 2002
Database er0rr
29·151 Posts 
n^n1 == (n1)*(n^(n1)+n^(n2)+....+n^2+n^1+n^0) and this is always composite for n>2. For n=2 it is prime!
As explained in the PFGW documentation, in abcfileformats.txt, an ABC2 file would be: ABC2 $a^$a1 a: from 2 to 100 Last fiddled with by paulunderwood on 20061107 at 10:39 
20061107, 10:56  #3 
"Bob Silverman"
Nov 2003
North of Boston
1D48_{16} Posts 
It factors further via an Aurefeuillian factorization when n = 1 mod 4.

20061107, 12:00  #4 
Jan 2006
Hungary
2^{2}·67 Posts 
Aha. That explains why my home built siever was so quick all of sudden.
But I can not easily find factors for n^n+1. Do you have a neat trick for that up your sleeve too? I googled a bit for "Aurefeuillian factorization" but unfortunately that doesn't mean that I can now magically perform one. Willem (I am sieving a lot of Woodall numbers (n*2^n1) lately, that's how I came to this) 
20061107, 13:50  #5  
"Robert Gerbicz"
Oct 2005
Hungary
11001000011_{2} Posts 
Quote:


20061107, 14:50  #6  
Aug 2002
Buenos Aires, Argentina
2·733 Posts 
Quote:


20061107, 15:45  #7  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}·937 Posts 
Quote:


20061107, 21:34  #8 
Jan 2006
Hungary
2^{2}·67 Posts 
Thanks a lot for the pointers guys. As I am more interested in primes than in factors it is clear that I have to make up a different formula.
How about n^n2 or n^n+2? Willem (I know, I know, one fool can ask more than 10 wise guys can answer) 
20061107, 22:14  #9  
"Robert Gerbicz"
Oct 2005
Hungary
3103_{8} Posts 
Quote:
I've done a quick search to find the first few terms, then a search in Neil Sloane's database, supposing that it is a known sequence, and I've gotten: http://www.research.att.com/~njas/sequences/A100407 http://www.research.att.com/~njas/sequences/A100408 I think that it is very possible that these two sequences has got infinetely many terms. Are you hungarian? Willem isn't a hungarian name. I lived also in Budapest. But now I live in Halasztelek, near Budapest. 

20061107, 22:16  #10 
Sep 2002
Database er0rr
29·151 Posts 
The problem with n^n+2 is how are you going to prove numbers with greater that say 7000 digits (see the Primo record holders for "general numbers"  with parallelised FastECPP more is possible) with classical N+1 methods? Probable primes with greater than 10,000 digits are recorded here.

20061108, 09:16  #11  
Jan 2006
Hungary
100001100_{2} Posts 
Quote:
As Paul U. pointed out that +2 means that only probable primes are feasible, I'll have to get hold of Primo now. Neil Sloane's database is neat. Maybe I'll try to add some factors, just so that I can leave my mark somewhere... I guess that my bid for a top 5000 can better stay with the Woodall Primes. Thanks for the advice guys, it helped me focus a lot quicker. Laters, Willem. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
SIEVE GAP  pepi37  Other Mathematical Topics  2  20160319 06:55 
Advantage of lattice sieve over line sieve  binu  Factoring  3  20130413 16:32 
46k sieve, max. n = 5M  Cruelty  Riesel Prime Search  11  20100310 22:15 
Sieve Vs PRP  Chino112  Prime Sierpinski Project  6  20070328 19:15 
Help with PSP Sieve  cswchan  Prime Sierpinski Project  7  20070203 19:24 