I was hoping someone might know the name for this representation of the positive integers. The idea is similar to Peano's arithmetic but applied to multiplication. So we have $1$, multiplication and a function $p$. We map onto the normal integers by having p map to the nth prime. To illustrate the first few integers would be $1, p(1), p(p(1)), p(1)p(1), p(p(p(1)))$.

This representation has some unusual properties. Computing whether a number is prime is trivial, as is factorization and multiplication.

Addition however is rather tricky since you have to convert back to a normal representation, perform the addition then recursively factorized the result!

  • $\begingroup$ Do you have a finite length recipe (i.e. without pre-specifying the value of every prime in a long list) for performing addition in this setting? Even an indirect description of the form '+ is the only binary operation with this this and this property' leaving all the hard work to the reader would be fine. If such a thing exists, that is. I am not so sure here... $\endgroup$ – Vincent Nov 23 '18 at 12:52
  • $\begingroup$ I don't have any such mechanism no. You can show its related to a hard problem. Suppose we could efficiently (in polynomial time) compute addition and divide-and-remainder in this representation. It is trivial to convert a binary number into this form since 2^n is simply p(1)^n and we can therefore use addition to covert from binary into this form efficiently. But now we can use repeatedly perform divide and remainder by 2 on the factorized form to compute the binary representation of the prime components. This would allow us to extract the prime factors. $\endgroup$ – Mumrah Nov 27 '18 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.