3 ms·
Is there a similar scheme using primes?
by teeray 5y ago
Is there a similar scheme using primes?
- swregert 5y agoSimilar but not totally analogous https://oeis.org/wiki/Primorial_numeral_system https://oeis.org/wiki/Primorial_numeral_system
- pacaro 5y agoThis made me think of Gödel Numbering¹, which was used in the plot of "The Gold at the Starbow's End" by Frederick Pohl² 1) https://en.wikipedia.org/wiki/G%C3%B6del_numbering https://en.wikipedia.org/wiki/G%C3%B6del_numbering 2) https://en.wikipedia.org/wiki/The_Gold_at_the_Starbow's_End https://en.wikipedia.org/wiki/The_Gold_at_the_Starbow's_End
- evanb 5y agoIf the Goldbach conjecture is true, such a scheme would be all zeros except in up two places, as long as the integer you want to encode is even. Even if the conjecture is true, the code must be ternary: to encode 6 you need to indicate 3 twice, as 6 = 3 + 3. However, very many even integers are the total of more than one pair of primes. So, the encoding of a number using this scheme is not unique. In contrast, because of the property F_n = F_{n-1} + F_{n-2} you never need more any Fibonacci number more than once in the code, so the code is binary (and the encoding unique).