4

I just came up with this question when I was thinking about the Goldbach conjecture.

For example, $$2=5 \oplus 7$$ $$4=3 \oplus 7$$ $$6=3 \oplus 5$$ $$8=3 \oplus 11$$ $$10=7 \oplus 13$$ $$12=7 \oplus 11$$ $$14=5 \oplus 11$$

I verified the even numbers up to $10^5$, there weren't any counterexamples.

If the Goldbach conjecture is true, how to prove the XOR version?

SegmentTree
  • 94
  • 2
    Question: can you find prime numbers with binary writing ending in a specified manner? Can they end in $100101$? How about $1010$ ? – orangeskid Jun 26 '22 at 13:08
  • 1
    @orangeskid $100101_2=37_{10}\in\mathbb{P}$, but there are no primes with a binary representation ending in $0$ except $p=2$. I think the more relevant question is whether for $k$ with binary representation $k=a_n..a_0$ where $a_0=0$ one can find primes $p_1$ and $p_2$ with binary representations $p_1=b_m..b_{n+1}b_n..b_0$ and $p_2=c_m..c_{n+1}c_n..c_0$ such that $k=p_1 \oplus p_2$ which requires $\left(b_m..b_{n+1}\right) \oplus \left(c_m..c_{n+1}\right)=0$ (which is satisfied only when $b_m..b_{n+1}=c_m..c_{n+1}$) and also requires for $0\le j\le n$ that $b_j\ne c_j$ only when $a_j=1$. – Steven Clark Jun 26 '22 at 16:54
  • 2
    I don't see any relationship between the Goldbach conjecture and the conjecture in this question as the Goldbach conjecture is based on normal addition and requires $p_1,p_2<k$ whereas the conjecture here is based on the exclusive-or operation and has no bound on the magnitude of $p_1$ and $p_2$ with respect to $k$ (i.e. the magnitude of $m$ with respect to $n$). I suspect the conjecture here is perhaps impossible to prove unless one puts a bound on the magnitude of $m$ with respect to $n$ in which case one could perhaps find a contradiction. – Steven Clark Jun 26 '22 at 16:54
  • @Steven Clark: It seems you can prescribe any binary ending for a prime, provided the last one is not $0$. I have to do some more testing. Cheers! :-) – orangeskid Jun 26 '22 at 17:18
  • A similar question, since $+$ and $- \mod 2$ are the same: is every even number a difference of primes, see here – orangeskid Jun 26 '22 at 17:28
  • 1
    @orangeskid Sorry, but I don't understand your point. It is true that for bit operations $b_j \oplus c_j=\left(b_j+c_j\right) \mod 2=\left(b_j-c_j\right) \mod 2$, but the bit-wise exclusive-or operation $k=p_1 \oplus p_2$ has no carries whereas normal addition operation $k=p_3 + p_4$ has carries, and $\left(p_3+p_4\right) \mod 2=0$ isn't particularly useful, so I still don't see any relationship between the two conjectures. Assuming $k=p_1 \oplus p_2=p_3 + p_4$ how are you saying $p_1$ and $p_2$ are related to $p_3$ and $p_4$? – Steven Clark Jun 26 '22 at 17:42
  • Every even number upto $138\ 472\ 076$ (including $0$) allows such a representation with one of the primes not exceeding $941$. I do not see any way either to prove this new conjecture assuming Goldbach is true. – Peter Jun 27 '22 at 11:58
  • I'm wondering if one can even disprove the stronger conjecture there are an infinite number of prime pairs $p_1,p_2$ for which $k=2 j=p_1 \oplus p_2$ where $j\in\mathbb{N}$ and $p_1,p_2\in\mathbb{P}$? – Steven Clark Jun 27 '22 at 15:17
  • @StevenClark How is this a stronger conjecture ? This conjecture does not imply that every even number allows such a representation. And that there are infinite many prime pairs $(p_1,p_2)$ such that the XOR sum is even is obvious since we only need that the primes are odd. – Peter Jun 29 '22 at 07:01
  • @Peter Sorry, I'm not following you. My stronger conjecture is that every even number $k=2 j$ can be represented by the bit-wise XOR of an infinite number of prime pairs. The case $k=2$ is dependent on the twin-prime conjecture but also depends on the what I refer to as the "parity" of the prime pair (see https://oeis.org/A074381). – Steven Clark Jun 29 '22 at 14:13
  • In case I'm still not making my self clear, let ${p_{k,n,1},p_{k,n,2}}$ be the $n^{th}$ prime pair for which $k=2 j=p_{k,n,1} \oplus p_{k,n,2}$. My stronger conjecture every even integer $k=2 j$ has an infinite number of such prime pairs. The first few prime pairs for the case $k=2$ are $2=5 \oplus 7=17 \oplus 19=29 \oplus 31=41 \oplus 43$. – Steven Clark Jun 29 '22 at 23:00
  • OK, I think, now I got it. – Peter Jun 30 '22 at 06:52

0 Answers0