A005245 -id:A005245 - cp's OEIS frontend

A255641 Smallest number requiring n 1's to build using +, * and -.

1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 29, 41, 58, 67, 101, 131, 173, 262, 346, 461, 617, 787, 1123, 1571, 2077, 2767, 4153, 5443, 7963, 10733, 13997, 21101, 27997, 36643, 49747, 72103, 99317, 143239, 179107, 260213

Offset: 1

Janis Iraids, Mar 01 2015

nonn

Until n = 10 the terms are equal to A005520(n) where subtraction is not allowed.

			a(11) = 29, because 23 = (1+1)*(1+1)*(1+1)*(1+1+1)-1, but 29 = ((1+1+1)*(1+1)+1)*(1+1)*(1+1)+1.

Janis Iraids, Table of n, a(n) for n = 1..81
Juris Čerņenoks, Jānis Iraids, Mārtiņš Opmanis, Rihards Opmanis, and Kārlis Podnieks, Integer Complexity: Experimental and Analytical Results II, arXiv:1409.0446 [math.NT], 2014.
Index to sequences related to the complexity of n

Least inverse (or records) of A091333.

Cf. A005520, A005245, A173419.

A351467 Numbers with integer defect at most 1; m such that A350723(m) <= 1.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 18, 19, 20, 21, 24, 27, 28, 30, 32, 36, 37, 38, 39, 40, 42, 45, 48, 54, 55, 56, 57, 60, 63, 64, 72, 81, 82, 84, 90, 96, 108, 109, 110, 111, 112, 114, 117, 120, 126, 128, 135, 144, 162, 163, 164, 165, 168, 171

Offset: 1

Harry Altman, Feb 12 2022

m appears in this list if and only if it can be written as 2^p*3^r for p <= 10 or as 2^p*(2^q*3^r+1)*3^s for p+q <= 2.

Harry Altman, Integer Complexity: The Integer Defect, Moscow Journal of Combinatorics and Number Theory 8-3 (2019), 193-217.

Harry Altman, Integer Complexity: The Integer Defect, arXiv:1804.07446 [math.NT], 2018.

Cf. A350723, A005245, A349983. Contains A000792 as a subset.

A362471 a(n) is the smallest number of 1's used in expressing n as a calculation containing only decimal repunits and operators +, -, * and /.

Original entry on oeis.org

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

Offset: 1

Yifan Xie, Haochen Mi and Michael S. Branicky, Apr 21 2023

Here, fractions are not allowed as intermediate results.

See A362626 for the variant that allows such fractions. The sequences differ first at a(74) and its immediate neighbors, since a(74) = 8 > 7 = A362626(74). See the example in A362626. - Peter Munn, Apr 28 2023

			For n = 6, 6 = (1+1)*(1+1+1), so a(6) = 5.
For n = 32, 32 = 11*(1+1+1)-1, so a(32) = 6.
For n = 37, 37 = 111/(1+1+1), so a(37) = 6.
For n = 78, 78 = 111-(11)*(1+1+1), so a(78) = 8.

Michael S. Branicky, Table of n, a(n) for n = 1..10000

Cf. A002275, A005245, A091333, A133344, A362626.

a(n+1) <= a(n) + 1.

a(n) <= a(i) + a(j), for all i O j = n, for O = +, -, *, /.

A362626 a(n) is the smallest number of 1's used in expressing n as a calculation containing only decimal repunits and operators +, -, * and /, where fractions are allowed as intermediate results.

Original entry on oeis.org

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

Offset: 1

Yifan Xie, Haochen Mi and Michael S. Branicky, Apr 28 2023

a(n+1) <= a(n) + 1.

a(n) <= a(i) + a(j), for all i O j = n, for O = +, -, *, /.

			a(74) = 7, since 74 = 111/(1+(1/(1+1))).
a(111) = 3.

Michael S. Branicky, Table of n, a(n) for n = 1..10000

Cf. A002275, A005245, A362471.

A168650 Integers that can be generated with a C/C++ expression that is shorter than their decimal representation.

Original entry on oeis.org

1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000, 11000, 12000, 13000, 14000, 15000, 16000, 17000, 18000, 19000, 20000, 21000, 22000, 23000, 24000, 25000, 26000, 27000, 28000, 29000, 30000, 31000, 32000, 33000, 34000, 35000

Offset: 1

Dmitry Kamenetsky, Dec 01 2009

From Dmitry Kamenetsky, Jul 24 2015: (Start)
By "expression" we mean a string representing a piece of code in C/C++ that evaluates to a positive integer, where we assume for simplicity that the result is converted to an integer using the floor operation. An expression can use the binary operators available in those languages and the digits '0' to '9', and we also allow "AeB" for A*10^B.
For example: "A+B" evaluates to A plus B, "A*B" evaluates to A multiplied by B, "A/B" is floor(A/B), "A<This sequence lists every integer n having an expression whose length is strictly less than the decimal length of n; of course every integer n has an expression whose length is the same as the decimal length of n, namely "n". In some sense the numbers in this sequence can be considered simple, since they have a low Kolmogorov complexity.
We assume that there are no rounding errors or integer overflow during the evaluation of the expression.(End)

			1000 has 4 digits, but it can be generated with a 3-digit expression "1e3". The integers 43000, 116666, 114688, 199997 are also in the sequence, since they can be generated using the expressions "43e3", "7e5/6", "7<<14", "2e5-3" respectively.

Dmitry Kamenetsky, Table of n, a(n) for n = 1..14238
Dmitry Kamenetsky, Plot showing the length of the shortest C/C++ expression that generates integers from 1 to 2000000.
Ed Pegg, Jr., Integer Complexity, 2004.
L. Staiger, The Kolmogorov complexity of real numbers, Theoretical Computer Science, pp. 455-466, 2002.
E. Weisstein, Integer Complexity
Wikipedia, Kolmogorov Complexity
Index to sequences related to the complexity of n

Cf. A005245, A117607, A118121, A168651, A168652.

Name clarified by Dmitry Kamenetsky, Jul 24 2015

A182061 Smallest number with "natural" logarithm n, cf. A061373.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 23, 41, 46, 47, 83, 94, 139, 167, 235, 283, 359, 517, 659, 719, 1081, 1319, 1439, 2209, 2878, 2879, 5756, 5758, 8637, 11516, 14395, 20147, 28790, 31669, 48943, 61993, 66217, 103823, 132434, 135313, 238957, 270626, 397303

Offset: 1

Reinhard Zumkeller, Apr 09 2012

nonn

Corresponding to A061373 like A005520 to A005245; A061373(a(n)) = n and A061373(m) < n for m < a(n).

Index to sequences related to the complexity of n

import Data.List (elemIndex)
import Data.Maybe (fromJust)
a182061 = (+ 1) . fromJust . (`elemIndex` a061373_list)

A253177 Numbers which can be expressed with fewer 1s using +, -, and * than with + and *.

Original entry on oeis.org

23, 47, 53, 59, 69, 71, 89, 94, 106, 107, 134, 141, 142, 143, 159, 161, 167, 177, 178, 179, 188, 191, 207, 212, 213, 214, 215, 227, 233, 239, 242, 251, 263, 265, 267, 268, 269, 282, 283, 284, 286, 287, 299, 311, 317, 318, 319, 321

Offset: 1

Charles R Greathouse IV, Mar 23 2015

nonn

Numbers n such that A005245(n) > A091333(n). Is it true that a(n) ~ n?

			23 = 2*3*4 - 1 = 3*(2*3 + 1) + 2 can be written with 10 1s using subtraction but requires 11 without, hence 23 is a member. Here the digits 2, 3, and 4 are used for clarity, but could be expanded to (1+1), (1+1+1), etc.

Charles R Greathouse IV, Table of n, a(n) for n = 1..3128
Index to sequences related to the complexity of n

Cf. A091333, A005520, A005245, A173419, A255641.

A265360 Second smallest number of complexity n: second smallest number requiring n 1's to build using + and *.

Original entry on oeis.org

6, 8, 12, 13, 19, 25, 29, 43, 53, 67, 94, 131, 173, 214, 269, 359, 479, 713, 863, 1277, 1499, 2099, 3019, 3833, 5639, 7103, 10463, 12527, 18899, 22643, 33647, 45989, 60443, 88379, 103319, 166319, 206639, 280223, 384479, 543659, 755663, 1020599, 1316699, 1856159, 2556839, 3346559, 4895963, 6649199, 8666783

Offset: 5

Antti Karttunen, with terms computed by Janis Iraids, Dec 15 2015

nonn

As the first term of A005421 > 1 is A005421(5), the starting offset of this sequence is 5.

Only composites seem to be 6, 8, 12, 25, 94, 214, 713 and in many ways the sequence seems to have similar properties with A005520, the smallest number of complexity n.

Jānis Iraids, Table of n, a(n) for n = 5..89

Cf. A005245, A005421, A005520.

def aupton(nn):
  alst, R = [], {0: {1}} # R[n] is set reachable using n+1 1's (n ops)
  for n in range(1, nn):
    R[n]  = set(a+b for i in range(n//2+1) for a in R[i] for b in R[n-1-i])
    R[n] |= set(a*b for i in range(n//2+1) for a in R[i] for b in R[n-1-i])
    new = R[n] - R[n-1]
    if n >= 4: alst.append(min(new - {min(new)}))
  return alst
print(aupton(35)) # Michael S. Branicky, Jun 08 2021

A210659 The smallest possible depth of an arithmetic expression for n using only +, *, parentheses and the minimum number of 1's.

Original entry on oeis.org

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

Offset: 1

Janis Iraids, Mar 28 2012

nonn

The minimum number of leaves is A005245(n).
The tree of an arithmetic expression for n is a rooted tree with the number 1 in leaves and addition or multiplication in inner nodes such that the inner nodes correspond to operations in the expression and its children are the operands of said operation. Adjacent additions (and multiplications) are allowed to be merged and typically give smaller depth.
This sequence was discovered by Martins Opmanis and Jānis Iraids.

			4 can be written as (1+1)*(1+1) or 1+1+1+1 with a minimum number of ones, but the depth of the tree of the latter expression is smaller - 1 compared to 2 - so a(4)=1.

Janis Iraids, Table of n, a(n) for n = 1..10000
Index to sequences related to the complexity of n

Cf. A005245, A210660.

int a(int* rank, int N) { // output rank in the array for values up to N
  rank[1]=0;
  for(int n=2;n<=N;i++){
    int r=n;
    for(int a=1;a<=N/2;a++)
      if(c(a)+c(n-a)==c(n)){ // c(n) -- the complexity function A005245(n)
        int ro=max(rank[a],rank[n-a]);
        r=min(r,ro%2==0?ro+1:ro);
      }
    for(int a=1;a*a<=N;a++)
      if(n%a==0&&c(a)+c(n/a)==c(n)){
        int ro=max(rank[a],rank[n/a]);
        r=min(r,ro%2==0?ro:ro+1);
      }
    rank[n]=r;
  }
  return rank[N];
}

A214835 Total sum of lengths of formula representations of n using addition, multiplication and the constant 1.

Original entry on oeis.org

1, 3, 10, 42, 144, 564, 2064, 7944, 30252, 117000, 453192, 1768480, 6917504, 27163232, 106923648, 421931308, 1668250408, 6608054656, 26215991648, 104154492224, 414324786144, 1650080158832, 6578448714144, 26251704924528, 104850927048448, 419119282453408

Offset: 1

Alois P. Heinz, Mar 07 2013

nonn

			a(1) = 1: 1.
a(2) = 3: 11+.
a(3) = 10: 111++, 11+1+.
a(4) = 42: 1111+++, 111+1++, 11+11++, 111++1+, 11+1+1+, 11+11+*.
a(5) = 144: 11111++++, 1111+1+++, 111+11+++, 1111++1++, 111+1+1++, 111+11+*+, 11+111+++, 11+11+1++, 111++11++, 11+1+11++, 1111+++1+, 111+1++1+, 11+11++1+, 111++1+1+, 11+1+1+1+, 11+11+*1+.

Alois P. Heinz, Table of n, a(n) for n = 1..100
Edinah K. Ghang, Doron Zeilberger, Zeroless Arithmetic: Representing Integers ONLY using ONE, arXiv:1303.0885v1 [math.CO], 2013
Shalosh B. Ekhad, Everything About Formulas Representing Integers Using Additions and Multiplication for integers from 1 to 8000
Wikipedia, Postfix notation
Index to sequences related to the complexity of n

Cf. A005245, A214833 (number of formula representations), A213923 (minimal length of formula), A005408(n-1) (maximal length of formula).

Previous Showing 31-40 of 60 results. Next

cp's OEIS Frontend

A255641 Smallest number requiring n 1's to build using +, * and -.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A351467 Numbers with integer defect at most 1; m such that A350723(m) <= 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A362471 a(n) is the smallest number of 1's used in expressing n as a calculation containing only decimal repunits and operators +, -, * and /.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A362626 a(n) is the smallest number of 1's used in expressing n as a calculation containing only decimal repunits and operators +, -, * and /, where fractions are allowed as intermediate results.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A168650 Integers that can be generated with a C/C++ expression that is shorter than their decimal representation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A182061 Smallest number with "natural" logarithm n, cf. A061373.

Views

Author

Keywords

Comments

Links

Programs

Haskell

A253177 Numbers which can be expressed with fewer 1s using +, -, and * than with + and *.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A265360 Second smallest number of complexity n: second smallest number requiring n 1's to build using + and *.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

A210659 The smallest possible depth of an arithmetic expression for n using only +, *, parentheses and the minimum number of 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

A214835 Total sum of lengths of formula representations of n using addition, multiplication and the constant 1.

Views