Squeezing primes

Question

Any positive odd number $n$ can be coded one binary digit smaller by the rule $\frac{n-1}{2}$ and that's obviously the best squeeze: a bijection from $\mathbb N$ such that $f(n)\geq n$. I'm looking for "elementary" squeezing bijections to the primes. The bijection $n\mapsto p_n$ is the non elementary optimum. A non optimal squeezing bijection has a proper subset $S\subset\mathbb N$ as domain, $f:S\to\mathbb P$, where $f(s)\geq s$.

Is there an elementary squeezing bijection for primes such that the number of saved binary digits is a non bounded increasing function as the primes increase?

Is there an example of a simple bijection that save at least 8 bits for all primes greater than some number?

---

Reformulation:

I wanted to know if there was a simple and fast algorithm to squeeze prime numbers into smaller numbers, which likewise simple and fast could be transformed back to the corresponding prime.

The $\displaystyle\frac{p-1}{2}$ squeeze save 1 bit for odd primes.

A $\displaystyle\frac{p}{3}$ squeeze is also possible, since the set $\{3\cdot\lfloor\frac{p}{3}\rfloor+1,3\cdot\lfloor\frac{p}{3}\rfloor+2\}$ contains of a prime and an even number.

But for a slowly increasing function as $p_n$ there is no hope, since the optimal bit saving is very little: 50000 has just 4 binary digits less than $p_{50000}=611953$. For primes of size $10^{23}$ is the maximal bit saving 6 bits.

Answer 1

There really are methods to squeeze primes very effective when using extra information besides the prime or the squeezed prime. It's possible to store each prime in one byte when making arrays to read $p_n$. The needed extra information is the number $n$: all the primes $p_1,\dots,p_{54}$ is less than $2^8$. So if $n=55,56,\dots$ just store $p\!\!\mod 256$ at that place in the array and get a byte array with byte squeezed array for the primes $p_1,\dots,p_{97}$. To find prime number $85$ read the array at position 85 and add $256$ since $85>54$.

With help of an array of breakpoints $54,97,\dots$ the method can be used for prime number arrays up to the first gap including a whole intervall modulo $256$. Using two bytes for each prime number the array will work at least to the occurrence of the first prime gap of size $2^{16}$.

I just didn't think outside the box when I asked the question.

Answer 2

Here is a way to save any constant number of bits.

Let $N$ be an integer so that $\frac{\varphi(N)}{N}<\varepsilon$ ($N=k\#$ (primorial) for large enough $k$ will work). Let's fix a bijection $g:\Phi(N)\rightarrow\{0,1,...,\varphi(N)-1\}$, where $\Phi(N)$ is the set of numbers below $N$ relatively prime with it. For every prime $p$ not dividing $N$ we have $p\mod N\in\Phi(N)$. Now we can code $p$ as a number $f(p)=\varphi(N)\lfloor\frac{p}{N}\rfloor+g(p\mod N)$. This codes all but finitely many primes (which could be easily fixed), and we can decode $p=N\lfloor\frac{f(p)}{\varphi(N)}\rfloor+g^{-1}(f(p)\mod\varphi(N))$.

Now $f(p)<\varphi(N)\lfloor\frac{p}{N}\rfloor+\varphi(N)<\frac{\varphi(N)}{N}(p+2N)<2\varepsilon p$ for $p$ large enough. By taking $\varepsilon=\frac{1}{2^{n+1}}$ we see that we can save up to $n$ bits.