Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952338 | Theoretical Computer Science | 2016 | 22 Pages |
Abstract
Define ânâ to be the complexity of n, the smallest number of ones needed to write n using an arbitrary combination of addition and multiplication. John Selfridge showed that ânââ¥3log3â¡n for all n. Based on this, this author and Zelinsky defined [4] the “defect” of n, δ(n):=ânââ3log3â¡n, and this author showed that the set of all defects is a well-ordered subset of the real numbers [1]. This was accomplished by showing that for a fixed real number s, there is a finite set S of polynomials called “low-defect polynomials” such that for any n with δ(n)
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Harry Altman,