Open AccessPrime Decompositions with Minimum Sum
Author(s) -
Ole Østerby
Publication year - 1973
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v2i19.6438
Subject(s) - combinatorics , integer (computer science) , mathematics , prime (order theory) , connection (principal bundle) , function (biology) , discrete mathematics , computer science , geometry , evolutionary biology , biology , programming language
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.