Message Boards Message Boards

Unlawful primes

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
5 years 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
5 years 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
5 years 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
5 years 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];
    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]
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 *)
N[Total[IntegerDigits[#]]/IntegerLength[#]] & /@ NestList[sparsePrimeWithSeed, 1 + 10^4 + 10^18 + 10^201, 6],
PlotRange -> {0, .05}]
POSTED BY: Chip Hurst
5 years ago

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
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
5 years ago
Some primes are actually illegal:
POSTED BY: Carlo Barbieri
5 years 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.

5 years 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
5 years ago
POSTED BY: Udo Krause
2 years ago

It would be amazing if one could actually make this analogy computable, and then even more amazing to find a simple description of a large prime by starting out with a simple knot.

This type of mathematics is perhaps more art than science, leaving behind simple rules and necessary conclusions for the sake of an adventure. But maybe someone can do the calculations (say, using KnotData and Wolfram Language)?

POSTED BY: Todd Rowland
2 years ago

This introduces Mazur’s knotty dictionary .

POSTED BY: Udo Krause
2 years ago

One way to get big numbers quickly is to use exponent towers. These are prime:


To get a lot of large primes with small representations, visit the Probable Prime Records page. Virtually all known primes and probable primes with more than 100000 digits have a short, elegant representation. Why? Because it takes awhile to do the primality tests, and no-one is looking at big random primes.

Among actual primes, there are Primorial primes 1098133#-1 (476311 digits), Factorial primes 150209!+1 (712355 digits), Cullen primes 6679881 · 2^6679881 + 1 (2010852 digits), Proth primes 19249 · 2^13018586 + 1 (3918990 digits).

The probable primes are much more varied. Elliptic curves can be used to prove primality, but that only works up to about 22000 digits at the moment.

The Cunningham project factors numbers of the type a^b+1 and a^b-1. I recently put up a Demonstration that factors up to 2^1200 + 1 and 2^1200 - 1, for those where solutions are known.

2 years ago

Group Abstract Group Abstract