Group Abstract Group Abstract

Message Boards Message Boards

Unlawful primes

GROUPS:
How small can a description of a large prime number be? There are the Fermat primes 2^n-1 for certain n, and in base 2 these are a sequence of ones.  In base 10, if you have just zeros and two ones, then the only primes of that form are 11 and 101.  If there are three ones then it is divisible by three.  But what about four ones?  It seems wrong to me that there might be an unbounded number of such primes.

That's what some brief experiments suggest though.
1+10^4+10^18+10^201 == 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000010001
is the largest one I found.  Also I don't notice any patterns, e.g. here in the first 200 such primes



and here are the first 254 primes with nonzero digits {1,2,1}



the largest found is
1+2*10^14+10^201 == 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000200000000000001
Does anyone else have any primes which don't seem like they should be prime?  The more extreme the better.
POSTED BY: Todd Rowland
Answer
8 months ago
Very interesting, Todd, I am curious what code did you use to get those images. I tried this for {0,1} and 5 ones to form primes and its running out of computational resources pretty quickly:
data = Select[
           ParallelTable[{n, IntegerDigits[Prime[n], 10, 10]}, {n, 10^7}],
                         Union[#[[2]]] == {0, 1} && Total[#[[2]]] == 5 &];

{#1, Spacer[10], ArrayPlot[{#2}, Mesh -> True]} & @@@ data // Grid



So this is only a few primes. What code did you ran to get 200?
POSTED BY: Vitaliy Kaurov
Answer
8 months ago
From tutorial/SomeNotesOnInternalImplementation#6849
  • PrimeQ first tests for divisibility using small primes, then uses the Miller\Rabin strong pseudoprime test base 2 and base 3, and then uses a Lucas test.
  • As of 1997, this procedure is known to be correct only for n<10^16, and it is conceivable that for larger n it could claim a composite number to be prime.

Anyway, the PrimalityProving package agrees they are primes:
<< PrimalityProving`
ProvablePrimeQ[1 + 2*10^14 + 10^201]
ProvablePrimeQ[1 + 10^4 + 10^18 + 10^201]
(* Both are True *)
POSTED BY: Simon Schmidt
Answer
8 months ago
This is a somewhat extreme example of a naughty (as in having a lot of naughts) prime (source).
3*10^665829 + 1
As of now, there are 21 known primes of this form (3.10^n + 1).

By the way, the test used by PrimeQ is currently known to be correct up to 2^64. Also, no pseudoprime (a composite number passing the test) of any size has ever been found.
POSTED BY: Ilian Gachevski
Answer
8 months ago
I'm going to call a prime that only consists of moslty 0's and few 1's a sparse prime. Here's some code to find even larger sparse primes. It runs surprisingly quickly.
 (*Searches for a prime that matches the first digits of n and remaining digits 0 or 1.*)
 sparsePrimeWithSeed[n_Integer] :=
  Block[{k = 1, p, remainder},
   p = NextPrime[10 n];
   Monitor[
    While[Quotient[p, 10^k] != n || !MatchQ[IntegerDigits[Mod[p, 10^(k + 1)]], {(0 | 1) ..}],
     remainder = Mod[p, 10^(k + 1)];
     p = NextPrime[10^(++k)*n]
    ],
   remainder];
  p
]
We can now look for primes whose first digits match Todd's prime and remaining digits are all 0 or 1.
In[2]:= sparsePrimeWithSeed[1 + 10^4 + 10^18 + 10^201]

Out[2]= 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000010001000000000001
Or we can nest this function to get even larger sparse primes.
In[3]:= Nest[sparsePrimeWithSeed, 1 + 10^4 + 10^18 + 10^201, 5]

Out[3]= 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000010001000000000001000000000011100000000000000110100000000000000010100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111
It turns out all primes seeded by Todd's prime aren't as sparse as the original. Here's a plot of the sparsity of succesive primes generated with the above code.
(* sparsity is number of 1's divided by integer length *)
ListLinePlot[
N[Total[IntegerDigits[#]]/IntegerLength[#]] & /@ NestList[sparsePrimeWithSeed, 1 + 10^4 + 10^18 + 10^201, 6],
PlotRange -> {0, .05}]
POSTED BY: Chip Hurst
Answer
8 months ago
Vitaliy,

You don't need any complicated code to explore this.  I just used 1+10^a+10^b+10^c where a<b<c so just using ordered triples of numbers.  I wish I could say I wrote something as clear as
candidates =Flatten[Table[1 + 10^a + 10^b + 10^c, {c, 1, 100}, {b, 1, c - 1}, {a, 1, b - 1}]];
Select[candidates, PrimeQ]
but I actually wrote
Flatten[Table[Select[FromDigits[Join[{1},
ReplacePart[
ConstantArray[0, n], (Alternatives @@ #) -> 1], {1}]] & /@
Subsets[Range[n], {2}], PrimeQ], {n, 2, 200}]]
To find something simple and cool, you can try all sorts of things like other bases for the exponents, other sums of digits, other things besides exponent.
POSTED BY: Todd Rowland
Answer
8 months ago
Some primes are actually illegal: 

https://en.wikipedia.org/wiki/Illegal_prime
POSTED BY: Carlo Barbieri
Answer
8 months ago
A really interesting discussion, Todd emoticon

When falling in love with a prime, be careful. There are unlawful primes, illegal primes .... and MONSTER prime numbers.

Answer
7 months ago
In[1]:= Table[
Limit[Zeta[s] Total[1/Divisors[n]^(s - 1)*MoebiusMu[Divisors[n]]],
  s -> 1], {n, 1, 32}]

Out[1]= {\[Infinity], Log[2], Log[3], Log[2], Log[5], 0, Log[7],
Log[2], Log[3], 0, Log[11], 0, Log[13], 0, 0, Log[2], Log[17], 0,
Log[19], 0, 0, 0, Log[23], 0, Log[5], 0, Log[3], 0, Log[29], 0,
Log[31], Log[2]}
POSTED BY: Mats Granvik
Answer
7 months ago