mersenneforum.org Which sieve to use for n^n-1?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2006-11-07, 10:10 #1 Siemelink     Jan 2006 Hungary 22·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 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.  2006-11-07, 10:30 #2 paulunderwood Sep 2002 Database er0rr 24×229 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 2006-11-07, 10:56 #3 R.D. Silverman Nov 2003 22×5×373 Posts 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.

 2006-11-07, 12:00 #4 Siemelink     Jan 2006 Hungary 1000011002 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, 13:50   #5
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

101101110102 Posts

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

2006-11-07, 14:50   #6
alpertron

Aug 2002
Buenos Aires, Argentina

135510 Posts

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.

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

Nov 2003

22×5×373 Posts

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.

 2006-11-07, 21:34 #8 Siemelink     Jan 2006 Hungary 22·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^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:14   #9
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2×733 Posts

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.

 2006-11-07, 22:16 #10 paulunderwood     Sep 2002 Database er0rr 24×229 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.
2006-11-08, 09:16   #11
Siemelink

Jan 2006
Hungary

22×67 Posts

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.

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post pepi37 Other Mathematical Topics 2 2016-03-19 06:55 binu Factoring 3 2013-04-13 16:32 Cruelty Riesel Prime Search 11 2010-03-10 22:15 Chino112 Prime Sierpinski Project 6 2007-03-28 19:15 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.