High school contest math question (number theory) - prove:

Reposting with Mathjax - sorry, first time!

Let $$S = \{4,8,9,16,...\}$$ be the set of integers of the form $$m^k$$ for integers $$m, k \ge 2$$. For a positive integer $$n$$, let $$f(n)$$ denote the number of ways to write $$n$$ as the sum of (one or more) distinct elements of $$S$$. For example, $$f(5) = 0$$ since there are no ways to express 5 in this fashion, and $$f(17) = 1$$ since $$17 = 8+9$$ is the only way to express 17.

(a) Prove that $$f(30) = 0$$

(b) Show that $$f(n) \ge 1$$ for $$n \ge 31$$.

(c) Let $$T$$ be the set of integers for which $$f(n) = 3$$. Prove that $$T$$ is finite and non-empty, and find the largest element of $$T$$.

I think that part a) is relatively easy to just check since none of the values in the first few values of the set $$S = \{4,8,9,16,25,27,32,64,...\}$$ will add to get to 30.

I'm not sure where to start with part b and part c. For part b, I was working at finding sums for each number but figured this was not an intelligent way to proceed. For part c) I'm not sure where to start at all.

• Why 1 isn't in S? – Toni Mhax Dec 14 '20 at 3:44
• @ToniMhax $1$ is not a perfect power where the base and exponent are both $\ge 2$ – Benjamin Wang Dec 14 '20 at 3:47
• @RossMillikan Part of the question states that $f(n)$ denotes the number of ways to write $n$ as the sum of one or more distinct elements of $S$. Since $32$ is in the set, I assume by the question's wording that it itself counts as a way to represent it. (Also I just copied this question word for word from the collection of contest questions) – bobby_mc_gee Dec 14 '20 at 4:01
• Yes, I now believe the question is correct and you do use distinct values. – Ross Millikan Dec 14 '20 at 14:07

For part b, note that all multiples of $$4$$ can be represented because you have all the powers of $$2$$ except $$1,2$$. Express any multiple of $$4$$ in binary and read off the numbers to add to get it. All numbers equivalent to $$1 \bmod 4$$ that are at least $$9$$ can be expressed because the number minus $$9$$ is a multiple of $$4$$ and therefore expressible. All numbers equivalent to $$2 \bmod 4$$ that are $$34$$ or greater are expressible because $$34=9+25$$. All numbers equivalent to $$3 \bmod 4$$ that are $$27$$ or greater because we have $$27$$ available. Therefore the greatest number that cannot be expressed is $$30$$.

For c, numbers that are large enough will have too many representations. We will do each residue class $$\mod 4$$ in turn.

For $$0 \bmod 4$$ we have $$\emptyset,36, 9+27, 25+27$$ as ways to express numbers without any of the $$2^n$$ terms. We can therefore express any number $$52$$ or greater in $$4$$ or more ways.

For $$1 \bmod 4$$ we have $$9, 25, 9+36, 49$$ so we can express any number $$49$$ or greater in $$4$$ or more ways.

For $$2 \bmod 4$$ we have $$9+25, 9+49, 9+36+49, 25+49$$ so we can express any number $$74$$ or greater in $$4$$ or more ways.

For $$3 \bmod 4$$ we have $$27, 27+36, 9+25+49, 9+25+36+49$$ so we can express any number $$119$$ or greater in $$4$$ or more ways.

The greatest number in $$T$$ is $$115$$, which can be expressed as $$64+27+16+8, 36+32+27+16+4, 49+32+25+9$$ but in no other ways.

• So this answer assumes that you can pick non-distinct elements? I guess this might be the question's intention, as someone noted that 34 can't be represented by picking distinct elements – Benjamin Wang Dec 14 '20 at 10:08
• No, it does not assume you can duplicate elements. You can get $34$ as $25+9$. I had thought there were gaps, but there are not. – Ross Millikan Dec 14 '20 at 14:07
• This problem was posted recently (possibly by OP) and then deleted. The solution there showed by induction that $f(n+4) \geq f(n)$ (while maintaining distinctness). The solution didn't find the largest element of $T$, and believed that it required checking enough small cases (as opposed to an insightful argument for why that's the largest possible, similar to showing 30 is the max). – Calvin Lin Dec 14 '20 at 15:43
• @CalvinLin: I have done it. I don't think it is too many cases to check. – Ross Millikan Dec 14 '20 at 20:10
• Nice. I don't think 0 is allowed to be used though, so for 0 mod 4 it looks like you will have to go up to 76 = 49+27. – Mike Dec 14 '20 at 20:37