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

TitleAn algorithmic approach to some problems on the representation of natural numbers as sums without repetitions
Publication TypeJournal Article
Year of Publication1997
AuthorsSkordev D
JournalAnnuaire de l’Université de Sofia “St. Kliment Ohridski”. Faculté de Mathématiques et Informatique
Volume89
IssueLivre 1 - Mathématiques et Mecanique
Pagination89-99
ISSN0205-0808
Keywordsalgorithm, representability of natural numbers, sums of distinct positive cubes, sums of distinct squares, 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.

1991/95 MSC

11-04, 11B13, 11E25

AttachmentSize
PDF icon 89-089-099.pdf1.15 MB