Paterson primes

[henryzz]

I have just watched Numberphile's video on a class of primes that a school friend of 3Blue1Brown came up with.

https://www.youtube.com/watch?v=jhObLT1Lrfo

This friend noticed that if you take a prime, convert it to base 4 and then interpret it in base 10 then it would be prime. Given his lack of a computer he was unable to find a counter example; however, as you search higher there are many (strong law of small numbers).

This algorithm relies on the fact that this base conversion from prime numbers excludes the factors 2, 3 and 5 from the resulting numbers.

Below are a few questions that came up in the comments:

• Are there infinitely many "Paterson primes"?
• How exactly does the ratio between "Paterson primes" and "non-Paterson primes" behave for larger and larger numbers?
• Is there a longest consecutive run of "Paterson primes"? So, could it theoretically be all "Paterson primes" after a certain number? If so, from what number on is that? If not (which is probably more likely), what's the longest consecutive run of "Paterson primes" we know of?
• Are there a better selection of bases other than interpretting a base 4 prime as base 10 that exclude more factors and result in a higher number of primes? (24 to 5634 is good according to comments)

[science_man_88]

Well 4 and 10's remainder on division by 6 is the same so really comes down to primes that have only 1,2,3,0 in the digits of course.

[Dr Sardonicus]

I noticed a run of 9 "non-Paterson" primes less than 1000:

853 31111 [53, 1; 587, 1]
857 31121 prime
859 31123 prime
863 31133 [163, 1; 191, 1]
877 31231 prime
881 31301 [113, 1; 277, 1]
883 31303 [23, 1; 1361, 1]
887 31313 [173, 1; 181, 1]
907 32023 [31, 1; 1033, 1]
911 32033 [103, 1; 311, 1]
919 32113 [17, 1; 1889, 1]
929 32201 [13, 1; 2477, 1]
937 32221 [7, 1; 4603, 1]
941 32231 [167, 1; 193, 1]
947 32303 prime
953 32321 prime
967 33013 prime
971 33023 prime
977 33101 [79, 1; 419, 1]
983 33113 prime
991 33133 [17, 1; 1949, 1]
997 33211 prime

It would appear they thin out as the numbers get bigger. Here are the proportions of "Paterson primes" among primes up to 10^k, k = 2 to 8.

100 0.80000000000000000000000000000000000000
1000 0.55952380952380952380952380952380952381
10000 0.37347436940602115541090317331163547600
100000 0.25823603002502085070892410341951626355
1000000 0.20712629621136844250808937807332670896
10000000 0.17486107746407876264522351744487863745
100000000 0.14798813841295297802378045129225169684

[science_man_88]

forvec(x=[[0,3],[0,3],[0,3],[0,3],[0,3],[0,3],[0,3],[0,3]],if(isprime(fromdigits(x,4)),print(fromdigits(x,4))))

[R. Gerbicz]

Originally Posted by Dr Sardonicus

It would appear they thin out as the numbers get bigger. Here are the proportions of "Paterson primes" among primes up to 10^k, k = 2 to 8.

100 0.80000000000000000000000000000000000000
1000 0.55952380952380952380952380952380952381
10000 0.37347436940602115541090317331163547600
100000 0.25823603002502085070892410341951626355
1000000 0.20712629621136844250808937807332670896
10000000 0.17486107746407876264522351744487863745
100000000 0.14798813841295297802378045129225169684

The ratio should be close to const/k.

[kriesel]

From the limited data it appears the asymptotic const ~ 1.

[Dr Sardonicus]

Originally Posted by R. Gerbicz

The ratio should be close to const/k.

Basically an extra factor of log(x) in the denominator of the asymptotic formula. Sounds reasonable.

I was however unable to conform the question to the Prime k-tuple or Bateman-Horn conjectures. It is thus not clear to me why it "should" be asymptotically proportional to 1/k.

I note that it is in fact a case of "multibase primes." If f(x) is a non-zero polynomial with coefficients in {0,1,2,3}, and f(4) = p, a prime, we want f(10) = N also to be prime. I note that for large p, log(N)/log(p) = 1.66, approximately [limiting value log(10)/log(4)].