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

Author

Bernard Schott, Jun 30 2023

Keywords

• nonn
• base

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.

Examples

			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.
		

Links

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

Crossrefs

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

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

Extensions

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