Is there a primality test for Repunits? I am too lazy to read...

[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

[ProximaCentauri]

Hi Supermod,

Do u find it fair to edit the title after posted?

Who do you think you are?

[Brian-E]

If you google "repunit prime" you see the answer to your question and lots of other information.

[davar55]

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.

[ProximaCentauri]

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.

[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.

[ProximaCentauri]

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!

[TheMawn]

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 * (10ⁿ - 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.

[Mini-Geek]

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.

[ProximaCentauri]

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 * (10ⁿ - 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

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)³.

Thx mawn for your credit, even unwarranted