-5
$\begingroup$

I am exploring the question of efficiently identifying two prime numbers that sum to a given large even number, particularly for even numbers exceeding 100 digits. While brute force and precomputed prime tables are common approaches, I am curious whether there exists a deterministic algorithm capable of solving this problem, given sufficient computational resources.

Specifically, I am interested in methods that:

Avoid reliance on probabilistic techniques (e.g., random sampling of primes).
Operate deterministically to find a valid prime pair for any even number within the given constraints.
Scale efficiently as the size of the even number increases.

Are there any existing algorithms or advancements in this area that can achieve this deterministically? Alternatively, is there ongoing research into related methods for efficiently handling this problem?

I would appreciate any insights or pointers to theoretical or computational techniques that address this challenge. Thank you for your time and expertise.

Follow up

Thank you for your detailed response. I appreciate the breakdown of traditional approaches to finding Goldbach pairs and the reliance on probabilistic models like Cramer's, as well as the discussion of deterministic primality testing methods like AKS.

That said, I believe I may have phrased my question too narrowly. I’m exploring whether there exists a deterministic algorithm that can directly locate Goldbach pairs for any even number, including numbers of 100 digits or larger, without relying on probabilistic heuristics, exhaustive primality testing, or precomputing prime tables.

Improve this question
New contributor
Dood is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
7
  • 1
    $\begingroup$ I'm not a computational number theorist and so do not know the specifics, but I expect if you look up the papers verifying Goldbach up to some large number, those papers will tell you what methods they used. $\endgroup$
    – Jakob Streipel
    Commented yesterday
  • 1
    $\begingroup$ Thank you for your detailed answer, @JakobStreipel. I’ve added a follow-up to the original question to clarify and expand on my inquiry. I’d greatly appreciate it if you could take a look when you have a moment. $\endgroup$
    – Dood
    Commented yesterday
  • 2
    $\begingroup$ "My purpose in asking this question is not to make bold claims...." "based on my proof of the Goldbach conjecture...." Looks like a bold claim to me.... $\endgroup$
    – Gerry Myerson
    Commented 11 hours ago
  • 2
    $\begingroup$ "demonstrate the capabilities of my work and allow the results to speak for themselves." this sounds like an announcement of results, not asking a question. As such I think this angle to your post is off-topic. $\endgroup$
    – David Roberts ♦
    Commented 5 hours ago
  • $\begingroup$ It's curious that none of you have engaged with the mathematics itself. My work demonstrates something unprecedented efficiently finding prime pairs for even numbers of extreme size. Instead of addressing how this is achieved or testing it, the focus has been on dismissing me personally or nitpicking phrasing. If you are truly mathematicians driven by curiosity and truth, then why not explore the substance of the work? Engage with the math, not the messenger. $\endgroup$
    – Dood
    Commented 4 hours ago

1 Answer 1

Reset to default
5
$\begingroup$

Cramer's random model suggests that the probability that $a, n-a$ are both primes is $\frac{1}{\log(a)\log(n-a)}$. For fixed $n$, this is is maximized for $a$ small (or $n-a$ small) suggesting that the most efficient method would be to first check if $n-3$ is prime, then $n-5$, then $n-7$, and so on.

For $n$ enormous and $a$ small, the natural approach would be to use a precomputed table for small primes $a$ and a primality test for large primes $n-a$. You want to use deterministic approaches, but thankfully there is the AKS deterministic primality test.

Following Jakob Streipel's suggestion, I observe that at least one Goldbach verification, the one by Tomás Oliveira e Silva, and probably most/all of them focus on finding the least $a$ such that $a$ and $n-a$ are both primes, and therefore use a similar overallstrategy.

The heuristic suggests that almost all numbers $n$ should have a prime solution $a$ less than about $\log n \log \log n$. For $n< 4 \cdot 10^{18}$, the worst case has $a < 10^4$. I therefore suspect that for $n$ of $100$ digits one should still only need to take $a<10^5$ or so, so one should need to use only a tiny precomputed table and run the primality test at most 9592 times, which seems fine.

I'm not sure what you mean by "a deterministic algorithm capable of solving this problem, given sufficient computational resources". If you want an algorithm that is guaranteed to solve the problem, assuming a prime pair exists, then you may need to provide sufficient computational resources to search every prime up to $n/2$.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ It might be better to sieve around $n$ using small-ish primes (like in the segmented sieve algorithm) before doing expensive primality tests $\endgroup$
    – Daniel Weber
    Commented yesterday
  • 1
    $\begingroup$ Thank you for your detailed answer, Professor @WillSawin , Daniel Weber. I’ve added a follow-up to the original question to clarify and expand on my inquiry. I’d greatly appreciate it if you could take a look when you have a moment. $\endgroup$
    – Dood
    Commented yesterday
  • $\begingroup$ "If you want an algorithm that is guaranteed to solve the problem, assuming a prime pair exists, then you may need to provide sufficient computational resources to search every prime up to 𝑛/2" — this leaves me curious; assuming Goldbach's conjecture, is there anything known about the behavior of a 'minimal' Goldbach pair? e.g., can we prove that if it exists then for any $\epsilon$ there's always a pair $p+q$ with $p\lt o(n^\epsilon)$? $\endgroup$
    – Steven Stadnicki
    Commented 12 hours ago
  • 2
    $\begingroup$ @StevenStadnicki No, I don't think there are any methods to prove results of this type. Even if there were it would probably not be nearly as strong as what you state - your statement implies that there is a prime within $o(n^\epsilon)$ of $n$, which is stronger than the best bounds on prime gaps we can prove even assuming the Riemann hypothesis. $\endgroup$
    – Will Sawin
    Commented 11 hours ago
  • $\begingroup$ @StevenStadnicki &WillSawin: Thank you for the thoughtful comments. The guarantee of Goldbach pairs doesn’t rely on bounds like p< o(n^e), which align with finite views constrained by prime gaps and the Riemann hypothesis. My proof reveals the deterministic nature of primes in an infinite context, where such pairs inevitably exist, though not as traditionally expected. This shift underpins the framework enabling my algorithm’s efficiency. Proving Goldbach led to new insights on the Riemann Hypothesis it's true but unprovable within traditional methods, linking to Gödel's incompleteness theorem $\endgroup$
    – Dood
    Commented 9 hours ago

Not the answer you're looking for? Browse other questions tagged .