mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2014-12-05, 09:17   #1
ProximaCentauri
 
ProximaCentauri's Avatar
 
"M49"
Dec 2014
Austria

23·3 Posts
Default 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
ProximaCentauri is offline   Reply With Quote
Old 2014-12-05, 09:39   #2
ProximaCentauri
 
ProximaCentauri's Avatar
 
"M49"
Dec 2014
Austria

1816 Posts
Default

Hi Supermod,

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

Who do you think you are?
ProximaCentauri is offline   Reply With Quote
Old 2014-12-05, 10:02   #3
Brian-E
 
Brian-E's Avatar
 
"Brian"
Jul 2007
The Netherlands

7·467 Posts
Default

If you google "repunit prime" you see the answer to your question and lots of other information.
Brian-E is offline   Reply With Quote
Old 2014-12-05, 11:23   #4
davar55
 
davar55's Avatar
 
May 2004
New York City

23×232 Posts
Default

Quote:
Originally Posted by ProximaCentauri View Post
..... 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.
davar55 is offline   Reply With Quote
Old 2014-12-05, 13:06   #5
ProximaCentauri
 
ProximaCentauri's Avatar
 
"M49"
Dec 2014
Austria

23×3 Posts
Default

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
ProximaCentauri is offline   Reply With Quote
Old 2014-12-05, 15:54   #6
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

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.
Mini-Geek is offline   Reply With Quote
Old 2014-12-05, 16:43   #7
ProximaCentauri
 
ProximaCentauri's Avatar
 
"M49"
Dec 2014
Austria

23×3 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
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!
ProximaCentauri is offline   Reply With Quote
Old 2014-12-05, 18:02   #8
TheMawn
 
TheMawn's Avatar
 
May 2013
East. Always East.

172710 Posts
Default

Quote:
Originally Posted by ProximaCentauri View Post
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
TheMawn is offline   Reply With Quote
Old 2014-12-05, 18:23   #9
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
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.
Mini-Geek is offline   Reply With Quote
Old 2014-12-05, 19:06   #10
ProximaCentauri
 
ProximaCentauri's Avatar
 
"M49"
Dec 2014
Austria

23×3 Posts
Default

Quote:
Originally Posted by TheMawn View Post
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
ProximaCentauri is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
there is another way to test the primality of a no shawn Miscellaneous Math 5 2007-07-17 17:55
AKS Primality Test Guilherme Math 2 2004-11-26 05:29
A primality test for Fermat numbers faster than Pépin's test ? T.Rex Math 0 2004-10-26 21:37
chance of finding a factor?......Read me read me read me :) Firedog18 Software 9 2003-07-25 17:10

All times are UTC. The time now is 10:55.

Sun Apr 11 10:55:51 UTC 2021 up 3 days, 5:36, 1 user, load averages: 1.16, 1.47, 1.71

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.