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

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,1

Comments

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.

Links

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

Index to sequences related to the complexity of n.

Formula

|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

Example

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.

Crossrefs

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

Sequence in context: A175793 A244789 A309932 * A058886 A236858 A220661

Adjacent sequences: A363965 A363966 A363967 * A363969 A363970 A363971

Keyword

nonn,base

Author

Bernard Schott, Jun 30 2023

Extensions

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

Status

approved