Janis Iraids - cp's OEIS frontend

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

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

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

Original entry on oeis.org

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.

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];
}

A210660 Smallest number m such that A210659(m)=n.

Original entry on oeis.org

1, 2, 6, 7, 14, 23, 86, 179, 538, 1439, 9566, 21383, 122847, 777419, 1965374, 6803099, 19860614, 26489579, 269998838, 477028439

Offset: 0

Janis Iraids, Mar 28 2012

nonn

The sequence was discovered by Martins Opmanis.

J. Iraids, K. Balodis, J. Cernenoks, M. Opmanis, R. Opmanis and K. Podnieks, Integer Complexity: Experimental and Analytical Results. arXiv preprint arXiv:1203.6462, 2012. - From _N. J. A. Sloane_, Sep 22 2012
Index to sequences related to the complexity of n

Cf. A210659, A005245, A005520.

cp's OEIS Frontend

User: Janis Iraids

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

A210660 Smallest number m such that A210659(m)=n.

Views

Author

Keywords

Comments

Links

Crossrefs