Distinct powers of 3, 4, and 5

sdkudrgn88 · Riemann Hypothesis Offline Joined: 06 Apr 2009 Posts: 300

Prove that every positive integer can be written as the sum of distinct integer powers of 3, 4, and 5.
(e.g. 29 = 3^3 + 3^0 + 4^0, 145 = 5^3 + 4^2 + 3^1 + 5^0. For the purposes of this problem, the zero powers of 3, 4, and 5 are distinct.)

**Posted:** Thu Oct 29, 2009 4:09 pm

azjps

Let $f(n)$ denote the $n$ th smallest number that may be expressed as a power of one of $\{3,4,5\}$ , so $f(1) = f(2) = f(3) = 1$ . Let $P_n(k) = 1$ if $k$ may be written as the sum of the elements of a subset of $\{f(1), \ldots, f(n - 1)\}$ [eg, satisfies conditions of problem statement], and $0$ otherwise; then we claim by strong induction that $P_n(k) = 1$ for all $k$ satisfying $0 < k \le 2f(n)$ , and $n > 1$ . Obviously, if $P_m(k') = 1$ , and $k - k'$ may be written as a sum of the elements of a subset of $\{f(m + 1), \ldots, f(n)\}$ , then $P_n(k) = 1$ .

Let $g_{k,n}(s) = k - \left[\sum_{i = 1}^s f(n - i)\right]$ ; if $0 < g_{k,n}(s) \le 2f\big(n - (s + 1)\big)$ , then by inductive hypothesis, $P_{n - (s + 1)}\left(g_{k,n}(s)\right) = 1$ , so $P_{n - 1}(k) = 1$ . Note that $\begin{align*}f(n) \le 3f(n - 1), 4f(n - 2), 5f(n - 3), 9f(n - 4),\end{align*}$ and writing out our result for $s = 0,1,2,3$ gives: $\begin{align*}0 \le g_{k,n}(0) \le 2f(n - 1) \ & \Longrightarrow\ P_{n - 1}(k) = 1,\ \forall k: 0 < k \le 2f(n - 1) \\...$ whence $P_{n - 1}(k) = 1$ for all $0 < k \le f(n)$ . Furthermore, for all $k$ satisfying $f(n) < k \le 2f(n)$ , we have $P_{n - 1}(k - f(n)) = 1$ and thus $P_n(k) = 1$ , and our problem statement is true.

**Posted:** Thu Nov 05, 2009 9:03 pm

sdkudrgn88 · Riemann Hypothesis Offline Joined: 06 Apr 2009 Posts: 300

Okay, since I don't completely understand your solution (I'm only a junior, you're already in university... Mr. Green

), I'll try and analyze it:

**Posted:** Tue Nov 10, 2009 2:56 pm

azjps

Sorry for the rather late response, also I'm only a freshmen Smile

I used a bit of condensed notation to avoid having to re-write the statements, esp $P$ just being that the proposition is true, so my apologies for that (though reading "and therefore the statement is true for this value of $k$ " fifteen times might be tiresome also Smile

).

**Posted:** Sat Nov 21, 2009 5:10 pm