# How to add numbers represented as prime factorization vectors?

Suppose we represent all positive integers as vectors of the powers of their prime factorization. Ex. $$72 = (2^3)(3^2)(5^0)(7^0)...=\{3,2,0,0,...\}$$ and applying Legendre's Theorem for example: $$n! =\{\sum_{k=1} ceil(\frac{n}{p_1^k}),\sum_{k=1} ceil(\frac{n}{p_2^k}),...\}$$ Some operations, such as multiplication, are trivial to define: $$\{a_1,a_2,...\}*\{b_1,b_2,...\}=\{a_1+b_1,a_2+b_2,...\}$$ An addition definition, if it can be given as a single statement, seems difficult to define. I'm curious to see what if one exists and what results from such a statement. $$\{a_1,a_2,...\}+\{b_1,b_2,...\}=\{?\}$$ $$3+5=8 \Leftrightarrow \{0,1,0,...\}+\{0,0,1,0,...\}=\{3,0,...\}$$ Perhaps first removing all common factors: $$\{a_1,a_2,...\}+\{b_1,b_2,...\}=\{min(a_1,b_1),min(a_2,b_2),...\}*\{?\}$$ Is there a way to define addition that doesn't require converting the vector representation back to its integer form in some way?

You are trying to bite the core of number theory. Twin primes, Goldbach's, Mersenne's, Fermat's, etc, depend on what you are asking.

To show the difficulty: $$2+7=9$$ $$3+11=14$$ $$5+13=18$$

I don't think an efficient way exists. Otherwise this would trivialize figuring out whether a number is a fermat prime or not.

one thing is clear though:

If you let $(a_1,a_2,\dots ) + (b_1,b_2,\dots )= (c_1,c_2,\dots )$

then you have $c_n=\min(a_n,b_n)$ whenever $a_n\neq b_n$.

• I see that, in addition to the distributive property the asker mentioned, you've also used the principle that a number which is a factor of one summand but not the other cannot be a factor of the sum (as is provable by considering the sum modulo that factor). That's why the min only applies whenever a_n ≠b_n. It's also true that, if a_n = b_n, then c_n ≥ a_n = b_n, by the distributive property the asker mentioned. May 12, 2023 at 4:41
• These facts reduce the computational burden of refactoring the sum inside the parentheses after the distributive property, conversion to addable notation, and addition. It's also possible to use either the prime factorization of the largest summand (which one is larger can be determined by comparing the dot product of each prime exponent vector with a vector of the logs of primes in some constant base, converting it into it's logarithm base that base) or the length of their sum in positional notation to get an upper bound on the square root of the sum if rooting it directly is too much. May 12, 2023 at 4:45