mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2006-11-07, 10:10   #1
Siemelink
 
Siemelink's Avatar
 
Jan 2006
Hungary

22·67 Posts
Default 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 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.
Siemelink is offline   Reply With Quote
Old 2006-11-07, 10:30   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

24×229 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2006-11-07, 10:56   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2006-11-07, 12:00   #4
Siemelink
 
Siemelink's Avatar
 
Jan 2006
Hungary

1000011002 Posts
Default

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)
Siemelink is offline   Reply With Quote
Old 2006-11-07, 13:50   #5
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

101101110102 Posts
Default

Quote:
Originally Posted by Siemelink View Post
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
R. Gerbicz is offline   Reply With Quote
Old 2006-11-07, 14:50   #6
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

135510 Posts
Default

Quote:
Originally Posted by Siemelink View Post
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.
alpertron is offline   Reply With Quote
Old 2006-11-07, 15:45   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by Siemelink View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2006-11-07, 21:34   #8
Siemelink
 
Siemelink's Avatar
 
Jan 2006
Hungary

22·67 Posts
Default

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)
Siemelink is offline   Reply With Quote
Old 2006-11-07, 22:14   #9
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×733 Posts
Default

Quote:
Originally Posted by Siemelink View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2006-11-07, 22:16   #10
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

24×229 Posts
Default

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.
paulunderwood is offline   Reply With Quote
Old 2006-11-08, 09:16   #11
Siemelink
 
Siemelink's Avatar
 
Jan 2006
Hungary

22×67 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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.
Siemelink is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 17:07.

Sat May 8 17:07:56 UTC 2021 up 30 days, 11:48, 0 users, load averages: 3.50, 3.26, 2.96

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.