Which sieve to use for n^n-1?

Siemelink · 2006-11-07, 10:10

Hi all.

I am curious how I can test a lot of numbers with the form:
n^n-1
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^n-1 with LLR. Is there a way that I can alter ABC $a*$b^$a$c into something that forms n^n-1?
I've tried ABC $a^$b$c but that fizzles.

Thought anyone?

Thanks a bunch, Willem.

paulunderwood · 2006-11-07, 10:30

n^n-1 == (n-1)*(n^(n-1)+n^(n-2)+....+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^$a-1
a: from 2 to 100

R.D. Silverman · 2006-11-07, 10:56

Quote:

Originally Posted by paulunderwood

n^n-1 == (n-1)*(n^(n-1)+n^(n-2)+....+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^$a-1
a: from 2 to 100

It factors further via an Aurefeuillian factorization when n = 1 mod 4.

Siemelink · 2006-11-07, 12:00

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^n-1) lately, that's how I came to this)

R. Gerbicz · 2006-11-07, 13:50

Quote:

Originally Posted by Siemelink

But I can not easily find factors for n^n+1. Do you have a neat trick for that up your sleeve too?

If n isn't a power of two, then it has got an odd prime factor, say p, then n^n+1 is divisible by n^(n/p)+1 so it is composite! We can suppose that n=2^k, from this n^n+1=2^(k*2^k)+1 but if k isn't 0 or a power of two, then it has got an odd prime factor, say q but then 2^(k*2^k)+1 is divisible by 2^(k*2^k/q)+1 so it isn't a prime. We arrived: k=2^s or k=0, if k=0 then n=2^0=1 and n^n+1=2 is prime. So n=1 is a solution, in other cases: k=2^s so n^n+1=2^(2^(s+2^s))+1=F(s+2^s) Fermat number. About the search for factors of these Fermat numbers see: http://www.primepuzzles.net/conjectures/conj_016.htm

alpertron · 2006-11-07, 14:50

Quote:

Originally Posted by Siemelink

I googled a bit for "Aurefeuillian factorization" but unfortunately that doesn't mean that I can now magically perform one.

My ECM factorization applet can perform Aurifeuillian factorizations, so you can start from there.

R.D. Silverman · 2006-11-07, 15:45

Quote:

Originally Posted by Siemelink

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^n-1) lately, that's how I came to this)

n^n + 1 has an Aurefeullian factorization as well.

Siemelink · 2006-11-07, 21:34

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^n-2 or n^n+2?

Willem
(I know, I know, one fool can ask more than 10 wise guys can answer)

R. Gerbicz · 2006-11-07, 22:14

Quote:

Originally Posted by Siemelink

How about n^n-2 or n^n+2?

Willem
(I know, I know, one fool can ask more than 10 wise guys can answer)

Hi Willem!

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.

paulunderwood · 2006-11-07, 22:16

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.

Siemelink · 2006-11-08, 09:16

Quote:

Originally Posted by R. Gerbicz

Hi Willem!

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.

I am dutch, my wife lured me here. I can mumble in Hungarian, but the kids are now big enough to translate for me.
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.

2006-11-07, 10:10	#1
Siemelink Jan 2006 Hungary 2²·67 Posts	Which sieve to use for n^n-1? Hi all. I am curious how I can test a lot of numbers with the form: n^n-1 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 *nn^n-1** with LLR. Is there a way that I can alter ABC $a*$b^$a$c into something that forms n^n-1? I've tried ABC $a^$b$c but that fizzles. Thought anyone? Thanks a bunch, Willem.

2006-11-07, 10:30	#2
paulunderwood Sep 2002 Database er0rr 2×7⁴ Posts	n^n-1 == (n-1)(n^(n-1)+n^(n-2)+....+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^$a-1 a: from 2 to 100 Last fiddled with by paulunderwood on 2006-11-07 at 10:39*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
SIEVE GAP	pepi37	Other Mathematical Topics	2	2016-03-19 06:55
Advantage of lattice sieve over line sieve	binu	Factoring	3	2013-04-13 16:32
46k sieve, max. n = 5M	Cruelty	Riesel Prime Search	11	2010-03-10 22:15
Sieve Vs PRP	Chino112	Prime Sierpinski Project	6	2007-03-28 19:15
Help with PSP Sieve	cswchan	Prime Sierpinski Project	7	2007-02-03 19:24

2006-11-07, 12:00	#4
Siemelink Jan 2006 Hungary 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^n-1) lately, that's how I came to this)

2006-11-07, 21:34	#8
Siemelink Jan 2006 Hungary 268₁₀ 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^n-2 or n^n+2? Willem (I know, I know, one fool can ask more than 10 wise guys can answer)

2006-11-07, 22:16	#10
paulunderwood Sep 2002 Database er0rr 1001011000010₂ 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.