cp's OEIS Frontend

A133344 Complexity of the number n, counting 1's and built using +, *, ^ and # representing concatenation.

%I A133344 #17 Nov 06 2013 19:09:12
%S A133344 1,2,3,4,5,5,6,5,5,6,2,3,4,5,6,6,7,6,6,7,3,4,5,5,6,6,6,7,7,8,4,5,5,6,
%T A133344 7,6,7,8,7,8,5,5,6,6,7,7,8,7,8,8,6,7,7,8,7,8,9,9,9,8,6,6,6,7,8,7,8,8,
%U A133344 8,9,7,8,8,8,9,10,8,9,10,10,6,7,8,7,8,8
%N A133344 Complexity of the number n, counting 1's and built using +, *, ^ and # representing concatenation.
%C A133344 The complexity of an integer n is the least number of 1's needed to represent it using only additions, multiplications, exponentiation and parentheses. This allows juxtaposition of numbers to form larger integers, so for example, 2 = 1+1 has complexity 2, but unlike A003037, so does 11 = 1#1 (concatenating two numbers is an allowed operation). Similarly a(111) = 3. The complexity of a number has been defined in several different ways by different authors. See the Index to the OEIS for other definitions.
%H A133344 Alois P. Heinz, <a href="/A133344/b133344.txt">Table of n, a(n) for n = 1..10000</a>
%H A133344 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%e A133344 An example (usually nonunique) of the derivation of the first 22 values.
%e A133344 a(1) = 1, the number of 1's in "1."
%e A133344 a(2) = 2, the number of 1's in "1+1 = 2."
%e A133344 a(3) = 3, the number of 1's in "1+1+1 = 3."
%e A133344 a(4) = 4, the number of 1's in "1+1+1+1 = 4."
%e A133344 a(5) = 5, the number of 1's in "1+1+1+1+1 = 5."
%e A133344 a(6) = 5, since there are 5 1's in "((1+1)*(1+1+1)) = 6."
%e A133344 a(7) = 6, since there are 6 1's in "1+(((1+1)*(1+1+1))) = 7."
%e A133344 a(8) = 5, since there are 5 1's in "(1+1)^(1+1+1) = 8."
%e A133344 a(9) = 5, since there are 5 1's in "(1+1+1)^(1+1) = 9."
%e A133344 a(10) = 6 since there are 6 1's in "1+((1+1+1)^(1+1)) = ten.
%e A133344 a(11) = 2 since there are 2 1's in "1#1 = eleven."
%e A133344 a(12) = 3 since there are 3 1's in "1+(1#1) = twelve."
%e A133344 a(13) = 4 since there are 4 1's in "1+1+(1#1) = thirteen."
%e A133344 a(14) = 5 since there are 5 1's in "1+1+1+(1#1) = fourteen."
%e A133344 a(16) = 6 since there are 6 1's in "(1+1+1+1)^(1+1)."
%e A133344 a(17) = 7 since there are 7 1's in "1+((1+1+1+1)^(1+1))."
%e A133344 a(18) = 6 since there are 6 1's in "1#((1+1)^(1+1+1))."
%e A133344 a(19) = 6 since there are 6 1's in "1#((1+1+1)^(1+1))."
%e A133344 a(20) = 7 since there are 7 1's in "(1#1)+((1+1+1)^(1+1))."
%e A133344 a(21) = 3 since there are 3 1's in "(1+1)#1."
%e A133344 a(22) = 4 since 22 = (1+1)*(1#1) = (1#1)+(1#1) = (1+1)#(1+1).
%p A133344 with(numtheory):
%p A133344 a:= proc(n) option remember; local r; `if`(n=1, 1, min(
%p A133344        seq(a(i)+a(n-i), i=1..n-1),
%p A133344        seq(a(d)+a(n/d), d=divisors(n) minus {1, n}),
%p A133344        seq(`if`(cat("", n)[i+1]<>"0", a(iquo(n, 10^(length(n)-i),
%p A133344            'r'))+a(r), NULL), i=1..length(n)-1),
%p A133344        seq(a(root(n, p))+a(p), p=divisors(igcd(seq(i[2],
%p A133344            i=ifactors(n)[2]))) minus {0, 1})))
%p A133344     end:
%p A133344 seq(a(n), n=1..120);  # _Alois P. Heinz_, Nov 06 2013
%Y A133344 Cf. A003037, A025280, A005520, A005245, A005421, A117618.
%K A133344 base,nonn
%O A133344 1,2
%A A133344 _Jonathan Vos Post_, Oct 20 2007