Storing large natural numbers as the sum of 2 primes? How efficient is it? [closed]

prime-numbers

I ask this as someone who loves maths but has no ability. So 2 axioms & a question.

Axiom 1 - a digital processor exists that can find the n'th prime number of any size instantly. Axiom 2 - all natural numbers can be expressed as the sum of 2 primes.

Would it take more/less/same amount of bits to define a natural number exactly as the sum of primes or as traditional POW2 digital format and will that fact apply to all natural numbers whatever their size? I presume a +/- wouldn't be needed because if it's a - then the larger prime is given first. I'm also interested to know if it's ALWAYS more/less efficient or is their a numerical point at which the optimal solution alters.

Maybe it's a very badly written question. If so, I can only apologise. I have wondered this for 20 years but never had anywhere to ask. Thanks.


Solution 1:

The ordinary way of storing natural numbers by means of bits is already optimal. This can easily be seen: Each of the $2^n$ combinations of assignments of $n$ bits represents exactly one distinct natural number between $0$ and $2^n-1$. If there was a way of storing more numbers with the same amount of bits, and we would try to create the mapping between the combination of bits and the actual numbers, we would necessarily end up with a combination of bits that maps to more than one natural number, see pigeonhole principle. This obviously does not make sense, because we want each number to be unambiguously represented as a certain "bit pattern" in the memory.

But it is even worse: We know for sure, that there are infinitely many numbers that can be represented as sum of two primes in more than one way (see Infinitely many even numbers that can be expressed as the sum of $m$ primes in $n$ different ways). This means, that there will be definitely fewer natural numbers than unique combinations of two primes. Even if your axioms were true, you would have to represent the pairs of primes in such way that each sum appears only once, i.e. you need some magic that skips the combinations that map to natural numbers that are already covered by other prime pairs.

Related

Geometrical meaning of orientation on vector space
Give an example to show that the inequalities are strict inequalities
An example of distributional limit
Make $2$ cubes out of $1729$ unit cubes, expected number of times you have to paint
calculating the wedge product for 2 4D vectors
Why does a group homomorphism preserve more structure than a monoid homomorphism while satisfying fewer equations
How to reverse digits of an integer mathematically? [duplicate]
A complex number $a+bi$ as a continued fraction.
Show that $R\cong R_P$, the ring of quotients of $R$ with respect to the multiplicative set $R-P$ if $R$ has exactly one prime ideal $P$.
If one plays $132$ games in $77$ days, there is a span of consecutive days with exactly $21$ games
limit of $\lim_{n\to \infty} (-1)^{n-1} \sin(\pi \sqrt{n^2 + 0.5n + 1})$ what am I doing wrong?
Find the minimum value of $\sin^{2} \theta +\cos^{2} \theta+\sec^{2} \theta+\csc^{2} \theta+\tan^{2} \theta+\cot^{2} \theta$