27
$\begingroup$

My question is whether it is possible to represent every positive integer as the sum of any number of unique terms $b^x$, where $b\in\{3,5,7\}$, and integer $x \geq 0$.

(Note this would be trivially easy if using the prime base $2$ were allowed, as using additive terms $2^i$ is essentially how binary numbers are written.)

For example, in my scenario, $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 $$

My instinct is that this shouldn't hold, but I haven't been able to find a counterexample yet or a convincing argument against it. I have been able to find empirical evidence that it doesn't work for almost all larger triples, e.g. $\{3,7,13\}$.


Edit

While Brian provided a nice counterexample to my $\{3,5,7\}$ case, it's natural to ask whether the same result will hold for $\{3,5,7,11\}$, or in general, for any finite subset of odd primes. Also remaining is the question of how to effectively determine the minimum counterexample for a given set.

$\endgroup$
14
  • 3
    $\begingroup$ $3^0$ + $5^0$. Exponents may be repeated, it's the entire term ($3^0$, say) that can't be repeated. $\endgroup$
    – Trevor
    Commented Aug 15, 2019 at 10:39
  • $\begingroup$ Oh okay, got your question now. $\endgroup$
    – Toby Mak
    Commented Aug 15, 2019 at 10:40
  • 1
    $\begingroup$ How in the representation $24=3^1+3^2+5^1+7^1$ does the condition "without using any single prime power twice" hold? $\endgroup$ Commented Aug 15, 2019 at 11:17
  • 4
    $\begingroup$ The heading of the question makes some sense, but the text inside contradicts the heading in various ways, which renders it senseless to me. You start by asking "distinct powers" and then you give an example with repeating powers, both zero and one. You write in the text "prime powers of $3$,$5$ and $7$", which in English means $3^p$ or $5^p$ or $7^p$ where $p$ can take only prime values. But then you write powers of zero. So after guessing more or less what the question is, there can be various guesses as to what the answer can be. $\endgroup$ Commented Aug 15, 2019 at 11:29
  • 2
    $\begingroup$ @RoddyMacPhee There's still an ambiguity here, since by that definition of "prime power" excludes $p^0$ (and also, if we simply appended it to the definition, would make $3^0 + 5^0$ inadmissible by the "distinct" qualification). It's apparent to me that he meant "For each positive integer $n,$ there are finite subsets $I_3, I_5, I_7$ of the non-negative integers such that $$n = \sum_{i \in I_3} 3^i + \sum_{i \in I_5} 5^i + \sum_{i \in I_7} 7^i,$$ but this is inferred from the examples rather than from the definitions (in any case, this is the least strict interpretation, and it's false) $\endgroup$ Commented Aug 15, 2019 at 20:00

1 Answer 1

34
$\begingroup$

$3^{60} - 1$ isn't achievable.

This can be seen as $$\lfloor\log_5(3^{60}-1)\rfloor = 40 \\ \lfloor\log_7(3^{60}-1)\rfloor = 33$$ but $$\sum_{n=0}^{59} 3^n + \sum_{n=0}^{40} 5^n + \sum_{n=0}^{33} 7^n < 3^{60} - 1$$


Edit: Please also see the generalization given by user687721 in the comments. If you can understand what is said there, you'll see what I did here is just a specific example of that procedure, and the resulting test given in the comment could be done by a grade-schooler with a pencil (whereas I needed a computer, or at least a decent calculator, for several steps)

$\endgroup$
20
  • 2
    $\begingroup$ It's definitely not the lower bound. I was just searching for numbers of the form $n = 3^m - 1$ such that the fractional parts of $\log_5(n)$ and $\log_7(n)$ were close to $1.$ A few other possible candidates happened before $m=60,$ but this one looked the most promising (I had an early false positive, so I made my threshold for acceptance rather strict after going through the process of testing it) $\endgroup$ Commented Aug 15, 2019 at 11:39
  • 2
    $\begingroup$ What if the exponents have arbitrary gap between them instead of being serial numbers? E.g. $3^0 + 3^4 +3^{23} + \ldots$ $\endgroup$ Commented Aug 15, 2019 at 11:53
  • 4
    $\begingroup$ @Nilos I don't think that matters. He's showed that even if you use every possible term up through $3^{59}$, $5^{40}$, and $7^{33}$, you won't reach $3^{60}$, and any larger terms will overshoot all by themselves. Very nice! $\endgroup$
    – Trevor
    Commented Aug 15, 2019 at 11:57
  • 1
    $\begingroup$ @Nilos For any subset $I \subseteq \{0,1,2,\ldots, 59\},$ $$\sum_{i \in I} 3^i \leq \sum_{n=0}^{59} 3^n$$ so we still have a strict inequality when compared to $3^{60}-1$ $\endgroup$ Commented Aug 15, 2019 at 11:58
  • 10
    $\begingroup$ Suppose that $p_i$ are a set of multiplicatively independent integers (distinct primes, for example). By Kronecker, one can find simlutaneous rational approximations $a_i/a_1$ to the quantities $\log(p_1)/\log(p_i)$ where the error is of the form $\epsilon/a_1$ for sufficiently small $\epsilon$. Then all the powers $(p_i)^{a_i}$ are the same order (up to multiplication by $1 + o(1)$), taking $N$ to be $1$ less than the smallest one you win as long as $\sum \frac{1}{p_i - 1} < 1$ (e.g. $1/2+1/4+1/6=11/12$ in this case). This certainly deals with all triples of distinct primes not involving $2$ $\endgroup$
    – user687721
    Commented Aug 15, 2019 at 12:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .