Random article ( of 1101 ) Latest updates

User Tools

Site Tools


content / mathematics / sholz_conjecture

Wikenigma - an Encyclopedia of Unknowns Wikenigma - an Encyclopedia of the Unknown

The Scholz conjecture

The Scholz Conjecture relates the shortest length of an addition chain of Mersene numbers (ref.) to the shortest length of addition chains producing their exponents.

Stated formally as :

l(2n − 1) ≤ n − 1 + l(n),

where l(n) is the length of the shortest addition chain producing n.

Here, an addition chain is defined as a sequence of numbers, starting with 1, such that every number after the first can be expressed as a sum of two earlier numbers (which are allowed to both be equal). Its length is the number of sums needed to express all its numbers, which is one less than the length of the sequence of numbers (since there is no sum of previous numbers for the first number in the sequence, 1)."

Source : Wikipedia

Note that various 'weaker' versions of the conjecture have been proved. For example :

Brauer, Alfred (1939), "On addition chains" Bulletin of the American Mathematical Society, 45 (10): 736–739,

Agama,Theophilus (2022). "On the shortest addition chain of numbers of special forms" arXiv, mathematics, general mathematics, Mar. 2022.

Example chains have also been extensively investigated by computational methods. See: Clift, Neill Michael (2011). "Calculating optimal addition chains". Computing. 91 (3): 265–284.

But the full conjecture, as stated above, remains unproved.

THIS WEBSITE DOES NOT USE TRACKING, ADVERTISING, OR ANALYTICAL COOKIES OF ANY KIND.
All essential cookies (for login status etc) are automatically deleted at the end of the session.
(full details here)

Show another (random) article

Suggestions for corrections and ideas for articles are welcomed : Get in touch!


Further resources :