A118121 Roman numeral complexity of n.

1, 2, 3, 2, 1, 2, 3, 4, 2, 1, 2, 3, 4, 3, 2, 3, 4, 4, 3, 2, 3, 4, 5, 4, 3, 4, 5, 5, 4, 3, 4, 5, 5, 5, 4, 4, 5, 5, 5, 2, 3, 4, 5, 4, 3, 4, 5, 6, 4, 1, 2, 3, 4, 3, 2, 3, 4, 5, 3, 2, 3, 4, 5, 4, 3, 4, 5, 6, 4, 3, 4, 5, 6, 5, 4, 5, 5, 6, 5, 4, 4, 5, 6, 5, 5, 6, 6, 6, 6, 2, 3, 4, 5, 4, 3, 4, 5, 6, 4, 1, 2, 3

Offset

1,2

Comments

The least number of letters {I, V, X, L, C, D, M} needed to represent n by an expression with conventional Roman numerals, addition, multiplication and parentheses. a(n) <= A006968(n) and a(n) <= A005245(n). Conventional Roman numerals are very efficient at reducing complexity from number of letters in "old style" Roman numerals (A092196) and more primitive representations. In all but two examples shown (38, 88) the use of {+,*} reduces the representation by a single symbol (counting + and *); in these two it saves 2 symbols. In an alternate history, complexity theory and minimum description length could have been invented by Gregorius Catin.

Links

Table of n, a(n) for n=1..102.

Index to sequences related to the complexity of n

Example

a(n) < A006968(n) for these examples. Here "<" means less in letter count:
a(18) = 4 [IX + IX < XVIII]; a(28) = 5 [XIV * II < XXVIII]; a(33) = 5 [XI * III < XXXIII]; a(36) = 4 [VI * VI < XXXVI]; a(37) = 5 [VI * VI + I < XXXVII]; a(38) = 5 [XIX * II < XXXVIII]; a(77) = 5 [XI * VII < LXXVII]; a(78) = 6 [XIII * VI < LXXVIII]; a(81) = 4 [IX * IX < LXXXI]; a(82) = 5 [XLI * II < LXXXII]; a(83) = 6 [XLI * II + I < LXXXIII]; a(84) = 5 [XX * IV < LXXXIV]; a(87) = 6 [IX * IX + VI < LXXXVII]; a(88) = 6 [XI * VIII < LXXXVIII].

Crossrefs

Cf. A005245, A006968, A092196.

Sequence in context: A269624 A098236 A152978 * A006968 A058207 A105969

Adjacent sequences: A118118 A118119 A118120 * A118122 A118123 A118124

Keyword

base,easy,nonn

Author

Jonathan Vos Post, May 12 2006

Status

approved