A003313 -id:A003313 - cp's OEIS frontend

A056792 Minimal number of steps to get from 0 to n by (a) adding 1 or (b) multiplying by 2.

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

Offset: 0

N. J. A. Sloane, Sep 01 2000

A stopping problem: begin with n and at each stage if even divide by 2 or if odd subtract 1. That is, iterate A029578 while nonzero.
From Peter Kagey, Jul 16 2015: (Start)
The number of appearances of n in this sequence is identically A000045(n). Proof:
By application of the formula,
  "a(0) = 0, a(2*n+1) = a(2*n) + 1 and a(2*n) = a(n) + 1",
it can be seen that:
  {i: a(i) = n} = {2*i: a(i) = n-1, n>0} U {2*i+1: a(i) = n-2, n>1}.
Because the two sets on the left hand side share no elements:
  |{i: a(i) = n}| = |{i: a(i) = n-1, n>0}| + |{i: a(i) = n-2, n>1}|
Notice that
  |{i : a(i) = 1}| = |{1}| = 1 = A000045(1) and
  |{i : a(i) = 2}| = |{2}| = 1 = A000045(2).
Therefore the number of appearances of n in this sequence is A000045(n). (End)

			12 = 1100 in binary, so a(12)=2+4-1=5.

Charles R Greathouse IV, Table of n, a(n) for n = 0..10000
Hugo Pfoertner, Addition chains
Index to sequences related to the complexity of n

Equals A056791 - 1. The least inverse (indices of record values) of A056792 is A052955 prepended with 0. See also A014701, A115954, A056796, A056817.
Cf. A000120, A070939, A007088: base 2 sequences.
Analogous sequences with a different multiplier k: A061282 (k=3), A260112 (k=4).

c i = if i `mod` 2 == 0 then i `div` 2 else i - 1
b 0 foldCount = foldCount
b sheetCount foldCount = b (c sheetCount) (foldCount + 1)
a056792 n = b n 0 -- Peter Kagey, Sep 02 2015

a:= n-> (l-> nops(l)+add(i, i=l)-1)(convert(n, base, 2)):
seq(a(n), n=0..105);  # Alois P. Heinz, Jul 16 2015

f[ n_Integer ] := (c = 0; k = n; While[ k != 0, If[ EvenQ[ k ], k /= 2, k-- ]; c++ ]; c); Table[ f[ n ], {n, 0, 100} ]
f[n_] := Floor@ Log2@ n + DigitCount[n, 2, 1]; Array[f, 100] (* Robert G. Wilson v, Jul 31 2012 *)

a(n)=if(n<1,0,n-valuation(n!*sum(i=1,n,1/i),2))

PARI
```
a(n)=if(n<1,0,1+a(if(n%2,n-1,n/2)))
```

a(n)=if(n<1,0,n=binary(n);sum(i=1,#n,n[i])+#n-1) \\ Charles R Greathouse IV, Apr 11 2012

a(0) = 0, a(2*n+1) = a(2*n) + 1 and a(2*n) = a(n) + 1.
a(n) = n-valuation(A000254(n), 2) for n>0. - Benoit Cloitre, Mar 09 2004
a(n) = A000120(n) + A070939(n) - 1. - Michel Marcus, Jul 17 2015
a(n) = (weight of binary expansion of n) + (length of binary expansion of n) - 1.

More terms from James Sellers, Sep 06 2000

More terms from David W. Wilson, Sep 07 2000

A173419 Length of shortest computation yielding n using addition, subtraction and multiplication (starting from 1).

Original entry on oeis.org

0, 1, 2, 2, 3, 3, 4, 3, 3, 4, 4, 4, 5, 4, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 4, 5, 4, 5, 5, 5, 5, 4, 5, 5, 5, 4, 5, 5, 5, 5, 6, 5, 6, 6, 5, 6, 6, 5, 5, 5, 6, 6, 6, 5, 6, 5, 6, 6, 6, 5, 6, 5, 5, 4, 5, 5, 6, 5, 6, 6, 6, 5, 6, 6, 5, 6, 6, 5, 5, 5, 4, 5, 5, 5, 6, 6, 6, 6, 6, 5, 6, 6, 6, 6, 6, 5, 6, 6, 5, 5, 6, 6, 6, 6, 6, 6, 6, 5

Offset: 1

Charles R Greathouse IV, Feb 17 2010, Apr 22 2010

Let x_0 = 1 and x_m = n, with each x_k = x_i + x_j, x_k = x_i * x_j, or x_k = x_i - x_j for some 0 <= i,j < k. a(n) is the least such m.
Shub & Smale ask if there is a c such that a(n!) <= (log n)^c for all n.
If for any sequence of nonzero integers (m_i) there is no constant c such that a(n! * m_n) <= (log n)^c, then "the Hilbert Nullstellensatz is intractable, and consequently the algebraic version of 'NP != P' is true" (Shub & Smale).
Conjecture: if n is prime then a(n) >= a(n-1). The conjecture is true for n < 1800. - Dmitry Kamenetsky, Dec 26 2019

			For n = 9, one sequence is (1, 1 + 1 = 2, 1 + 2 = 3, 3 * 3 = 9). Since no shorter sequence is possible, a(9) = 3.
For n = 96, one sequence is (1, 1 + 1 = 2, 2 + 2 = 4, 2 + 4 = 6, 4*4 = 16, 6*16 = 96); no shorter is possible so a(96) = 5.

R. K. Guy, Unsolved Problems Number Theory, Sect. F26.

Alois P. Heinz, Table of n, a(n) for n = 1..1800
Peter Borwein and Joe Hobart, The extraordinary power of division in straight line programs, American Mathematical Monthly 119:7 (2012), pp. 584-592.
F. Cucker, M. Shub, and S. Smale, Separation of Complexity classes in Koiran's weak model, Theoretical Computer Science 133:1 (1994), pp. 3-14.
W. DeMelo and B. F. Svaiter, The cost of computing integers, Proc. Amer. Math. Soc. 124 (1996), pp. 1377-1378.
P. Koiran, Valiant's model and the cost of computing integers, Comput. Complex. 13 (2004), pp. 131-146.
Carlos Gustavo T. de A. Moreira, On asymptotic estimates for arithmetic cost functions, Proceedings of the American Mathematical Society 125:2 (1997), pp. 347-353.
Richard J. Mathar, Extended list of chain examples
Michael Shub and Steve Smale, On the intractability of Hilbert's Nullstellensatz and an algebraic version of "NP = P", Duke Mathematical Journal 81:1 (1995), pp. 47-54.
Al Zimmermann's Programming Contests, Factorials
Index to sequences related to the complexity of n

Records are essentially A141414.

Cf. A003313 (shortest chain using just addition), A005245 (number of 1s using just addition and multiplication), A217032(n):=A173419(n!).

g:= f->seq(f union {t}, t={seq(seq({i+j, i-j, i*j}[], j=f), i=f)} minus f):
F:= proc(n) F(n):= map(g, F(n-1)) end: F(0):= {{1}}:
S:= proc(n) S(n):= map(x->x[], F(n)) end:
a:= proc(n) local k; for k from 0 while not(n in S(k)) do od; k end:
seq(a(n), n=1..110);  # Alois P. Heinz, Sep 24 2012

a(n) <= 2 log_2(n).
a(n) >= log_2(log_2(n)) + 1.
a(n) >= log_2(n)/log_2(log_2(n)) for almost all n, as proved by Moreira (improving DeMelo & Svaiter).
a(n) <= A005245(n) <= A003313(n) <= A014701(n) <= 2*A000523(n). - Charles R Greathouse IV, Feb 07 2022

A003064 a(n) = smallest number with shortest addition chain of length n.

Original entry on oeis.org

1, 2, 3, 5, 7, 11, 19, 29, 47, 71, 127, 191, 379, 607, 1087, 1903, 3583, 6271, 11231, 18287, 34303, 65131, 110591, 196591, 357887, 685951, 1176431, 2211837, 4169527, 7624319, 14143037, 25450463, 46444543, 89209343, 155691199, 298695487, 550040063, 994660991

Offset: 0

N. J. A. Sloane and Don Knuth

An addition chain of length n for a number a is a sequence 1 = a_0, a_1,..., a_n = a such that for each i>0, a_i is the sum of two (not necessarily distinct) elements of the sequence. - Glen Whitney, Nov 09 2021
The largest number with an addition chain of length n is 2^n. This chain is of course shortest for 2^n. - Franklin T. Adams-Watters, Jan 20 2016
The step from a_{i-1} to a_i is called "small" if a_i is less than the smallest power of two greater than a_{i-1}. The sequence b(n) of the smallest number which requires n small steps in an addition chain is a subsequence of this sequence, starting a(0), a(2), a(4), a(7), a(10), a(15), a(21), a(28), a(37), a(46),... - Glen Whitney, Nov 09 2021

			a(7) = 29 because 29 is the smallest number with a shortest addition chain requiring 7 additions. An example of a shortest addition chain for 29 is (1 2 3 4 7 11 18 29).

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 2, p. 458; Vol. 2, 3rd. ed., p. 477.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
See A003313 for a much more extensive list of references and links.

Glen Whitney, Table of n, a(n) for n = 0..46 (Terms 0..41 from R. J. Mathar)
Daniel Bleichenbacher, Efficiency and Security of Cryptosystems based on Number Theory, PhD Thesis, Diss. ETH No. 11404, Zürich 1996. See p. 60.
Swee Hong Chan and Igor Pak, Computational complexity of counting coincidences, arXiv:2308.10214 [math.CO], 2023. See p. 10.
M. Elia and F. Neri, A note on addition chains and some related conjectures, pp. 166-181 of R. M. Capocelli, ed., Sequences, Springer-Verlag, NY 1990. The smallest number with an addition chain of length n is denoted c(n) in this paper.
Achim Flammenkamp, Shortest addition chains
D. Knuth, Letter to N. J. A. Sloane, date unknown
Index to sequences related to the complexity of n

This is the "smallest inverse" of A003313. Cf. A003065.

Cf. A075530, A115617 [Smallest number for which Knuth's power tree method produces an addition chain of length n].

New terms from Achim Flammenkamp, Math. Diplomarbeit, Univ. Bielefeld, 1991; and from Daniel Bleichenbacher (bleichen(AT)inf.ethz.ch)
a(25)-a(27) from the 3rd. ed. of Knuth vol. 2, sent by David Moulton, Jun 24 2003
a(28)-a(30) from Achim Flammenkamp's web site, Feb 01 2005
a(31) computed Dec 15 2005 by Neill M. Clift. - Hugo Pfoertner, Jan 29 2006
a(32) from Neill M. Clift, Jun 15 2007
a(33)-a(34) from Neill M. Clift, May 21 2008
b-file up to a(41) extracted from Achim Flammenkamp's web site. - R. J. Mathar, May 14 2013
b-file updated to a(46) from Achim Flammenkamp's web site. - Glen Whitney, Nov 09 2021

A014701 Number of multiplications to compute n-th power by the Chandah-sutra method.

Original entry on oeis.org

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

Offset: 1

James Kilfiger (jamesk(AT)maths.warwick.ac.uk)

In other words, number of steps to reach 1 starting from n and using the process: x -> x-1 if n is odd and x -> x/2 otherwise.
a(n) = number of 0's + twice number of 1's (disregarding the leading digit 1) in the binary expansion of n, i.e., A007088(n). - Lekraj Beedassy, May 28 2010
From Daniel Forgues, Jul 31 2012: (Start)
For the binary Fibonacci rabbits sequence (A036299) (cf. OEIS Wiki link below) we have the substitution/concatenation rule: a(n), n >= 3, may be obtained by the concatenation of a(n-1) and a(n-2), with a(1) = 0, a(2) = 1. Thus, using . (dot) as the concatenation operator, we have the recursive substitution/concatenation
    a(n) = a(n-0)
    a(n) = a(n-1).a(n-2)
    a(n) = a(n-2).a(n-3).a(n-3).a(n-4)
    a(n) = a(n-3).a(n-4).a(n-4).a(n-5).a(n-4).a(n-5).a(n-5).a(n-6)
  which suggests the sequence
    {0}
    {1, 2}
    {2, 3, 3, 4}
    {3, 4, 4, 5, 4, 5, 5, 6}
  whose concatenation gives A014701 (this sequence).
Number of multiplications to compute n-th power by the Chandah-sutra method, also called left-to-right binary exponentiation:
  x^1 = x^(   1_2) =                                 (x)   (0 prod)
  x^2 = x^(  10_2) =                         (x^2)         (1 prod)
  x^3 = x^(  11_2) =                         (x^2) * (x)   (2 prod)
  x^4 = x^( 100_2) =               (x^2)^2                 (2 prod)
  x^5 = x^( 101_2) =               (x^2)^2         * (x)   (3 prod)
  x^6 = x^( 110_2) =               (x^2)^2 * (x^2)         (3 prod)
  x^7 = x^( 111_2) =               (x^2)^2 * (x^2) * (x)   (4 prod)
  x^8 = x^(1000_2) = ((x^2)^2)^2                           (3 prod) (End)
From Ya-Ping Lu, Mar 03 2021: (Start)
Index at which record m occurs is A052955(m).
First appearance of m in the sequence (or the record value m) is at n = 2^(m/2 + 1) - 1 for even m, and at n = 3*2^((m - 1)/2) - 1 for odd m.
The last appearance of m in the sequence is at n = 2^m. (End)
a(n) is the digit sum of n-1 in bijective base-2. Since the Fibonacci number F(m) can be defined as the number of ways to compose m as the sum of 1s and 2s, we get that m appears F(m) times in the sequence. - Oscar Cunningham, Apr 14 2024
Conjecture: a(n+1) is the minimal number of steps to go from 0 to n, by choosing before each step, after the first step, whether to keep the same step length or double it. The initial step length is 1. - Jean-Marc Rebert, May 15 2025

			5 -> 4 -> 2 -> 1 so 3 steps are needed to reach 1 hence a(5)=3; 9 -> 8 -> 4 -> 2 -> 1 hence a(9)=4.

Alois P. Heinz, Table of n, a(n) for n = 1..16384 (first 1000 terms from T. D. Noe)
Wawrzyniec Bieniawski, Piotr Masierak, Andrzej Tomski, and Szymon Łukaszyk, Assembly Theory - Formalizing Assembly Spaces and Discovering Patterns and Bounds, Preprints (2025).
C. K. Caldwell, The Prime Glossary, binary exponentiation
Hermann Gruber and Markus Holzer, Optimal Regular Expressions for Palindromes of Given Length, Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, Article No. 53, pp. 53:1-53:15, 2021.
J. Jordan and R. Southwell, Further Properties of Reproducing Graphs, Applied Mathematics, Vol. 1 No. 5, 2010, pp. 344-350. - From _N. J. A. Sloane_, Feb 03 2013
Szymon Łukaszyk and Wawrzyniec Bieniawski, Assembly Theory of Binary Messages (How to Assemble a Black Hole and Use it to Assemble New Binary Information?), Preprints (2024).
OEIS Wiki, Binary Fibonacci rabbits sequence
Index to sequences related to the complexity of n
Index entries for sequences related to binary expansion of n

Cf. A003313, A056791, A056792, A115964, A052955.

a014701 1 = 0
a014701 n = a007953 $ a007931 (n - 1)
-- Reinhard Zumkeller, Oct 26 2012

A014701 := proc(n) local j,k; j := n; k := 0; while(j>1) do if j mod 2=1 then j := j-1 else j := j/2 fi; k := k+1 od end;
# second Maple program:
a:= n-> add(i+1, i=Bits[Split](n))-2:
seq(a(n), n=1..128);  # Alois P. Heinz, Aug 30 2021

a[n_] := DigitCount[n, 2] /. {x_, y_} -> 2x + y - 2; Array[a, 100] (* Robert G. Wilson v, Jul 31 2012 *)

a(n)=hammingweight(n)+logint(n,2)-1 \\ Charles R Greathouse IV, Dec 29 2016

def a(n):
    if n==1:
        return 0
    return a(n//2)+1+n%2
for i in range(1,60):
    print(a(i), end=", ")
# Pablo Hueso Merino, Oct 28 2020

a(n) = A056792(n) - 1 = A056791(n) - 2.
a(n) = floor(log_2(n)) + (number of 1's in binary representation of n) - 1. - Corrected (- 1 at end) by Daniel Forgues, Aug 01 2012
a(2^n) = n, a(2^n-1) = 2*(n-1), and for n >= 2, log_2(n) <= a(n) <= 2*log_2(n) - 1. - Robert FERREOL, Oct 01 2014
Let u(1) = 1, u(2*n) = u(n)+1, u(2*n+1) = u(2*n)+1; then a(1) = 0 and a(n) = u(n-1). - Benoit Cloitre, Dec 19 2002
G.f.: -2/(1-x) + (1/(1-x)) * Sum_{k>=0} (2*x^2^k + x^2^(k+1))/(1+x^2^k). - Ralf Stephan, Aug 15 2003
From {0}, apply the substitution rule (n -> n+1, n+2) repeatedly, giving {{0}, {1, 2}, {2, 3, 3, 4}, {3, 4, 4, 5, 4, 5, 5, 6}, ...} and concatenate. - Daniel Forgues, Jul 31 2012
For n > 1: a(n) = A007953(A007931(n-1)). - Reinhard Zumkeller, Oct 26 2012
a(n) >= A003313(n). - Charles R Greathouse IV, Jan 03 2018
a(n) = a(floor(n/2)) + 1 + (n mod 2) for n > 1. - Pablo Hueso Merino, Oct 28 2020
a(n+1) = max_{1<=i<=n} (H(i) + H(n-i)) where H(n) denotes the Hamming weight of n (A000120(n)). See Lemma 8 in Gruber/Holzer 2021 article. - Hermann Gruber, Jun 26 2024

A114622 The power tree (as defined by Knuth), read by rows, where T(n,k) is the label of the k-th node in row n.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 8, 7, 10, 9, 12, 16, 14, 11, 13, 15, 20, 18, 24, 17, 32, 19, 21, 28, 22, 23, 26, 25, 30, 40, 27, 36, 48, 33, 34, 64, 38, 35, 42, 29, 31, 56, 44, 46, 39, 52, 50, 45, 60, 41, 43, 80, 54, 37, 72, 49, 51, 96, 66, 68, 65, 128

Offset: 1

Hugo Pfoertner and Paul D. Hanna, Dec 20 2005

The power tree is generated by a systematic method that is supposed to give the minimum number of multiplications to arrive at x^n.

The number of multiplications required to compute x^m by this method is n-1 if m appears in the n-th row. The smallest number m for which the power tree method does not give the minimum number of multiplications for x^m is m = 77 (see A113945, Knuth reference, or Pfoertner link "Addition chains"). The power tree method requires 9 multiplications for x^77 but A003313(77) = 8. - Pontus von Brömssen, Apr 23 2024

			The rows of the power tree begin:
  1;
  2;
  3,4;
  5,6,8;
  7,10,9,12,16;
  14,11,13,15,20,18,24,17,32;
  19,21,28,22,23,26,25,30,40,27,36,48,33,34,64;
  38,35,42,29,31,56,44,46,39,52,50,45,60,41,43,80,54,37,72,49,51,96,66,68,65,128;
where nodes are attached to each other as follows:
  1->[2];
  2->[3,4];
  3->[5,6], 4->[8];
  5->[7,10], 6->[9,12], 8->[16];
  7->[14], 10->[11,13,15,20], 9->[18], 12->[24], 16->[32];
  ...
E.g., the path from root node (1) to node (10) is [1,2,3,5,10], so the possible labels for nodes to be attached to node (10) are [10+1,10+2,10+3,10+5,10+10], but label (12) has already been used, so 4 nodes with labels [11,13,15,20] are attached to node (10).

D. E. Knuth, The Art of Computer Programming Third Edition. Vol. 2, Seminumerical Algorithms. Chapter 4.6.3 Evaluation of Powers, Page 464. Addison-Wesley, Reading, MA, 1997.

Alois P. Heinz, Rows n = 1..18, flattened
Hugo Pfoertner, Fortran program implementing Knuth's algorithm, from "Answers to exercises" for Section 4.6.3 page 692, exercise 5, page 481 TAOCP Vol. 2.
Hugo Pfoertner, Addition chains

Cf. A114623 (number of nodes in rows), A114624 (row sums), A114625 (leftmost node in rows).
See A122352 for another presentation of the tree.
Cf. A003313, A113945.

T:= proc(n) option remember; local i, j, l, s; l:= NULL;
      for i in [T(n-1)] do j:=i; s:=[];
        while j>0 do s:= [s[], j]; j:=b(j) od;
        for j in sort([s[]]) do
          if b(i+j)=0 then b(i+j):=i; l:=l, i+j fi
        od
      od; l
    end: T(1):=1:
b:= proc() 0 end:
seq(T(n), n=1..10);  # Alois P. Heinz, Jul 24 2013

T[n_] := T[n] = Module[{i, j, l, s}, l={}; Do[j=i; s={}; While[j>0, AppendTo[s, j]; j = b[j]]; Do[If[b[i+j] == 0, b[i+j]=i; AppendTo[l, i+j]], {j, Sort[s]}], {i, T[n-1]}]; l]; T[1]=1; Clear[b]; b[]=0; Table[T[n], {n, 1, 10}] // Flatten (* _Jean-François Alcover, Jun 15 2015, after Alois P. Heinz *)

from functools import cache
b = dict()
@cache
def T(n):
    global b
    if n == 1: return [1]
    l = []
    for i in T(n-1):
        j = i; s = []
        while j > 0:
            s.append(j)
            j = b.get(j, 0)
        for j in sorted(s):
            if b.get(i+j, 0) == 0:
                b[i+j] = i
                l.append(i+j)
    return l
print([Tik  for i in range(1, 9) for Tik in T(i)])  # Michael S. Branicky, Apr 28 2024 after Alois P. Heinz

Start the root node with label (1) in row 1. Assuming that the first n rows have been constructed, define row (n+1) of the power tree as follows. Proceeding from left to right in row n of the tree, take each node labeled L = T(n, k) and let the labels [1, T(2, j_2), T(3, j_3), ..., T(n, j_n)], where j_n=k, form the path from the root of the tree to node T(n, k). Attach to node (L) new nodes with labels generated by: [L+1, L+T(2, j_2), L+T(3, j_3), ..., L+T(n, k)=2*L] after discarding any label that has appeared before in the tree.

A003065 Number of integers with a shortest addition chain of length n.

Original entry on oeis.org

1, 1, 2, 3, 5, 9, 15, 26, 44, 78, 136, 246, 432, 772, 1382, 2481, 4490, 8170, 14866, 27128, 49544, 90371, 165432, 303475, 558275, 1028508, 1896704, 3501029, 6465774, 11947258, 22087489, 40886910, 75763102, 140588339, 261070184, 485074788, 901751654, 1677060520

Offset: 0

N. J. A. Sloane, Don Knuth

			a(6) = 15 because 15 numbers have shortest addition chains involving 6 additions. These numbers are 19,21,22,23,25,26,27,28,30,33,34,36,40,48,64.

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 2, p. 459.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
See A003313 for a much more extensive list of references and links.

Glen Whitney, Table of n, a(n) for n = 0..44 (Terms 0..38 from R. J. Mathar)
Daniel Bleichenbacher, Efficiency and Security of Cryptosystems based on Number Theory, PhD Thesis, Diss. ETH No. 11404, Zürich 1996. See p. 61.
M. Elia and F. Neri, A note on addition chains and some related conjectures, pp. 166-181 of R. M. Capocelli, ed., Sequences, Springer-Verlag, NY 1990.
Achim Flammenkamp, Shortest addition chains
Index to sequences related to the complexity of n

Cf. A003064, A003313.

Cf. A114623 [Number of integers for which Knuth's power tree method produces an addition chain of length n].

Updated through a(28) from Achim Flammenkamp's web site Feb 01 2005
a(28) corrected from 6465773 to 6465774, based on information received from Neill M. Clift. - Hugo Pfoertner, Jan 29 2006
a(29)-a(30) from Neill M. Clift, Jun 15 2007
a(31)-a(33) from Neill M. Clift, May 21 2008
b-file up to a(38) extracted from Achim Flammenkamp's web site. R. J. Mathar, May 14 2013
b-file updated to a(44) from Achim Flammenkamp's web site. Glen Whitney, Nov 09 2021

A182002 Smallest positive integer that cannot be computed using exactly n n's, the four basic arithmetic operations (+, -, *, /), and the parentheses.

Original entry on oeis.org

2, 2, 1, 10, 13, 22, 38, 91, 195, 443, 634, 1121, 3448, 6793, 17692

Offset: 1

Ali Dasdan, Apr 05 2012

			a(2) = 2 because two 2's can produce 0 = 2-2, 1 = 2/2, 4 = 2+2 = 2*2, so the smallest positive integer that cannot be computed is 2.
a(3) = 1 because no expression with three 3's gives 1.

Cf. A005245, A005520, A003313, A076142, A076091, A061373, A005421, A064097, A025280, A003037, A117618.

Cf. A171826, A171827, A171828, A171829, A258068, A258069, A258070, A258071.

f:= proc(n,b) option remember;
      `if`(n=1, {b}, {seq(seq(seq([k+m, k-m, k*m,
      `if`(m=0, NULL, k/m)][], m=f(n-i, b)), k=f(i, b)), i=1..n-1)})
    end:
a:= proc(n) local i, l;
      l:= sort([infinity, select(x-> is(x, integer) and x>0, f(n, n))[]]);
      for i do if l[i]<>i then return i fi od
    end:
seq(a(n), n=1..8); # Alois P. Heinz, Apr 13 2012

from fractions import Fraction
from functools import lru_cache
def a(n):
    @lru_cache()
    def f(m):
        if m == 1: return {Fraction(n, 1)}
        out = set()
        for j in range(1, m//2+1):
            for x in f(j):
                for y in f(m-j):
                    out.update([x + y, x - y, y - x, x * y])
                    if y: out.add(Fraction(x, y))
                    if x: out.add(Fraction(y, x))
        return out
    k, s = 1, f(n)
    while k in s: k += 1
    return k
print([a(n) for n in range(1, 10)]) # Michael S. Branicky, Jul 29 2022

a(11)-a(12) from Alois P. Heinz, Apr 22 2012
a(13)-a(14) from Michael S. Branicky, Jul 29 2022
a(15) from Michael S. Branicky, Jul 27 2023

A079300 a(n) = number of shortest addition chains ending in n.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 5, 1, 3, 4, 15, 3, 10, 14, 4, 1, 2, 7, 33, 6, 29, 40, 4, 4, 14, 24, 5, 23, 132, 12, 77, 1, 2, 4, 43, 12, 39, 92, 20, 8, 23, 84, 4, 69, 14, 8, 220, 5, 12, 36, 4, 38, 205, 16, 156, 32, 173, 352, 37, 24, 91, 233, 87, 1, 2, 4, 23, 6, 29, 134, 1258, 18, 49, 104, 32

Offset: 1

David W. Wilson, Feb 09 2003

nonn

An addition chain is a finite sequence of whole numbers starting with 1 in which each subsequent term is the sum of two (not necessarily distinct) earlier terms. - Glen Whitney, Nov 08 2021

			7 has a(7) = 5 shortest addition chains: (1,2,3,4,7), (1,2,3,5,7), (1,2,3,6,7), (1,2,4,5,7), (1,2,4,6,7).

Glen Whitney, Table of n, a(n) for n = 1..18286 (Terms 1..1024 from D. W. Wilson)
Achim Flammenkamp, Compressed table of a(n) (for all n such that A003313(n) < 23, including all n < 196591)
Achim Flammenkamp, Shortest addition chains
Eric Weisstein's World of Mathematics, Addition Chain
Glen Whitney, C program to compute counts of addition chains

Cf. A003313, A118386, A118387.

Cf. A079301, A079302, the number of shortest addition chains of Brauer and non-Brauer type, respectively.

a(n) = A079301(n) + A079302(n). - Glen Whitney, Nov 06 2021

More terms from Don Reble, Mar 31 2006

Name edited by Glen Whitney, Nov 08 2021

A230697 Length of shortest addition-multiplication chain for n.

Original entry on oeis.org

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

Offset: 1

Harry Altman, Oct 27 2013

			A shortest addition-multiplication chain for 16 is (1,2,4,16), of length a(16) = 3.
A shortest addition-multiplication chain for 281 is (1,2,4,5,16,25,256,281), of length a(281) = 7. This is the first case where not all terms in some shortest chain are the sum or product of the immediately preceding term and one more preceding term. In other words, 281 is the smallest of the analog of non-Brauer numbers (A349044) for addition-multiplication chains. The next ones are 913, 941, 996, 997, 998, 1012, 1077, 1079, 1542, 1572, 1575, 1589, 1706, 1792, 1795, 1816, 1864, ... . - _Pontus von Brömssen_, May 02 2025

Jinyuan Wang, Table of n, a(n) for n = 1..10000
H. M. Bahig, On a generalization of addition chains: Addition-multiplication chains, Discrete Mathematics 308 (2008), 611-616.
Gleb Ivanov, Python program.

Cf. A003313, A005245, A128998, A173419, A349044, A354914, A383001, A383002.

A113945 Numbers n such that the smallest possible number of multiplications required to compute x^n is by 1 less than the number of multiplications obtained by Knuth's power tree method.

Original entry on oeis.org

77, 154, 233, 293, 308, 319, 359, 367, 377, 382, 423, 457, 466, 551, 553, 559, 571, 573, 586, 616, 617, 619, 623, 638, 699, 713, 717, 718, 734, 754, 764, 813, 841, 846, 849, 869, 879, 905, 914, 932, 1007, 1051, 1063, 1069, 1102, 1103, 1106, 1115, 1118, 1133

Offset: 1

Hugo Pfoertner and Neill M. Clift, Jan 31 2006

nonn

The first three terms are given in Knuth's TAOCP, Vol. 2. The sequence is based on a table of shortest addition chain lengths computed by Neill M. Clift, see link to Achim Flammenkamp's web page given at A003313.

			a(1)=77 because the power tree construction produces the chain 1 2 3 5 7 14 19 38 76 77 requiring 9 additions, whereas there are 4 shortest chains that come along with 8 additions, e.g. 1 2 4 8 9 17 34 43 77.

D. E. Knuth, The Art of Computer Programming Third Edition. Vol. 2, Seminumerical Algorithms. Chapter 4.6.3 Evaluation of Powers, Page 464. Addison-Wesley, Reading, MA, 1997.

Cf. A114622 [The power tree (as defined by Knuth)], A003313 [Length of shortest addition chain for n], A115614 [numbers such that Knuth's power tree method produces a result deficient by 2], A115615 [numbers such that Knuth's power tree method produces a result deficient by 3], A115616 [smallest number for which Knuth's power tree method produces an addition chain n terms longer than the shortest possible chain].

cp's OEIS Frontend

A056792 Minimal number of steps to get from 0 to n by (a) adding 1 or (b) multiplying by 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Formula

Extensions

A173419 Length of shortest computation yielding n using addition, subtraction and multiplication (starting from 1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

A003064 a(n) = smallest number with shortest addition chain of length n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A014701 Number of multiplications to compute n-th power by the Chandah-sutra method.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A114622 The power tree (as defined by Knuth), read by rows, where T(n,k) is the label of the k-th node in row n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A003065 Number of integers with a shortest addition chain of length n.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Extensions

A182002 Smallest positive integer that cannot be computed using exactly n n's, the four basic arithmetic operations (+, -, *, /), and the parentheses.

Views