Scholz conjecture

In mathematics, the Scholz conjecture sometimes called the Scholz–Brauer conjecture or the Brauer–Scholz conjecture (named after A. Scholz and Alfred T. Brauer), is a conjecture from 1937 stating that

l(2n  1)  n  1 + l(n) where l(n) is the length of the shortest addition chain producing n. N. Clift checked this by computer for n  64.[1]

As an example, l(5) = 3 (since 1 + 1 = 2, 2 + 2 = 4, 4 + 1 = 5, and there is no shorter chain) and l(31) = 7 (since 1 + 1 = 2, 2 + 1 = 3, 3 + 3 = 6, 6 + 6 = 12, 12 + 12 = 24, 24 + 6 = 30, 30 + 1 = 31, and there is no shorter chain), so

l(251) = 5  1 + l(5).

References

  1. Clift, Neill Michael (2011). "Calculating optimal addition chains". Computing 91 (3): 265–284. doi:10.1007/s00607-010-0118-8.

External links