A114622 -id:A114622 - cp's OEIS frontend

A115617 Smallest number for which Knuth's power tree method produces an addition chain of length n.

1, 2, 3, 5, 7, 11, 19, 29, 47, 71, 127, 191, 319, 551, 1007, 1711, 2687, 4703, 8447, 15179, 28079, 45997, 89599, 138959, 257513, 485657, 834557, 1433501, 2854189, 4726127, 8814047, 15692153, 30078877, 53574623, 94189807, 177848059, 322928189

Offset: 0

Hugo Pfoertner, Jan 29 2006

Minimum number in row of power tree A114622. The first 12 terms are identical with A003064.

Smallest k such that A383329(k) = n. - Pontus von Brömssen, Apr 24 2025

Cf. A114622 (the power tree (as defined by Knuth)), A003064 (smallest number with addition chain of length n), A113945 (numbers such that Knuth's power tree method produces a result deficient by 1).

Indices of records in A383329.

a(28)-a(32) from Hugo Pfoertner, Sep 05 2015
a(33) from Hugo Pfoertner, Oct 01 2015
a(34)-a(36) from Michael S. Branicky, Apr 30 2024
a(0) from Pontus von Brömssen, Apr 24 2025

A383329 Number of multiplications required to compute x^n by Knuth's power tree method.

Original entry on oeis.org

0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5, 5, 6, 5, 6, 6, 6, 5, 6, 6, 6, 6, 7, 6, 7, 5, 6, 6, 7, 6, 7, 7, 7, 6, 7, 7, 7, 7, 7, 7, 8, 6, 7, 7, 7, 7, 8, 7, 8, 7, 8, 8, 8, 7, 8, 8, 8, 6, 7, 7, 8, 7, 8, 8, 9, 7, 8, 8, 8, 8, 9, 8, 9, 7, 8, 8, 8, 8, 8, 8, 9

Offset: 1

Pontus von Brömssen, Apr 24 2025

nonn

n appears in row a(n)+1 of A114622.
n appears A114623(n+1) times.
First differs from A003313 at n = 77.

Donald E. Knuth, The Art of Computer Programming, Vol. 2, 3rd edition, Addison-Wesley, 1998. See page 464.

Pontus von Brömssen, Table of n, a(n) for n = 1..10000

Cf. A003313, A113945, A114622, A114623, A115617 (indices of records), A122352.

a(n) = a(A122352(n)) + 1 for n >= 2.

a(A115617(k)) = k and a(n) < k for n < A115617(k).

A370386 Irregular triangle read by rows. An infinite rooted tree having root node 1 in row n = 0. Nodes in row n each have n + 1 children with values m + k, where m is the value of the parent node and k takes the values of all nodes from the root to the parent including the parent itself.

Original entry on oeis.org

1, 2, 3, 4, 4, 5, 6, 5, 6, 8, 5, 6, 7, 8, 6, 7, 8, 10, 7, 8, 9, 12, 6, 7, 9, 10, 7, 8, 10, 12, 9, 10, 12, 16, 6, 7, 8, 9, 10, 7, 8, 9, 10, 12, 8, 9, 10, 11, 14, 9, 10, 11, 12, 16, 7, 8, 9, 11, 12, 8, 9, 10, 12, 14, 9, 10, 11, 13, 16, 11, 12, 13, 15, 20, 8, 9

Offset: 0

John Tyler Rascoe, Feb 28 2024

The paths through the tree represent integer partitions which contain their own first differences and have least part 1. These partitions are counted, including those with any least part, in A364673.

			Triangle begins:
  1;
  2;
  3, 4;
  4, 5, 6, 5, 6, 8;
  5, 6, 7, 8, 6, 7, 8, 10, 7, 8, 9, 12, 6, 7, 9, 10, 7, 8, 10, 12, 9, 10, 12, 16;
  ...
The tree starts with root 1 in row n = 0. In row n = 2 the parent node 4 has 3 children using values of k: 1, 2, and 4.
Tree begins:
  row
  [n]
  [0]             1
                  |
  [1]         ____2____
             /         \
  [2]     __3__       __4__
         /  |  \     /  |  \
  [3]   4   5   6   5   6   8

The tree if only distinct values are allowed is A114622.
Cf. A000142 (row lengths), A002720 (empirical row sums).
Cf. A364673.

def A370386_rowlist(maxrow):
    A,C = [[(1,)]],[[1]]
    for i in range(maxrow):
        A.append([])
        C.append([])
        for j in A[i]:
            for k in j:
                x = j + (j[-1] + k,)
                A[i+1].append(x)
                C[i+1].append(x[-1])
    return(C)

cp's OEIS Frontend

A115617 Smallest number for which Knuth's power tree method produces an addition chain of length n.

Views

Author

Keywords

Comments

Crossrefs

Extensions

A383329 Number of multiplications required to compute x^n by Knuth's power tree method.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

A370386 Irregular triangle read by rows. An infinite rooted tree having root node 1 in row n = 0. Nodes in row n each have n + 1 children with values m + k, where m is the value of the parent node and k takes the values of all nodes from the root to the parent including the parent itself.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python