An algorithmic approach to some problems on the representation of natural numbers as sums without repetitions

Abstract

Given any strictly increasing computable function in the set of natural numbers, certain algorithmic problems arise on the representation of numbers as sums of distinct values of the function. The problem whether a given natural number is representable in this form is obviously algorithmically solvable, but we propose some methods for the solution of the problem that seem to be better than the straightforward ones.

It is easy to see the algorithmic unsolvability of the problem whether all natural numbers are representable (under the usual assumption that an index of the given computable function is used as input data). However, under an appropriate restriction concerning, roughly speaking, the speed of the growth of the function, we present an algorithm for solving this problem and the more general one whether all natural numbers greater than a given one are representable (the restriction is satisfied, for example, when the given function is a polynomial).

We make applications of the presented positive results to concrete problems concerning, for instance, the representation as sums of distinct squares or as sums of distinct positive cubes.