A003313 -id:A003313 - cp's OEIS frontend

A086833 Minimum number of different addends occurring in any shortest addition chain of Brauer type for a given n, or 0 if n has no shortest addition chain of Brauer type.

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

Offset: 1

Tatsuru Murai, Aug 08 2003

nonn

n = 12509 is the first n for which a(n) = 0 because it is the smallest number that has no shortest addition chain of Brauer type. - Hugo Pfoertner, Jun 10 2006 [Edited by Pontus von Brömssen, Apr 25 2025]

			a(23)=5 because 23=1+1+2+1+4+9+5 is the shortest addition chain for 23.
For n=9 there are A079301(9)=3 different shortest addition chains, all of Brauer type:
[1 2 3 6 9] -> 9=1+1+1+3+3 -> 2 different addends {1,3}
[1 2 4 5 9] -> 9=1+1+2+1+4 -> 3 different addends {1,2,4}
[1 2 4 8 9] -> 9=1+1+2+4+1 -> 3 different addends {1,2,4}
The minimum number of different addends is 2, therefore a(9)=2.

Giovanni Resta, Tables of Shortest Addition Chains, computed by David W. Wilson.
Index to sequences related to the complexity of n

Cf. A003064, A003065, A003313, A005766, A008057, A008928, A008933, A079300, A079300, A079301, A349044.

a(n) = 0 if and only if n is in A349044. - Pontus von Brömssen, Apr 25 2025

Edited by Hugo Pfoertner, Jun 10 2006

Escape clause added by Pontus von Brömssen, Apr 25 2025

A104233 Positive integers which have a "compact" representation using fewer decimal digits than just writing the number normally.

Original entry on oeis.org

125, 128, 216, 243, 256, 343, 512, 625, 729, 1000, 1015, 1016, 1017, 1018, 1019, 1020, 1021, 1022, 1023, 1024, 1025, 1026, 1027, 1028, 1029, 1030, 1031, 1032, 1033, 1080, 1089, 1125, 1152, 1156, 1215, 1225, 1250, 1280, 1287, 1288, 1289, 1290, 1291, 1292, 1293, 1294

Offset: 1

Jack Brennen, Apr 01 2005

You are allowed to use the following symbols as well:
  ( ) grouping
  + addition
  - subtraction
  * multiplication
  / division
  ^ exponentiation
Note that 1015 to 1033 are all representable in the form 4^5-d or 4^5+d, where d is a single digit.
The complexity of a number has been defined in several different ways by different authors. See the Index to the OEIS for other definitions. - Jonathan Vos Post, Apr 02 2005
From Bernard Schott, Feb 10 2021: (Start)
These numbers are called "entiers compressibles" in French.
There are no 1-digit or 2-digit terms.
The 3-digit terms are all of the form m^q, with 2 <= m, q <= 9.
The 4-digit terms are of the form m^q with m, q > 1, or of the form m^q+-d or m^q*r with m, q, r > 1, d >= 0, and m, q, r, d are all digits (see examples where [...] is a corresponding "compact" representation). (End)

			From _Bernard Schott_, Feb 10 2021: (Start)
a(1) = 125 = [5^3] = 5*5*5 is the smallest cube.
a(5) = 256 = [2^8] = [4^4] = 16*16 is the smallest square.
a(6) = 343 = [7^3] is the smallest palindrome.
a(15) = 1019 = [4^5-5] is the smallest prime.
6555 = [3^8-5] = [35^2] = T(49) = 49*50/2 is the smallest triangular number.
362880 = 9! = [70*72^2] = [8*(6^6-6^4)] is the smallest factorial.
The smallest zeroless pandigital number 123456789 = [(10^10-91)/81] = [3*(6415^2+38)] is a term. (End)
The largest pandigital number 9876543210 = [(8*10^11+10)/81] = [(8*10^11+10)/9^2] = [5*(15^5+67)*51^2] is also a term. - _Bernard Schott_, Apr 20 2022

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

J. Arias de Reyna, Complejidad de los números naturales, Gaceta R. Soc. Mat. Esp., 3 (2000), 230-250. [Cached copy, with permission]
J. Arias de Reyna, Complexity of natural numbers, arXiv:2111.03345 [math.NT], 2021.
Diophante, A164, Les entiers compressibles (in French).
R. K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.
Eric Weisstein's World of Mathematics, Integer Complexity
Index to sequences related to the complexity of n

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

More terms from Bernard Schott, Feb 10 2021

Missing terms added by David A. Corneth, Feb 14 2021

A124393 Numbers whose shortest addition chains unavoidably contain 3.

Original entry on oeis.org

3, 14759, 15449, 26089

Offset: 1

Max Alekseyev, Dec 16 2006

For a comprehensive list of references see A003313.

A186520 Number of evaluation schemes for x^n achieving the minimal number of multiplications, and with the maximal number of squarings among the multiplications.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 4, 1, 1, 2, 4, 3, 5, 10, 2, 1, 1, 2, 4, 3, 5, 10, 2, 4, 7, 12, 2, 16, 47, 6, 22, 1, 1, 2, 4, 3, 5, 10, 10, 4, 6, 12, 2, 18, 2, 4, 10, 5, 7, 17, 2, 19, 55, 6, 28, 22, 49, 120, 8, 12

Offset: 1

Laurent Thévenoux and Christophe Mouilleron, Feb 23 2011

nonn

			For n=7, we can evaluate x^7 using only 4 operations in 6 ways:
  x^2 = x * x ; x^3 = x   * x^2 ; x^4 = x   * x^3 ; x^7 = x^3 * x^4    (1 squaring)
  x^2 = x * x ; x^3 = x   * x^2 ; x^4 = x^2 * x^2 ; x^7 = x^3 * x^4    (2 squarings)
  x^2 = x * x ; x^3 = x   * x^2 ; x^5 = x^2 * x^3 ; x^7 = x^2 * x^5    (1 squaring)
  x^2 = x * x ; x^3 = x   * x^2 ; x^6 = x^3 * x^3 ; x^7 = x   * x^6    (2 squarings)
  x^2 = x * x ; x^4 = x^2 * x^2 ; x^5 = x   * x^4 ; x^7 = x^2 * x^5    (2 squarings)
  x^2 = x * x ; x^4 = x^2 * x^2 ; x^6 = x^2 * x^4 ; x^7 = x   * x^6    (2 squarings)
The maximal number of squarings in these evaluation schemes is 2, and it is achieved by a(7) = 4 schemes.

Cf A003313, A186435, A186437.

A372152 Number of k in the range 2^n <= k < 2^(n+1) whose shortest addition chain does not have length n, n+1 or n+2.

Original entry on oeis.org

0, 0, 0, 0, 2, 9, 30, 80, 193, 432, 925, 1928, 3953, 8024, 16189, 32544

Offset: 0

Szymon Lukaszyk, Apr 20 2024

The length of the shortest addition chain for k is A003313(k).
Dividing natural numbers into sections 2^n <= k < 2^(n+1), some of the 2^n numbers available in a section have the shortest addition chains given by
 n (for k=2^n),
 n+1 (for k=2^n+2^m, m in [0..n-1], A048645), or
 n+2 (for some k in A072823).
The sequence gives the numbers of k within each section (N_oth) that have the shortest addition chains other than n, n+1, and n+2.
In particular for 4 <= n <= 6, N_oth = 2^n - n^2 + 2 and for n >= 7, N_oth = 2^n - n^2 + 1.

S. Łukaszyk and W. Bieniawski, Assembly Theory of Binary Messages, Mathematics, 12(10) (2024), 1600.

Cf. A003313, A048645, A072823, A014701, A024012.

cp's OEIS Frontend

A086833 Minimum number of different addends occurring in any shortest addition chain of Brauer type for a given n, or 0 if n has no shortest addition chain of Brauer type.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A104233 Positive integers which have a "compact" representation using fewer decimal digits than just writing the number normally.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A124393 Numbers whose shortest addition chains unavoidably contain 3.

Views

Author

Keywords

References

A186520 Number of evaluation schemes for x^n achieving the minimal number of multiplications, and with the maximal number of squarings among the multiplications.

Views

Author

Keywords

Examples

Crossrefs

A372152 Number of k in the range 2^n <= k < 2^(n+1) whose shortest addition chain does not have length n, n+1 or n+2.

Views

Author

Keywords

Comments

Links

Crossrefs