# Unlawful primes

GROUPS:
 Todd Rowland 7 Votes 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 == 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000010001is the largest one I found.  Also I don't notice any patterns, e.g. here in the first 200 such primesand here are the first 254 primes with nonzero digits {1,2,1}the largest found is1+2*10^14+10^201 == 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000200000000000001Does anyone else have any primes which don't seem like they should be prime?  The more extreme the better.
2 years ago
12 Replies
 Vitaliy Kaurov 6 Votes 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 // GridSo this is only a few primes. What code did you ran to get 200?
2 years ago
 Simon Schmidt 5 Votes From tutorial/SomeNotesOnInternalImplementation#6849PrimeQ 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:<< PrimalityProvingProvablePrimeQ[1 + 2*10^14 + 10^201]ProvablePrimeQ[1 + 10^4 + 10^18 + 10^201](* Both are True *)
2 years ago
 Ilian Gachevski 5 Votes 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.
2 years ago
 Chip Hurst 7 Votes 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}]
2 years ago
 Todd Rowland 4 Votes Vitaliy,You don't need any complicated code to explore this.  I just used 1+10^a+10^b+10^c where a 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.
2 years ago
 Carlo Barbieri 4 Votes Some primes are actually illegal: https://en.wikipedia.org/wiki/Illegal_prime
2 years ago
 Bernat Espigulé Pons 3 Votes A really interesting discussion, Todd When falling in love with a prime, be careful. There are unlawful primes, illegal primes .... and MONSTER prime numbers.
2 years ago
 Mats Granvik 1 Vote 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]}
 Ed Pegg 1 Vote One way to get big numbers quickly is to use exponent towers. These are prime: PrimeQ[3^7^3+4^6^4] PrimeQ[7^6^3+6^5^5] PrimeQ[3^7^2+8^5^5] `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.