Scholz conjecture: Difference between revisions
Content deleted Content added
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
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 |
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''(2<sup>''n''</sup> − 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.<ref name=Clift>{{cite journal |first=Neill Michael |last=Clift |year=2011 |title=Calculating optimal addition chains |journal=Computing |volume=91 |issue=3 |pages=265–284 |doi=10.1007/s00607-010-0118-8 |url=http://link.springer.com/content/pdf/10.1007%2Fs00607-010-0118-8.pdf}} |
:''l''(2<sup>''n''</sup> − 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.<ref name=Clift>{{cite journal |first=Neill Michael |last=Clift |year=2011 |title=Calculating optimal addition chains |journal=Computing |volume=91 |issue=3 |pages=265–284 |doi=10.1007/s00607-010-0118-8 |url=http://link.springer.com/content/pdf/10.1007%2Fs00607-010-0118-8.pdf}}</ref> |
||
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 |
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 |
||
Revision as of 08:35, 4 September 2014
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(25−1) = 5 − 1 + l(5).
References
- Scholz, Arnold (1937), "Aufgaben und Lösungen, 253", Jahresbericht der Deutschen Mathematiker-Vereinigung, 47: 41–42, ISSN 0012-0456
- Brauer, Alfred (1939), "On addition chains", Bulletin of the American Mathematical Society, 45 (10): 736–739, doi:10.1090/S0002-9904-1939-07068-7, ISSN 0002-9904, Zbl 0022.11106, MR0000245
- Guy, Richard K. (2004). Unsolved problems in number theory (3rd ed.). Springer-Verlag. pp. 169–171. ISBN 978-0-387-20860-2. Zbl 1058.11001.
External links
- ^ Clift, Neill Michael (2011). "Calculating optimal addition chains" (PDF). Computing. 91 (3): 265–284. doi:10.1007/s00607-010-0118-8.