A076142

[Pfoertner, Hugo]

-----Original Message-----
From: franktaw at netscape.net [mailto:franktaw at netscape.net] 
Sent: Monday, January 30, 2006 20:04
To: seqfan at ext.jussieu.fr
Subject: A076142


Here's another incorrect conjecture (although this one is at least marked as
a conjecture).  This basically states that a totally additive sequence
(A064097) which is always >= the length of the shortest addition chain
(A003313), never exceeds it by more than 1.  But if A064097(n)-A003313(n)=1,
A064097(n^2)-A003313(n^2)>=2.  Since the first non-zero term in A076142 is
a(23), at minimum a(529)>=2.  (More generally, it follows that A076142 is
unbounded.)

My question is, what is the smallest n such that A064097(n)>=2?  That way we
can replace the conjecture with the smallest counterexample.

Franklin T. Adams-Watters
16 W. Michigan Ave.
Palatine, IL 60067
847-776-7645

----------------------------------------------

Based on a preliminary table (extended version of
http://www.uni-bielefeld.de/~achim/add24.bits.gz ) of shortest addition
chain lengths provided by Neill Clift I computed the following results
related to A064097, A076091 and A076142. Can someone (Franklin?) fix the
wrong conjectures, formulas etc.?  My backlog currently is too big to do
this myself within the next few days.

Hugo Pfoertner

------------------------------------------------

The source code of my program can be found at
http://www.randomwalk.de/sequences/a064097.for
The program calls a subroutine "factor(n,m,f)" that computes the number of
prime factors m of n and puts them into f(1),f(2),...

Results:

Shortest addition chain lengths computed by Neill Clift.
Chain length table read until:    31070901


Records in A064097:
   1        2
   2        3
   3        5
   4        7
   5       11
   6       19
   7       23
   8       43
   9       47
  10       94
  11      139
  12      235
  13      283
  14      517
  15      659
  16     1081
  17     1319
  18     2209
  19     2879
  20     5758
  21     8637
  22    13301
  23    20147
  24    30337
  25    49727
  26    61993
  27   103823
  28   135313
  29   247439
  30   366683
  31   606743
  32   811879
  33  1266767
  34  1739761
  35  2913671
  36  3797401
  37  5827343
  38  8288641
  39 16577282
  40 22784407

  A064097: (OEIS values are correct)
 0 1 2 2 3 3 4 3 4 4 5 4 5 5 5 4 5 5 6 5 6 6 7 5 6 6 6 6 7 6 7
 5 7 6 7 6 7 7 7 6 7 7 8 7 7 8 9 6 8 7 7 7 8 7 8 7 8 8 9 7 8 8
 8 6 8 8 9 7 9 8 9 7 8 8 8 8 9 8 9 7 8 8 9 8 8 9 9 8 9 8 9 9 9
10 9 7 8 9 9 8

  Increasing length difference to shortest addition chain:
First occurrence
           n        diff      A064097(n)  A003313(n)
           1           0           0           0
          23           1           7           6
         129           2          10           8
         517           3          14          11
        2049           4          16          12
        4613           5          19          14
       33097           6          24          18
       33793           7          24          17
      135313           8          28          20
      794627           9          31          22
     3797401          10          36          26
     8288641          11          38          27

  A076091: 43 is missing in the OEIS:

   23   33   43   46   47   49   59   65   66   67   69   77   83   86   92
   94   98   99  107  115  118  121  130  131  132  133  134  138  139  141
  145  147  149  154  163  165  166  167  172  173  177  179  184  188  195
  196  197  198  199  201  203  207  209  211  213  214  215  217  227  229
  230  231  233  235  236  242  245  249  253  259  260  261  262  263  264
  265  266  268  269  273  276  277  278  281  282  290  293  294  295  297
  298  299  301  308  311  317  319  323  325  326

  Check B. Cloitre's conjecture if limit approaches c=16.
  A076091(n)*ln(n)/n: (examples for n=2^k and at end of Neill Clifft's data)
           2          33   11.4369284792391     
           4          46   15.9423851528787     
           8          65   16.8954625261487     
          16          94   16.2889587431587     
          32         147   15.9207243034862     
          64         235   15.2708988217113     
         128         392   14.8593426832538     
         256         662   14.3394822978339     
         512        1188   14.4748626065370     
        1024        2270   15.3656650378035     
        2048        4518   16.8203264548184     
        4096        9492   19.2754483531494     
        8192       21398   23.5370512457376     
       16384       52623   31.1680161838674     
       32768      138216   43.8556048774445     
       65536      392440   66.4108104343127     
      131072     1227324   110.337638046039     
      262144     4192313   199.531627073465     
      524288    15426332   387.500099394706     
      747558    31070208   562.111722677853     
      747559    31070212   562.111098712112     
      747560    31070224   562.110619480922     
      747561    31070272   562.110791548420     
      747562    31070429   562.112935597016     
      747563    31070464   562.112872471187     
      747564    31070528   562.113333999896     
      747565    31070552   562.113071867292     
      747566    31070602   562.113280113970     
      747567    31070676   562.113922555259

Obviously the conjectured limit 16 is rather temporary.

This nicely illustrates Don Knuth's remark on the validity of conjectures
related to addition chains.