Let's say we have two oracles, NearestPrime and IndexOfPrime, defined as follows:
Given some integer x, NearestPrime yields the prime number nearest to x that is not greater than x.
Examples: \begin{aligned} NearestPrime(3) &= 3 \\ NearestPrime(25) &= 23 \\ NearestPrime(28) &= 23 \\ NearestPrime(102) &= 101 \end{aligned}
Given some prime p, IndexOfPrime yields the index of that prime in the sequence of all primes.
Examples: \begin{aligned} IndexOfPrime(2) &= 1 \\ IndexOfPrime(5) &= 3 \\ IndexOfPrime(29) &= 10 \end{aligned}
If both the number of primes and prime gaps increase as a natural log of the integers, then couldn't we specify an integer n by the the following tuple: $$ \left(IndexOfPrime(NearestPrime(n)), \\ n \bmod NearestPrime(n)\right) $$
And, further, because both parameters are in log-space, wouldn't this be an space-efficient encoding for large integers?