mersenneforum.org Is there a primality test for Repunits? I am too lazy to read...
 Register FAQ Search Today's Posts Mark Forums Read

 2014-12-05, 09:17 #1 ProximaCentauri     "M49" Dec 2014 Austria 23·3 Posts Is there a primality test for Repunits? I am too lazy to read... ..... and if u really wanna help me, please provide more info than "Read Knuth´s book" a la RDS ... To be more specific, we are dealing with numbers of the form (10^n-1)/9 thanks Last fiddled with by ProximaCentauri on 2014-12-05 at 09:22
 2014-12-05, 09:39 #2 ProximaCentauri     "M49" Dec 2014 Austria 23·3 Posts Hi Supermod, Do u find it fair to edit the title after posted? Who do you think you are?
 2014-12-05, 10:02 #3 Brian-E     "Brian" Jul 2007 The Netherlands 7·467 Posts If you google "repunit prime" you see the answer to your question and lots of other information.
2014-12-05, 11:23   #4
davar55

May 2004
New York City

23·232 Posts

Quote:
 Originally Posted by ProximaCentauri ..... and if u really wanna help me, please provide more info than "Read Knuth´s book" a la RDS ... To be more specific, we are dealing with numbers of the form (10^n-1)/9 thanks
Well, I'm no expert like RDS, but yes, one is: if the repunit contains an even number of digits, it is composite.

There are others. At least one other.

BTW 1 is not prime, and 2 is prime, so my rule has the exception: 11 is prime.

 2014-12-05, 13:06 #5 ProximaCentauri     "M49" Dec 2014 Austria 23·3 Posts ya thanks I am fully aware of this, but still searching for a primality test available, maybe LL-like with Lucas sequences. Is there a program which can perform such a primality test on RepUnits? I still did not find. Last fiddled with by ProximaCentauri on 2014-12-05 at 13:26
 2014-12-05, 15:54 #6 Mini-Geek Account Deleted     "Tim Sorbera" Aug 2006 San Antonio, TX USA 426710 Posts There's nothing so simple as the LL test. If there were, we would not find repunit primes on the PRP Top list. Some generalized repunit primes are proven via N-1 factoring. This is because N-1's factorization is related to the factors of some numbers of the form 10^n+1. For example, where R(n) = (10^n-1)/9 R(270343) is PRP. 270342 = 2 * 3^2 * 23 * 653 R(270343)-1 is divisible by 10^653+1 R(270343)-1 is divisible by 10^(3*653)+1 etc. So if n is smooth, it will be easier to find some factors of N-1. If you can factor 33.33% of N-1, you can run an N-1 primality test.
2014-12-05, 16:43   #7
ProximaCentauri

"M49"
Dec 2014
Austria

23·3 Posts

Quote:
 Originally Posted by Mini-Geek There's nothing so simple as the LL test. If there were, we would not find repunit primes on the PRP Top list. Some generalized repunit primes are proven via N-1 factoring. This is because N-1's factorization is related to the factors of some numbers of the form 10^n+1. For example, where R(n) = (10^n-1)/9 R(270343) is PRP. 270342 = 2 * 3^2 * 23 * 653 R(270343)-1 is divisible by 10^653+1 R(270343)-1 is divisible by 10^(3*653)+1 etc. So if n is smooth, it will be easier to find some factors of N-1. If you can factor 33.33% of N-1, you can run an N-1 primality test.
Thanks, MiniGeek!

2014-12-05, 18:02   #8
TheMawn

May 2013
East. Always East.

11·157 Posts

Quote:
 Originally Posted by ProximaCentauri Hi Supermod, Do u find it fair to edit the title after posted? Who do you think you are?
They do that from time to time. Most often it is done on threads that make themselves very big targets for stuff like that. Some times it's a thread title that can be slightly altered into something completely different (there was an "Artistic Insults" contest that became an "Autistic Insults" contest, as an example).

In this case you've made yourself a big target by being extra specific about not being told to go read a book. If you'd simply asked "Does anyone know if there is a primality test for numbers of the form 1/9 * (10n - 1)?" you may not have been trolled quite as hard.

Now I am giving you some as-of-yet unwarranted credit by assuming you DID do some searching around first. It takes less time and fewer keyboard presses to just Google Repunit Primality Test and look at what comes up. To your credit, such a Test does not appear so your question is valid in that sense as a "Does Anyone Happen to Know of One?" blurb.

Last fiddled with by TheMawn on 2014-12-05 at 18:03

2014-12-05, 18:23   #9
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts

Quote:
 Originally Posted by Mini-Geek So if n is smooth...
Correction: If n-1 is smooth...
n itself must be prime, for the same reason that Mersenne primes have exponent p.

2014-12-05, 19:06   #10
ProximaCentauri

"M49"
Dec 2014
Austria

308 Posts

Quote:
 Originally Posted by TheMawn They do that from time to time. Most often it is done on threads that make themselves very big targets for stuff like that. Some times it's a thread title that can be slightly altered into something completely different (there was an "Artistic Insults" contest that became an "Autistic Insults" contest, as an example). In this case you've made yourself a big target by being extra specific about not being told to go read a book. If you'd simply asked "Does anyone know if there is a primality test for numbers of the form 1/9 * (10n - 1)?" you may not have been trolled quite as hard. Now I am giving you some as-of-yet unwarranted credit by assuming you DID do some searching around first. It takes less time and fewer keyboard presses to just Google Repunit Primality Test and look at what comes up. To your credit, such a Test does not appear so your question is valid in that sense as a "Does Anyone Happen to Know of One?" blurb.

Yeah I did research before, such as

Code:
Irish Math. Soc. Bulletin 59 (2007), 29–35 29
Factoring Generalized Repunits
JOHN H. JAROMA
and some others, but i was unlucky to find anything of a primality test for these kind of numbers.

They seem to be very rare in base 10, maybe even less dense than the Mersenne Primes.

However, Lucas sequences are involved similar like in LLR-tests.

Harvey Dubner stated that R49081 is a PRP in March 2001 and he also said the only chance of proving it prime with current theory and technology is using the BLS method. This requires that (R49081 − 1) be about 1/3 factored, that is, the product of the known prime factors of (R49081 − 1) should be about (R49081 − 1)3.

Thx mawn for your credit, even unwarranted

 Similar Threads Thread Thread Starter Forum Replies Last Post Trilo Miscellaneous Math 25 2018-03-11 23:20 shawn Miscellaneous Math 5 2007-07-17 17:55 Guilherme Math 2 2004-11-26 05:29 T.Rex Math 0 2004-10-26 21:37 Firedog18 Software 9 2003-07-25 17:10

All times are UTC. The time now is 23:16.

Wed Apr 14 23:16:53 UTC 2021 up 6 days, 17:57, 0 users, load averages: 2.17, 2.06, 2.12