|
%I #6 Apr 11 2012 11:05:34
%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
|
