A025280 -id:A025280 - cp's OEIS frontend

A319975 Smallest number of complexity n with respect to the operations {1, shift, multiply}.

1, 2, 3, 4, 5, 6, 7, 10, 11, 14, 19, 22, 23, 38, 43, 58, 59, 89, 107, 134, 167, 179, 263, 347, 383, 537, 713, 719, 1103, 1319, 1439, 2099, 2879, 3833, 4283, 5939, 6299, 9059, 12239, 15118, 19079, 23039, 26459, 44879, 49559, 66239, 78839, 98999, 137339

Offset: 1

N. J. A. Sloane, Oct 11 2018

nonn

The shift operation here is also sometimes called successor, see A263283.

Note this complexity measure counts both operands (the ones) and operators (the shifts and multiplications), whereas most of the complexity measures in the crossrefs count only operands. However, in the presence of successor it would not make sense to count only operands, since any number can be expressed with a single occurrence of 1. - Glen Whitney, Oct 06 2021

			1 = 1 has complexity 1
2 = S1 has complexity 2
3 = SS1 has complexity 3
4 = SSS1 has complexity 4
5 = SSSS1 has complexity 5
6 = SSSSS1 has complexity 6
7 = SSSSSS1 has complexity 7
10 = S*SS1SS1 = shift(product of (3 and 3)) has complexity 8
(Note that 8 = *S1SSS1 has complexity 7)
11 = SS*SS1SS1 has complexity 9
14 = SS*SS1SSS1 has complexity 10

Michael S. Branicky, Table of n, a(n) for n = 1..67
Akshunna Shaurya Dogra, Minimal Representations of Natural Numbers Under a Set of Operators, arXiv preprint 1801.01360 [math.HO], Jan 2018.
Index to sequences related to the complexity of n.

Smallest number of complexity n (other definitions): A003037, A005520, A244743, A259466, and A265360.

Other definitions of the complexity of n: A005208, A005245, A025280, and A099053.

def aupton(nn):
    alst, R, allR = [1], {1: {1}}, {1} # R[n] is set reachable using n ops
    for n in range(2, nn+1):
        R[n]  = set(a+1 for a in R[n-1])
        R[n] |= set(a*b for i in range(1, (n+1)//2) for a in R[i] for b in R[n-1-i])
        alst.append(min(R[n] - allR))
        allR |= R[n]
    return alst
print(aupton(49)) # Michael S. Branicky, Oct 06 2021

A360269 Least sum of 2's and 3's required to build n using +, * and parentheses.

Original entry on oeis.org

2, 3, 4, 5, 5, 7, 6, 6, 7, 8, 7, 10, 9, 8, 8, 10, 8, 11, 9, 10, 10, 12, 9, 10, 11, 9, 11, 11, 10, 13, 10, 11, 12, 12, 10, 14, 12, 13, 11, 15, 12, 14, 12, 11, 14, 13, 11, 14, 12, 13, 13, 15, 11, 13, 13, 14, 13, 16, 12, 16, 14, 13, 12, 15, 13, 15, 14, 15, 14

Offset: 2

Tamas Sandor Nagy, Jan 31 2023

nonn

			a(7) = 7 because 7 built by the rules is 2*2+3 or 2+2+3, and in both cases the sum is 7 and there is no other combination with a lesser sum.
a(17) = 10 because 17 = (2+3)*3+2, with 10 being the minimal sum.
a(22) = 10 because 22 = 2*(3*3+2) and these 2's and 3's add up to 10, which is the least possible sum.
a(44) = 12 because 44 = 2*2*(3*3+2), with the least possible sum being 12.

Andrew Howroyd, Table of n, a(n) for n = 2..10000
Index to sequences related to the complexity of n

Cf. A000040, A025280.

seq(n)=my(a=vector(n)); for(n=1, #a, my(m=if(n==2||n==3, n, oo)); for(k=2, n-2, m=min(m, a[k]+a[n-k])); fordiv(n, d, if(d>1&&dAndrew Howroyd, Jan 31 2023

Terms a(46) and beyond from Andrew Howroyd, Feb 01 2023

A370829 Minimum number of (-1)'s needed to write n, using +, *, ^ and parentheses, disallowing noninteger intermediate values.

Original entry on oeis.org

2, 3, 4, 4, 6, 5, 7, 6, 6, 7, 8, 7, 9, 8, 7, 6, 8, 9, 10, 9, 10, 11, 10, 9, 8, 9, 8, 9, 10, 10, 10, 9, 10, 10, 9, 8, 10, 11, 11, 11, 13, 12, 13, 12, 11, 12, 11, 10, 10, 11, 11, 11, 10, 9, 11, 10, 12, 11, 12, 11, 10, 9, 8, 7, 9, 10, 11, 11, 13, 12, 12, 11, 12, 12, 12, 12, 11, 10, 9, 8, 7

Offset: 1

Edgar Deshayes, Mar 02 2024

nonn

a(n) is bounded by a(n-1)-1 <= a(n) <= a(n-1)+2 since:
An expression for n-1 can be increased to n by " + (-1)*(-1)" which is 2 more (-1)'s so that a(n) <= a(n-1)+2.
An expression for n can be decreased to n-1 by "+ (-1)" which is 1 more (-1) so that a(n-1) <= a(n)+1.

			Let m = -1. Then, n = 1..9 can be expressed using a(n) m's as follows:
a(1)=2: 1 = (-1)*(-1) = m*m.
a(2)=3: 2 = (-2)*(-1) = (m+m)*m.
a(3)=4: 3 = (-3)*(-1) = (m+m+m)*m.
a(4)=4: 4 = (-2)*(-2) = (m+m)*(m+m).
a(5)=6: 5 = (-5)*(-1) = (m+m+m+m+m)*m.
a(6)=5: 6 = (-2)*(-3) = (m+m)*(m+m+m).
a(7)=7: 7 =   8 +(-1) = (m+m+m+m)*(m+m)+m.
a(8)=6: 8 = (-4)*(-2) = (m+m+m+m)*(m+m).
a(9)=6: 9 = (-3)^  2  = (m+m+m)^((m+m)*m).

Edgar Deshayes, Java program

Cf. A025280 (same with +1).

Java
```
// see linked program
```

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

A329526 Number of 1's required to build n using +, -, *, ^ and factorial.

Original entry on oeis.org

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

Offset: 1

Onno M. Cain, Nov 15 2019

nonn

A number n may be written from the digits of its binary representation using the 5 aforementioned operations whenever a(n) <= floor(log_2(n))+1.

			a(117) = 7 since 117 = ((1+1+1)!-1)!-1-1-1 is the representation of 117 with the operations +,-,*,^ and factorial requiring the fewest 1's.

O. M. Cain, The Exceptional Selfcondensability of Powers of Five, arXiv:1910.13829 [Math.HO], 2019.

Cf. A025280, A306560, A323727, A091334.

import math
delta_bound = 10
limit = 8*2**delta_bound
log_limit = math.log(limit)
def factorial(n):
  if n <= 1: return 1
  return n * factorial(n-1)
def condensings(a, b):
  result = []
  # Addition
  if a+b < limit: result.append(a+b)
  # Subtraction
  if a > b: result.append(a-b)
  # Multiplication
  if a*b < limit: result.append(a*b)
  # Division
  if a % b == 0: result.append(a//b)
  # Exponentiation
  if b*math.log(a) < log_limit: result.append(a**b)
  for n in result:
    if 2 < n < 10:
      fac = factorial(n)
      if fac < limit: result.append(fac)
  return result
# Create delta bound.
# "delta(n) = k" means k 1's are required to build up
# n from the operations in the 'condensings' function.
delta = dict()
delta[1] = 1
# Create inverse map.
delta_inv = {i:[] for i in range(1, delta_bound)}
for a in delta: delta_inv[delta[a]].append(a)
# Calculate delta.
for D in range(2, delta_bound):
  for A in range(1, D):
    B = D - A
    for a in delta_inv[A]:
      for b in delta_inv[B]:
        for c in condensings(a, b):
          if c >= limit: continue
          if c not in delta:
            delta[c] = D
            delta_inv[D].append(c)
a = 1
while a < limit:
  if not a in delta: break
  print(a, delta[a])
  a += 1

cp's OEIS Frontend

A319975 Smallest number of complexity n with respect to the operations {1, shift, multiply}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A360269 Least sum of 2's and 3's required to build n using +, * and parentheses.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Extensions

A370829 Minimum number of (-1)'s needed to write n, using +, *, ^ and parentheses, disallowing noninteger intermediate values.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Java

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

A329526 Number of 1's required to build n using +, -, *, ^ and factorial.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python