# 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.

Thanks for any help you can give.

• 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

## 1 Answer

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