4
$\begingroup$

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.

$\endgroup$
9
  • 2
    $\begingroup$ The numerical methods tag does not seem to be a best fit. However, if you were to include the code that you suspect of containing a rounding error, then it could be an interesting question for the tags numerical-methods and floating-point. $\endgroup$ – Carl Christian Jan 18 at 20:25
  • 1
    $\begingroup$ Since all of $1,2$ and $3$ are less to $3^0+5^0+7^0+13^0=4$ these three first natural must be excluded firts at all. $\endgroup$ – Piquito Jan 18 at 20:30
  • 1
    $\begingroup$ @Piquito $1 = 3^0$, $2 = 3^0 + 5^0$, $3 = 3^1$. $\endgroup$ – Robert Israel Jan 18 at 20:50
  • $\begingroup$ @PM2Ring OP gave an example for $24$ including $3^0$, $5^0$ and $7^0$. $\endgroup$ – Robert Israel Jan 18 at 22:16
  • 1
    $\begingroup$ Added a clarification re: distinctness. I can never get my formalizations right. $\endgroup$ – Trevor Jan 18 at 23:08
3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I don't think you should accept this answer! This doesn't resolve your question either way. $\endgroup$ – Qiaochu Yuan Jan 19 at 4:58
  • $\begingroup$ Thanks for working through this. I found my error, and this result sits intuitively much better with me than a simple counterexample result did. $\endgroup$ – Trevor Jan 19 at 5:08
  • $\begingroup$ Sure it does. It shows that Brian's inequality approach won't work, which ruled out my counterexample and is a significant result; I expect it's too tricky of a problem to expect any more. $\endgroup$ – Trevor Jan 19 at 5:10
-1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is wrong, and counterexamples are easy to find. $\endgroup$ – Robert Israel Jan 20 at 15:14

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.