1
$\begingroup$

Instead of a list of prime numbers, we will be using $B_{p}(2n)$, a binary representation of the distribution of prime numbers from $3$ to $2n$. Simply writing 0 for non-primes and 1 for primes, we get something like this: $$B_{p}(2n)=101010001010001010001$$ Now the algorythm: $$ B_{g}(2n)=B_{p}(2n)+reverse(B_{p}(2n)) $$ And thats it.

Example: (we treat $B_{p}(2n)$ like if it's in base 10)

$$B_{g}(2n)=101010001010001010001+100010100010100010101=201010101020101020101010102$$
We now have $B_{g}(2n)$ where the $2$'s represent the Goldbach partitions.

Question: What would be the time complexity of the algorithm for finding:

A: The number of Goldbach partitions (count occurrence of 2 in $B_{g}(2n)$)?
B: The Goldbach partitions (get indexes of $2$'s in $B_{g}(2n)$)?


Tested results
I've been using this algorithm a lot lately while working on Goldbach's conjecture, and it is blazing fast. Getting $g(500000000)$ takes about 1.5 seconds. In my case i was coding in php, which have the bcadd() function that does addition for numbers up to 2 billion digits, but also strrev() to reverse the string and substr_count() to count occurrence of $2$ in the string, so i have no loop in my code.

Moreover, $B_{p}(2n)$ is easier to compute than a list of primes, because it contains a lot less information. One could use sieving over a big string "1111111111..." to switch all non-prime to $0$

$\endgroup$
1
$\begingroup$

Unless you have a way to compress your $B_p(2n)$, any algorithm that handles those long integers (from reversing, to addition, to scanning $B_g$ for a 2) has the time complexity of at least O(n), because it needs to actually access each of those $2n$ digits.

And that doesn't take into account how to actually get the $B_p$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.