The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A118121 Roman numeral complexity of n. 1

%I

%S 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,

%T 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,

%U 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

%N Roman numeral complexity of n.

%C 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.

%H <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>

%e a(n) < A006968(n) for these examples. Here "<" means less in letter count:

%e 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].

%Y Cf. A005245, A006968, A092196.

%K base,easy,nonn

%O 1,2

%A _Jonathan Vos Post_, May 12 2006

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 16 15:01 EDT 2021. Contains 347472 sequences. (Running on oeis4.)