# Representing natural numbers as sums of powers of distinct numbers

Find the smallest number $$n$$ such that almost all natural numbers can be represented as the sum $$a_1^{a_{p(1)}}+a_2^{a_{p(2)}}+\dots+a_n^{a_{p(n)}}$$where $$a_1,\dots,a_n$$ are pairwise distinct natural numbers and $$p$$ is a permutation of the set $$\{1,\dots,n\}$$.

The problem was posed on 24.03.2019 by Jacek Jurewicz on page 95 of Volume 2 of the Lviv Scottish Book.

The prize: A personal congratulation :)

• N=2. This works for numbers greater than N. (Hint: a_1=1.) Gerhard "You Can Congratulate Me Here" Paseman, 2019.08.23. – Gerhard Paseman Aug 23 '19 at 17:11
• @GerhardPaseman Could you please write more details of your solution, desirably as an answer? Thank you. – Lviv Scottish Book Aug 23 '19 at 17:14

One can represent N+1 as N^1 + 1^N. There does not seem to be a representation of 2 without using 0 and three or more terms. 1 (and some other powers) needs only one term.

The problem needs major alteration to be suitable for this forum.

Gerhard "More Simple Thinking Was Needed" Paseman, 2019.08.23.

• Yes, you are right. In its present form the problem is too simple. Maybe using 1 should be forbidden? I will write to the author of the problem and ask for a comment. – Lviv Scottish Book Aug 23 '19 at 18:13
• When p is a derangement, an interesting question is the density of such numbers, even for n fixed. I suspect the density is zero, and is "smaller" than any image of the integers under any fixed degree nontrivial polynomial. Gerhard "Ask About That, With Attribution" Paseman, 2019.08.23. – Gerhard Paseman Aug 23 '19 at 18:40
• Congratulations!!! :) Truth be told, when I visited the Scottish Cafe, I didn't expect that one could add new problems to the Scottish Book, but I couldn't pass up the opportunity, so I came up with this one while having dessert. It's nice to see it getting translated to English and catching some attention. I'm happy to be part of the tradition of the Scottish Book. It also seems to me that it could be made more interesting by adding the constraint that all a[i] > 1. – Jacek Jurewicz Aug 25 '19 at 14:54
• Thank you. It seems that for n greater than 2, such an expression is greater than med1^med2, where these are equal for n odd and represent the median of the set, and otherwise are the two ends of the median. For a fixed set, the distribution of values seems quite sparse. If 1 is not allowed, my guess is there is no such n, as the set of values has density zero (even including nonderangements). Gerhard "Might Start Bronco Billy's Book" Paseman, 2019.08.25. – Gerhard Paseman Aug 25 '19 at 15:48