On a certain kind of integer partitions

Question

Background: I am investigating partitioning integers using a fixed radix base.

Problem: Suppose we have $x$, an arbitrary integer. Let $M = \{2, 3, 5, ..., p\}$ be a set of prime moduli.

The prime factorization $$x = 2^{e_0}3^{e_1}5^{e_2} \cdots p^{e_p}, e_j \ge 0 \tag 1$$ is not always possible since $x$ may have a factor $q \notin M$.

Suppose we partition $x$ into $k$ partitions as $$x = x_0 + x_1 + \cdots + x_{k-1} \tag{2}$$

Is it true that there exists a partition of $x$ such that $\forall x_i$ in that partition, there is a representation of the form $(1)$?

Trivially, if we take $M = \{2\}$, we get the sum of powers of $2$ (binary representation) as the partition of $x$. So, we know the partition exists when $M$ is a singleton set consisting of a single element $b$ since a base-$b$ representation for $x$ can be found.

Also, a trivial partition exists by setting the exponents to $0$ (and we get the unitary representation $x = 1 + 1 + \cdots + 1$ ($x$ times).

I suppose one could find the largest integer smaller than $x$ in the form $(1)$ and then use the unitary representation for the residual. So, the answer to the existence question is probably True.

Define a non-trivial partition as one in which each part has more than one prime factor.

Define an optimal non-trivial partition as a non-trivial partition of length $k$ (i.e., $k$ parts with each part having more than one prime factor) with $k$ minimal.

Does an optimal non-trivial partition with not all exponents $0$ exist when $M$ is a non-trivial set of primes?

Answer 1

If $M = \{2\}$, of course there is never any nontrivial partition, since there is only one prime: $2$. Every prime factorization with only primes in $M$ will only have one prime factor.

If $M = \{2,3\}$, there is not always a non-trivial partition of every number $x$. Whenever $x$ is odd, if we split up $x$ as $x_0 + x_1 + \dots + x_{k-1}$, some $x_i$ must also be odd; if it factors in terms of primes in $M$, it must be a power of $3$. But then it has only one prime factor, so the partition is trivial.

Once $M = \{2,3,5\}$, every sufficiently large $x$ will have a nontrivial partition; in particular, every $x \ge 35$. Consider $x$ mod $6$:

• If $x \equiv 0 \pmod 6$, then we can write $\frac x6$ in binary, and multiply every term by $6 = 2 \cdot 3$ to get a nontrivial partition.

• If $x \equiv 1 \pmod 6$, use the first case to get a nontrivial partition of $x - 25$, and then add $2 \cdot 5$ and $3 \cdot 5$.

• If $x \equiv 2 \pmod 6$, use the first case to get a nontrivial partition of $x - 20$, and then add $2^2 \cdot 5$.

• If $x \equiv 3 \pmod 6$, use the first case to get a nontrivial partition of $x - 15$, and then add $3 \cdot 5$.

• If $x \equiv 4 \pmod 6$, use the first case to get a nontrivial partition of $x - 10$, and then add $2 \cdot 5$.

• If $x \equiv 5 \pmod 6$, use the first case to get a nontrivial partition of $x - 35$, and then add $2^2 \cdot 5$ and $3 \cdot 5$.

However, small $x$ might not have a nontrivial partition; for example, what are you going to do when $x = 4$?

We can use the same argument to show that there is a nontrivial partition whenever $|M| \ge 3$, provided $x$ is large enough. Here, $M$ doesn't even have to be the set of the first $|M|$ primes; some set like $\{3, 11, 97\}$ will work. In fact, we can take this approach to find a partition of large-enough $x$ in which every $x_i$ has at least $|M|-1$ prime factors. (This is best possible, because if you have to use all $|M|$ prime factors, you can never get something not divisible by the product of all primes in $M$.)