Can all naturals can be expressed as sums of prime powers of $\{3,5,7,13\}$?

Question

Define the set $$S=\left\{(p,k) \mid p\in\{3,5,7,13\} \land k \in\mathbb Z^{0+}\right\}.$$

The question is whether every natural number $n$ can be expressed as the sum of some subset $s\subseteq S$ of distinct pairs $(p,k)$ such that $$n=\sum_{(p,k)\in s}{p^k}.$$ To be clear, any pair in $S$ may be used at most once in the sum, though $k=0$ is allowed as an exponent. As an example, when using only the primes $\{3,5,7\}$, $24$ has two valid representations:

$$ 3^1+3^2+5^1+7^1 = 3^0+3^2+5^0+5^1+7^0+7^1 = 24. $$

Another way to describe the problem is to ask whether every natural can be described as the sum of four numbers, one each in bases 3, 5, 7, and 13, using only $0$ and $1$ digits. So equivalently, in that formulation, $$110_3+10_5+10_7=101_3+11_5+11_7=24.$$

Using $\{3,5,7,13\}$ gives 20 representations for $24$, which seemed a little spammy to include.

This post is a direct follow-up to this one, which posed the same question for $p\in\{3,5,7\}$. A nice proof was given that that set isn't sufficient to cover the naturals; the bottom line is that this arises because $$\frac{1}{3-1}+\frac{1}{5-1}+\frac{1}{7-1}=\frac{11}{12}<1.$$

This leaves open the interesting edge case of whether it would be possible for $\{3,5,7,13\}$, as $$\frac{1}{3-1}+\frac{1}{5-1}+\frac{1}{7-1}+\frac{1}{13-1}=1.$$

---

Note: To explain comments below, I originally thought I had a counterexample, but that was a rounding error. I'm leaving this question up as it seems like it still has merit. Clever arguments as to why $\{3,5,7,13\}$ should or should not work are also welcome.

---

Update

It actually seems like you may be able to limit this to proper prime powers after all, i.e. disallowing $p^0$ terms, for all $n\geq 113$. The only numbers I can find at first glance that require them are $\{1, 2, 4, 6, 11, 26, 31, 107, 112\}$ (though this is not proven!) So if you confine yourself to $n \geq 113$, each term $p^k$ in the sum must be distinct, no caveats required.

This seems like a cleaner formulation of the problem, but it's unclear to me which version would is more likely to be tractable or of greater interest. Input on this welcome.

Answer 1

I cannot confirm your counterexample. Here are the details so nobody else has to duplicate this effort. Following the method from Brian Moehring's answer, we want to find a value of $n$ such that $\log_5(3^n - 1), \log_7(3^n - 1), \log_{13}(3^n - 1)$ all have fractional parts close to $1$. If their integer parts are $n_5, n_7, n_{13}$, it then suffices to show that

$$\sum_{p = 3, 5, 7, 13} \left( \sum_{k=0}^{n_p} p^k \right) = \sum_{p = 3, 5, 7, 13} \frac{p^{n_p + 1} - 1}{p - 1} < 3^n - 1.$$

With $n = 338993010578$ we get (noting that $3^n$ is never a power of any other prime so $\lfloor \log_p(3^n - 1) \rfloor = \lfloor \log_p(3^n) \rfloor = \lfloor 3 \log_p n \rfloor$) we get (computations done in WolframAlpha)

$$n_3 = n - 1 = 338993010577$$ $$n_5 = \lfloor n \log_5 3 \rfloor = 231398728907$$ $$n_7 = \lfloor n \log_7 3 \rfloor = 191386990490$$ $$n_{13} = \lfloor n \log_{13} 3 \rfloor = 145196584918$$

and now it remains to show the desired inequality. If we try to compute the sums above directly we may run into rounding errors; we can do the following instead. First, since $\sum_{p = 3, 5, 7, 13} \frac{1}{p - 1} = 1$, we can add $1$ to both sides to convert the desired inequality into the slightly simpler form

$$\sum_{p= 3, 5, 7, 13} \frac{p^{n_p + 1}}{p - 1} < 3^n.$$

Second, we can divide both sides by $3^n$ to convert the inequality into the form

$$\sum_{p=3,5,7,13} \frac{3^{(n_p+1) \log_3 p - n}}{p - 1} < 1.$$

From here we see that to get the desired inequality it suffices (again using the fact that $\sum_{p=3,5,7, 13} \frac{1}{p-1} = 1$) that $3^{(n_p+1) \log_3 p - n} \le 1$ for each $p$ and that the inequality is strict for at least one $p$. Taking logs, equivalently we want $(n_p + 1) \log_3 p \le n$ or

$$n \log_p 3 \ge n_p + 1.$$

Unfortunately this is false for $p = 5, 7, 13$ since by definition we have $n \log_p 3 < n_p + 1$ (and we have equality for $p = 3$). So $3^{(n_p + 1) \log_3 p - n} > 1$ for $p = 5, 7, 13$ which implies that the inequality in Brian Moehring's answer cannot hold in this case for any value of $n$. The method can be salvaged if you show that one of the largest powers can't appear in the sum but this seems tricky.

Answer 2

Let $n_1, n_2, n_3, \dots$ be a nondecreasing sequence of integers $\geq 1$. Let $s_0 = 0, s_k = s_{k-1} + n_k$ for $k \geq 1$.

Then every integer is the sum of a finite subsequence of the $n_k$ if and only if $n_k \geq s_{k-1} + 1$. Proof: if the condition is met then by induction over $k$ all $n \leq s_k$ are the sum of a subsequence of the first $k$ numbers. Otherwise if $k$ is the smallest $k$ such that the condition is not met, then $n_k - 1$ is not the sum of any subsequence.

If we sort the prime powers in non-descending order then $\frac{1}{p_1-1} + \dots + \frac{1}{p_4-1} \geq 1$ guarantees the condition above. If the sum is less than $1$ then the condition above will fail if there are $4$ prime powers very closely together. A counter example can then be found by sorting the prime powers and calculating the sequence $n_k$ and $s_k$.

Proof: Assume we calculated up to $n_k$ and $s_k$, and the next $4$ powers are $a, b, c$ and $d$. Then $s_k = \frac{a-1}{2} + \frac{b-1}{4} + \frac{c-1}{6} + \frac{d-1}{12}$. Let $x$ be the smallest of $a, b, c, d$ then $s_k \geq \frac{x-1}{2} + \frac{x-1}{4} + \frac{x-1}{6} + \frac{x-1}{12} = x-1$, and $n_{k+1} = x \geq s_k +1$ as required.

There is no need for any or all of the numbers to be primes at all, as long as they are integers.