A133344 -id:A133344 - cp's OEIS frontend

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

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 = +, -, *, /.

A133374 Difference between largest number of complexity n in the sense of A005245 and smallest number of complexity n in the sense of A005245.

Original entry on oeis.org

0, 0, 0, 0, 1, 2, 2, 7, 10, 14, 31, 40, 61, 103, 154, 217, 319, 550, 709, 1111, 1720, 2233, 3655, 5338, 7310, 11683, 16804, 22477, 35083, 52750, 68653, 106291, 161860, 214597, 320695, 486244, 652549, 981235, 1495324, 1962505, 2984647, 4541086

Offset: 1

Jonathan Vos Post, Oct 28 2007

nonn

Complexity of n: number of 1's required to build n using + and *. The complexity of a number has been defined in several different ways by different authors. See the Index to the OEIS for other definitions.

			n A000792(n)-A005520(n) = a(n)
1 1 - 1 = 0.
2 2 - 2 = 0.
3 3 - 3 = 0.
4 4 - 4 = 0.
5 6 - 5 = 1.
6 9 - 7 = 2.
7 12 - 10 = 2.
8 18 - 11 = 7.
9 27 - 17 = 10.
10 36 - 22 = 14.
11 54 - 23 = 31.
12 81 - 41 = 40.
13 108 - 47 = 61.
14 162 - 59 = 103.
15 243 - 89 = 154.
16 324 - 107 = 217.
17 486 - 167 = 319.
18 729 - 179 = 550.
19 972 - 263 = 709.
20 1458 - 347 = 1111. etc.

Janis Iraids, Table of n, a(n) for n = 1..89
Eric Weisstein's World of Mathematics, Integer Complexity

Cf. A000792, A005245, A005520, A133344.

a(n) = A000792(n) - A005520(n).

Corrected and extended by Janis Iraids, Apr 20 2011

A274061 Number of 1's required to build n using +, * and concatenation of 1's, where the result of concatenation is interpreted as a binary string.

Original entry on oeis.org

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

Offset: 1

Jeremy Tan, Jun 08 2016

nonn

Like A005245, but concatenation of ones is allowed and their results are treated as binary representations of integers. Hence 3 can be represented as 11, 7 as 111 and so on.

The largest number with complexity n is 2^n-1 (A000225), the concatenation of n 1's. This follows from (2^m-1)(2^n-1) < 2^(m+n)-1 for m, n >= 1.

			n . minimal expression . number of 1's
1...1....................1
2...1+1..................2
3...11...................2
4...11+1.................3
5...11+1+1...............4
6...11*(1+1).............4
7...111..................3
8...111+1................4
9...11*11................4
10..11*11+1..............5
11..11*11+1+1............6
12..11*(11+1)............5
13..11*(11+1)+1..........6
14..111*(1+1)............5
15..1111.................4
16..1111+1...............5
17..1111+1+1.............6
18..11*11*(1+1)..........6
19..11*11*(1+1)+1........7
20..(11+1+1)(11+1).......7
21..111*11...............5

Alois P. Heinz, Table of n, a(n) for n = 1..20000
Jeremy Tan, Python program

Cf. A005245, A133344.

with(numtheory):
a:= proc(n) option remember; (k-> `if`(2^k=n+1, k,
      min(seq(a(d)+a(n/d), d=divisors(n) minus {1, n}),
          seq(a(i)+a(n-i), i=1..n/2))))(ilog2(n+1))
    end:
seq(a(n), n=1..120);  # Alois P. Heinz, Jun 09 2016

a[n_] := a[n] = Function[k, If[2^k == n+1, k, Min[Table[a[d] + a[n/d], {d, Divisors[n] ~Complement~ {1, n}}], Table[a[i] + a[n-i], {i, 1, n/2}]]]] @ Floor[Log[2, n+1]];
Array[a, 100] (* Jean-François Alcover, Mar 27 2017, after Alois P. Heinz *)

A363968 Least number of 1's needed to represent n using only additions +, subtractions -, multiplications *, divisions /, concatenations # and parentheses ().

Original entry on oeis.org

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

Offset: 0

Bernard Schott, Jun 30 2023

Fractions are not allowed as intermediate results.
The unique difference with A362471 is that concatenation is here allowed; in fact, in A362471, concatenation is only allowed for getting repunits as 111 = 1#1#1 but not for getting other integers.
Also, for example, the concatenation of 5 and -3 is not possible, so it should not be interpreted as 5-3 = 2.
The first differences with A362471 in the data appear at n = 16, 19, 20, 21, 29, ... see Example section.

			For n = 16, 16 = 1 # ((1+1)*(1+1+1)), so a(16) = 6 while A362471(16) = 7.
For n = 19, 19 = 1 # (11-1-1), so a(19) = 5 while A362471(19) = 6.
For n = 20, 20 = (1+1) # (1-1), so a(20) = 4 while A362471(20) = 5.
For n = 31, 31 = (1+1+1) # (1), so a(31) = 4 while A362471(31) = 7.
For n = 43, 43 = (1+1)*((1+1) # (1)) + 1, so a(43) = 6 while A362471(43) = 7.

Michael S. Branicky, Table of n, a(n) for n = 0..10000.
Index to sequences related to the complexity of n.

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

|a(n+1) - a(n)| <= 1; improved by Pontus von Brömssen, Jun 30 2023
a(n) <= A362471(n).
a(n) <= Sum_{k=1..m} a(dk), where d1d2..dm are the decimal digits of n. - Michael S. Branicky, Jun 30 2023

a(72) and beyond from Michael S. Branicky, Jun 30 2023

cp's OEIS Frontend

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

A133374 Difference between largest number of complexity n in the sense of A005245 and smallest number of complexity n in the sense of A005245.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A274061 Number of 1's required to build n using +, * and concatenation of 1's, where the result of concatenation is interpreted as a binary string.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A363968 Least number of 1's needed to represent n using only additions +, subtractions -, multiplications *, divisions /, concatenations # and parentheses ().

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions