Prime Decompositions with Minimum Sum

Abstract

During the January 1972 meeting in Aarhus on Automata Theory (see e.g. PB-15) a number-theoretic problem was posed in connection with determining the size of a language generated by a DOL-System (Deterministic Lindenmayer-System with no interaction between neighbours).

The problem as posed by Paul Vitanyi is:

Find an algorithm which for every integer n>O yields a number of pair wise relative primes k_1 ,k_2,... ,k_m and a non-negative integer r such that n = k_l € k_2 . . . k_m + r and such that k_1 + k_2 + ... + k_m + r is minimal.

In the paper an efficient alsorithm for this and a reiated problem is presented, and various tables and graphs indicating the behaviour of the minimal sum as a function of n are given.