Prime Decompositions with Minimum Sum

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.