Submit web site - 4.6.3 EVALUATION OF POWERS 459 Table 1 VALUES
4.6.3 EVALUATION OF POWERS 459 Table 1 VALUES OF n FOR SPECIAL ADDITION CHAINS 23 163 229 319 371 413 453 553 599 645 707 741 813 849 903 43 165 233 323 373 419 455 557 611 659 709 749 825 863 905 59 179 281 347 377 421 457 561 619 667 711 759 835 869 923 77 203 283 349 381 423 479 569 623 669 713 779 837 887 941 83 211 293 355 382 429 503 571 631 677 715 787 839 893 947 107 213 311 359 395 437 509 573 637 683 717 803 841 899 955 149 227 317 367 403 451 551 581 643 691 739 809 845 901 983 Let d(r) be the number of solutions n to the equation l(n) = T. The following table lists the first few values of this function: 1 1 6 15 11 246 2 2 7 26 12 432 3 3 8 44 13 772 4 5 9 78 14 1382 5 9 10 136 15 2481 Surely d(r) must be an increasing function of r, but there is no evident way to prove this seemingly simple assertion, much less to determine the asymptotic growth of d(r) for large r. The most famous problem about addition chains that is still outstanding is the Schola-Brauer conjecture, which states that l(2 -1) 2 n -1+ l(n). (49) Computer calculations show, in fact, that equality holds in (49) for 1 < n < 14; and hand calculations by E. G. Thurber [Discrete Math. 16 (1976), 279-2891 have shown that equality holds also for n = 15, 16, 17, 18, 20, 24, 32. Much of the research on addition chains has been devoted to attempts to prove (49); addition chains for the number 2n -1, which has so many ones in its binary representation, are of special interest, since this is the worst case for the binary method. Arnold Scholz coined the name addition chain (in German) and posed (49) as a problem in 1937 [Jahresbericht der deutschen Mathematiker- Vereinigung, class II, 47 (1937), 41-421; Alfred Brauer proved in 1939 that 1*(2n -1) 5 n -1 + l*(n). (50) Hansen s theorems show that l(n) can be less than l*(n), so more work is definitely necessary in order to prove or disprove (49). As a step in this direction, Hansen has defined the concept of an lo-chain, which lies between l-chains and l*-chains. In an lo-chain, certain of the elements are underlined; the condition is that ai = a? + uk, where a3 is the largest underlined element less t,han a,.