A064097 -id:A064097 - cp's OEIS frontend

A117498 Optimal combination of binary and factor methods for finding an addition chain.

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, 6, 6, 7, 6, 7, 7, 7, 6, 7, 7, 8, 7, 7, 8, 9, 6, 7, 7, 7, 7, 8, 7, 8, 7, 8, 8, 9, 7, 8, 8, 8, 6, 7, 7, 8, 7, 8, 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, 8, 8, 8, 9, 8, 9, 8, 9

Offset: 1

Franklin T. Adams-Watters, Mar 22 2006

nonn

This is an upper bound for both addition chains (A003313) and A117497. The first few values where A003313 is smaller are 23,43,46,47,59. The first few values where A117497 is smaller are 77,143,154,172,173. The first few values where both are smaller are 77,154,172,173,203.

For a function f from a finite set X to itself, let I(f) be the number of subsets A of X, which are f-stable in the sense that f(A) is contained in A. Then a(n) is the smallest positive integer m, such that a function f exists on a set with m elements, so that I(f) = n. The f-stable subsets form a finite topology on X, which implies that A137813 is a lower bound. The first index where A137813 is smaller is 23. - Qiaochu Yuan, Jun 27 2024

			a(33)=6 because 6 = 1+a(32) < a(3)+a(11) = 2+5. a(36) = min(a(35)+1, a(2)+a(18), a(3)+a(12), a(4)+a(9), a(6)+a(6)) = min(1+7, 1+5, 2+4, 2+4, 3+3) = 6.

John M. Campbell, A binary version of the Mahler-Popken complexity function, arXiv:2403.20073 [math.NT], 2024. See pp. 5-6. See also Integers (2024) Vol. 24, Art. No. A94. See pp. 5-6.
Math.Stackexchange, On the number of f-stable subsets, question posted by Alessandrod and answered by Qiaochu Yuan, June 23, 2024.
Index to sequences related to the complexity of n

Cf. A003313, A117497, A064097, A137813.

a(1)=0; a(n) = min(a(n-1)+1, min_{d|n, 1

A117632 Number of 1's required to build n using {+,T} and parentheses, where T(i) = i*(i+1)/2.

Original entry on oeis.org

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

Offset: 1

Jonathan Vos Post, Apr 08 2006

nonn

This problem has the optimal substructure property.

			a(1) = 1 because "1" has a single 1.
a(2) = 2 because "1+1" has two 1's.
a(3) = 2 because 3 = T(1+1) has two 1's.
a(6) = 2 because 6 = T(T(1+1)).
a(10) = 3 because 10 = T(T(1+1)+1).
a(12) = 4 because 12 = T(T(1+1)) + T(T(1+1)).
a(15) = 4 because 15 = T(T(1+1)+1+1).
a(21) = 2 because 21 = T(T(T(1+1))).
a(28) = 3 because 28 = T(T(T(1+1))+1).
a(55) = 3 because 55 = T(T(T(1+1)+1)).

W. A. Beyer, M. L. Stein and S. M. Ulam, The Notion of Complexity. Report LA-4822, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, 1971.
R. K. Guy, Unsolved Problems Number Theory, Sect. F26.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
W. A. Beyer, M. L. Stein and S. M. Ulam, The Notion of Complexity. Report LA-4822, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, December 1971. [Annotated scanned copy]
R. K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.
Ed Pegg, Jr., Integer Complexity.
Eric Weisstein's World of Mathematics, Integer Complexity.
Wikipedia, Optimal substructure.

See also A023361 = number of compositions into sums of triangular numbers, A053614 = numbers that are not the sum of triangular numbers. Iterated triangular numbers: A050536, A050542, A050548, A050909, A007501.

Cf. A000217, A005245, A005520, A003313, A076142, A076091, A061373, A005421, A023361, A053614, A064097, A025280, A003037, A099129, A050536, A050542, A050548, A050909, A007501.

a:= proc(n) option remember; local m; m:= floor (sqrt (n*2));
      if n<3 then n
    elif n=m*(m+1)/2 then a(m)
    else min (seq (a(i)+a(n-i), i=1..floor(n/2)))
      fi
    end:
seq (a(n), n=1..110);  # Alois P. Heinz, Jan 05 2011

a[n_] := a[n] = Module[{m = Floor[Sqrt[n*2]]}, If[n < 3, n, If[n == m*(m + 1)/2, a[m], Min[Table[a[i] + a[n - i], {i, 1, Floor[n/2]}]]]]];
Array[a, 110] (* Jean-François Alcover, Jun 02 2018, from Maple *)

I do not know how many of these entries have been proved to be minimal. - N. J. A. Sloane, Apr 15 2006

Corrected and extended by Alois P. Heinz, Jan 05 2011

A333959 First occurrence of n in A334144.

Original entry on oeis.org

1, 6, 15, 33, 65, 77, 154, 161, 217, 231, 455, 469, 483, 693, 957, 987, 1001, 1449, 1463, 2021, 2717, 2093, 2415, 2967, 3003, 4147, 3059, 4853, 4945, 4899, 6083, 8533, 4991, 7161, 9982, 8987, 9177, 10787, 10857, 10465, 10199, 12857, 14539, 20355, 18753, 20398

Offset: 1

Michael De Vlieger, Peter Kagey, Antti Karttunen, Robert G. Wilson v, Apr 24 2020

nonn

Consider the mappings f(m) := m -> m - m/p across primes p | m.
Row m of A334184, read as a triangle T(m, k), lists the number of distinct values that proceed from the mapping after exactly k iterations.
A334144(m) is the largest value in row m of A334184.
The smallest term in this sequence that is not an index of a record in A334144 is a(22) = 2093.
From Robert G. Wilson v, Jun 14 2020: (Start)
All terms are nonprimes, but not necessarily squarefree. They are: 693, 1449, 91791, 13126113, 46334057, ..., .
Even terms: 6, 154, 9982, 20398, 29946, 812630, 1366666, 4263182, 17766658, 22866158, 34688186, 80633294, ..., .
Except for the initial even term, all even terms divided by 2 are also terms.
(End)

			1 is the first term since 1 is the empty product.
6 follows 1 since 2 <= m <= 5 have total order, thus the maximum number in A333184 is 1. For m = 6, the mapping f(m) has two distinct results {4, 3}, which generate chains {4, 2, 1} and {3, 2, 1}, respectively, with the last two terms in both chains coincident. Since the largest number of terms in an antichain is 2, a(2) = 6.
15 follows 6 since row 15 of A334184 = [1, 2, 3, 2, 1, 1] is the smallest m for which n = 3 appears.
Hasse diagrams of the 3 smallest terms, with brackets around the widest row.
[1]        6           15
          / \          /\
         /   \        /  \
        [4   3]     12  __10
         |  /       | \/   |
         | /        |_/\   |
         2         [8  _6  5]
         |          | /_|_/
         |          |// |
         1          4   3
                    |  /
                    |_/
                    2
                    |
                    |
                    1

Robert G. Wilson v, Table of n, a(n) for n = 1..871 (first 256 terms from Peter Kagey)
Math StackExchange, Does a graded poset on the positive integers generated from subtracting factors define a lattice?, 2020.
Michael De Vlieger, Hasse diagrams of a(n) for 2 <= n <= 37.

Cf. A064097, A332809, A333123, A334144, A334184.

With[{s = Table[Max[Length@ Union@ # & /@ Transpose@ #] &@ If[n == 1, {{1}}, NestWhile[If[Length[#] == 0, Map[{n, #} &, # - # /FactorInteger[#][[All, 1]] ], Union[Join @@ Map[Function[{w, n}, Map[Append[w, If[n == 0, 0, n - n/#]] &, FactorInteger[n][[All, 1]] ]] @@ {#, Last@ #} &, #]] ] &, n, If[ListQ[#], AllTrue[#, Last[#] > 1 &], # > 1] &]], {n, 10^3}]}, TakeWhile[Array[FirstPosition[s, #][[1]] &, Max@ s], IntegerQ]]
f[n_] := Block[{lst = {{n}}}, While[lst[[-1]] != {1}, lst = Join[ lst, {Union[ Flatten[# - #/(First@# & /@ FactorInteger@#) & /@ lst[[-1]]] ]}]]; Max[Length@# & /@ lst]]; t[] := 0; k = 1; While[k < 21001, a = f@k; If[ t[a] == 0, t[a] = k]; k++]; t@# & /@ Range@ 46 (* _Robert G. Wilson v, Jun 14 2020 *)

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

Previous Showing 41-47 of 47 results.

cp's OEIS Frontend

A307743 a(n) = Sum_{k=1..n} A307742(k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A307723 Naturally ordered prime factorization of n as a quasi-logarithmic word over the binary alphabet {1,0}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A334206 Fully additive with a(p) = 1 + a(A014682(p)) when p is prime and a(n*m) = a(n) + a(m) when m,n > 1.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A117498 Optimal combination of binary and factor methods for finding an addition chain.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A117632 Number of 1's required to build n using {+,T} and parentheses, where T(i) = i*(i+1)/2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A333959 First occurrence of n in A334144.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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