mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2022-11-07, 16:32   #1
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

136178 Posts
Default Paterson primes

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)
henryzz is offline   Reply With Quote
Old 2022-11-07, 17:40   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

100000111000102 Posts
Default

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.
science_man_88 is offline   Reply With Quote
Old 2022-11-08, 14:14   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·33·5·23 Posts
Default

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
Dr Sardonicus is offline   Reply With Quote
Old 2022-11-08, 17:12   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

841810 Posts
Default

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))))
science_man_88 is offline   Reply With Quote
Old 2022-11-08, 17:21   #5
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

161110 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2022-11-08, 19:56   #6
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2×13×283 Posts
Default

From the limited data it appears the asymptotic const ~ 1.
Attached Files
File Type: pdf paterson primes trend.pdf (16.1 KB, 41 views)
kriesel is offline   Reply With Quote
Old 2022-11-10, 14:14   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

621010 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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)].
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Distribution of Mersenne primes before and after couples of primes found emily Math 35 2022-12-21 16:32
Mersenne Primes p which are in a set of twin primes is finite? carpetpool Miscellaneous Math 4 2022-07-14 02:29
Patterns in primes that are primitive roots / Gaps in full-reptend primes mart_r Prime Gap Searches 14 2020-06-30 12:42
Conjecture about Mersenne primes and non-primes v2 Mickey1 Miscellaneous Math 1 2013-05-30 12:32
possible primes (real primes & poss.prime products) troels munkner Miscellaneous Math 4 2006-06-02 08:35

All times are UTC. The time now is 06:44.


Sat Jan 28 06:44:49 UTC 2023 up 163 days, 4:13, 0 users, load averages: 0.75, 1.04, 1.16

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔