# Prime factorization formalism

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!

• 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... – Vincent Nov 23 '18 at 12:52
• 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. – Mumrah Nov 27 '18 at 16:00