110:
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
373:
111:
length of the sequence of numbers (since there is no sum of previous numbers for the first number in the sequence, 1). Computing the length of the shortest addition chain that contains a given number
292:
408:
459:
659:
527:
232:
equal 7. Therefore, these values obey the inequality (which in this case is an equality) and the Scholz conjecture is true for the case
297:
606:
247:
By using a combination of computer search techniques and mathematical characterizations of optimal addition chains,
649:
124:
654:
116:
54:
Neill Clift has announced an example showing that the bound of the conjecture is not always tight.
271:
523:
478:
440:
629:
428:
378:
564:
533:
494:
468:
490:
537:
519:
498:
486:
136:
120:
511:
100:
32:
643:
48:
44:
473:
607:"A Counter-Example that the Scholz-Brauer Conjecture holds with Equality for all n"
585:
131:. Scholz's conjecture, if true, would provide short addition chains for numbers
20:
268:
The bound of the conjecture is not always an exact equality. For instance, for
569:
552:
28:
482:
444:
119:
for small numbers, but it is not known whether it can be done in
265:, the inequality of the conjecture is actually an equality.
634:
368:{\displaystyle l(2^{n}-1)\leq 9307570<9307571=n-1+l(n)}
51:
who studied it soon afterward and proved a weaker bound.
381:
300:
274:
433:
Jahresbericht der
Deutschen Mathematiker-Vereinigung
402:
367:
286:
586:"Exact Equality in the Scholz-Brauer Conjecture"
191:of length seven, determined by the seven sums
162:of length three, determined by the three sums
460:Bulletin of the American Mathematical Society
457:Brauer, Alfred (1939), "On addition chains",
8:
123:measured as a function of the length of the
251:showed that the conjecture is true for all
568:
472:
380:
311:
299:
273:
258:. Additionally, he verified that for all
419:
553:"Calculating optimal addition chains"
248:
7:
70:(2 − 1) ≤
183:: it has a shortest addition chain
154:: it has a shortest addition chain
660:Unsolved problems in number theory
516:Unsolved problems in number theory
35:. It is sometimes also called the
14:
74: − 1 +
605:Flammenkamp, Achim (July 2024).
474:10.1090/S0002-9904-1939-07068-7
391:
385:
362:
356:
323:
304:
99:is the length of the shortest
47:who formulated it in 1937 and
1:
551:Clift, Neill Michael (2011).
429:"Aufgaben und Lösungen, 253"
62:The conjecture states that
676:
584:Clift, Neill (July 2024).
187:1, 2, 3, 6, 12, 24, 30, 31
570:10.1007/s00607-010-0118-8
287:{\displaystyle n=9307543}
31:on the length of certain
630:Shortest addition chains
41:Brauer–Scholz conjecture
37:Scholz–Brauer conjecture
427:Scholz, Arnold (1937),
403:{\displaystyle l(n)=29}
135:of a special form, the
404:
369:
288:
635:OEIS sequence A003313
405:
370:
289:
125:binary representation
522:. pp. 169–171.
379:
298:
272:
117:dynamic programming
400:
365:
284:
181:(31) = 7
529:978-0-387-20860-2
152:(5) = 3
25:Scholz conjecture
667:
617:
616:
614:
613:
602:
596:
595:
593:
592:
581:
575:
574:
572:
548:
542:
541:
518:(3rd ed.).
508:
502:
501:
476:
454:
448:
447:
424:
409:
407:
406:
401:
374:
372:
371:
366:
316:
315:
293:
291:
290:
285:
264:
257:
238:
231:
223:
182:
153:
137:Mersenne numbers
134:
130:
114:
98:
83:
675:
674:
670:
669:
668:
666:
665:
664:
650:Addition chains
640:
639:
626:
621:
620:
611:
609:
604:
603:
599:
590:
588:
583:
582:
578:
550:
549:
545:
530:
520:Springer-Verlag
512:Guy, Richard K.
510:
509:
505:
467:(10): 736–739,
456:
455:
451:
426:
425:
421:
416:
377:
376:
307:
296:
295:
270:
269:
259:
252:
245:
243:Partial results
233:
225:
218:
177:
148:
147:As an example,
145:
132:
128:
121:polynomial time
115:can be done by
112:
89:
66:
60:
33:addition chains
17:
12:
11:
5:
673:
671:
663:
662:
657:
652:
642:
641:
638:
637:
632:
625:
624:External links
622:
619:
618:
597:
576:
563:(3): 265–284.
543:
528:
503:
449:
418:
417:
415:
412:
399:
396:
393:
390:
387:
384:
364:
361:
358:
355:
352:
349:
346:
343:
340:
337:
334:
331:
328:
325:
322:
319:
314:
310:
306:
303:
283:
280:
277:
244:
241:
226:5 − 1 +
215:
214:
211:
208:
205:
202:
199:
196:
189:
188:
174:
173:
170:
167:
160:
159:
144:
141:
101:addition chain
86:
85:
59:
56:
15:
13:
10:
9:
6:
4:
3:
2:
672:
661:
658:
656:
653:
651:
648:
647:
645:
636:
633:
631:
628:
627:
623:
608:
601:
598:
587:
580:
577:
571:
566:
562:
558:
554:
547:
544:
539:
535:
531:
525:
521:
517:
513:
507:
504:
500:
496:
492:
488:
484:
480:
475:
470:
466:
462:
461:
453:
450:
446:
442:
438:
434:
430:
423:
420:
413:
411:
397:
394:
388:
382:
359:
353:
350:
347:
344:
341:
338:
335:
332:
329:
326:
320:
317:
312:
308:
301:
281:
278:
275:
266:
262:
255:
250:
242:
240:
236:
229:
221:
212:
209:
207:12 + 12 = 24,
206:
203:
200:
197:
194:
193:
192:
186:
185:
184:
180:
171:
168:
165:
164:
163:
157:
156:
155:
151:
142:
140:
138:
126:
122:
118:
108:
106:
102:
96:
92:
81:
77:
73:
69:
65:
64:
63:
57:
55:
52:
50:
49:Alfred Brauer
46:
45:Arnold Scholz
42:
38:
34:
30:
26:
22:
610:. Retrieved
600:
589:. Retrieved
579:
560:
556:
546:
515:
506:
464:
458:
452:
436:
432:
422:
267:
260:
256:< 5784689
253:
249:Clift (2011)
246:
234:
227:
219:
216:
213:30 + 1 = 31.
210:24 + 6 = 30,
190:
178:
175:
161:
149:
146:
109:
104:
94:
90:
87:
79:
75:
71:
67:
61:
53:
40:
36:
24:
18:
655:Conjectures
204:6 + 6 = 12,
21:mathematics
644:Categories
612:2024-07-20
591:2024-07-20
538:1058.11001
499:0022.11106
414:References
201:3 + 3 = 6,
198:2 + 1 = 3,
195:1 + 1 = 2,
172:4 + 1 = 5.
169:2 + 2 = 4,
166:1 + 1 = 2,
158:1, 2, 4, 5
103:producing
29:conjecture
16:Conjecture
557:Computing
483:0002-9904
445:0012-0456
439:: 41–42,
345:−
327:≤
318:−
58:Statement
514:(2004).
43:, after
491:0000245
375:, with
336:9307571
330:9307570
282:9307543
143:Example
39:or the
536:
526:
497:
489:
481:
443:
176:Also,
88:where
23:, the
217:Both
27:is a
524:ISBN
479:ISSN
441:ISSN
333:<
263:≤ 64
224:and
222:(31)
565:doi
534:Zbl
495:Zbl
469:doi
237:= 5
230:(5)
127:of
19:In
646::
561:91
559:.
555:.
532:.
493:,
487:MR
485:,
477:,
465:45
463:,
437:47
435:,
431:,
410:.
398:29
294:,
239:.
139:.
107:.
615:.
594:.
573:.
567::
540:.
471::
395:=
392:)
389:n
386:(
383:l
363:)
360:n
357:(
354:l
351:+
348:1
342:n
339:=
324:)
321:1
313:n
309:2
305:(
302:l
279:=
276:n
261:n
254:n
235:n
228:l
220:l
179:l
150:l
133:x
129:x
113:x
105:n
97:)
95:n
93:(
91:l
84:,
82:)
80:n
78:(
76:l
72:n
68:l
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.