cp's OEIS Frontend

A091333 Number of 1's required to build n using +, -, *, and parentheses.

%I A091333 #53 Dec 06 2024 11:23:12
%S A091333 1,2,3,4,5,5,6,6,6,7,8,7,8,8,8,8,9,8,9,9,9,10,10,9,10,10,9,10,11,10,
%T A091333 11,10,11,11,11,10,11,11,11,11,12,11,12,12,11,12,12,11,12,12,12,12,12,
%U A091333 11,12,12,12,13,13,12,13,13,12,12,13,13,14,13,13,13,13,12,13,13,13,13,14
%N A091333 Number of 1's required to build n using +, -, *, and parentheses.
%C A091333 Consider an alternate complexity measure b(n) which gives the minimum number of 1's necessary to build n using +, -, *, and / (where this additional operation is strict integer division, defined only for n/d where d|n). It turns out that b(n) coincides with a(n) for all n up to 50221174, see A348069. - _Glen Whitney_, Sep 23 2021
%C A091333 In respect of the previous comment: when creating A362471, where repunits are allowed, we found a difference if we allowed n/d with noninteger (intermediate) results. So, see also A362626. - _Peter Munn_, Apr 29 2023
%H A091333 Janis Iraids, <a href="/A091333/b091333.txt">Table of n, a(n) for n = 1..10000</a>
%H A091333 Juris Cernenoks, Janis Iraids, Martins Opmanis, Rihards Opmanis and Karlis Podnieks, <a href="http://arxiv.org/abs/1409.0446">Integer Complexity: Experimental and Analytical Results II</a>, arXiv:1409.0446 [math.NT], 2014.
%H A091333 Janis Iraids, <a href="/A091333/a091333.c.txt">A C program to compute the sequence</a>
%H A091333 J. Iraids, K. Balodis, J. Cernenoks, M. Opmanis, R. Opmanis and K. Podnieks, <a href="http://arxiv.org/abs/1203.6462">Integer Complexity: Experimental and Analytical Results</a>. arXiv preprint arXiv:1203.6462 [math.NT], 2012. - From _N. J. A. Sloane_, Sep 22 2012
%H A091333 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%e A091333 A091333(23) = 10 because 23 = (1+1+1+1) * (1+1+1) * (1+1) - 1. (Note that 23 is also the smallest index at which A091333 differs from A005245.)
%o A091333 (Python)
%o A091333 from functools import cache
%o A091333 @cache
%o A091333 def f(m):
%o A091333     if m == 0: return set()
%o A091333     if m == 1: return {1}
%o A091333     out = set()
%o A091333     for j in range(1, m//2+1):
%o A091333         for x in f(j):
%o A091333             for y in f(m-j):
%o A091333                 out.update([x + y, x * y])
%o A091333                 if x != y: out.add(abs(x-y))
%o A091333     return out
%o A091333 def aupton(terms):
%o A091333     tocover, alst, n = set(range(1, terms+1)), [0 for i in range(terms)], 1
%o A091333     while len(tocover) > 0:
%o A091333         for k in f(n) - f(n-1):
%o A091333             if k <= terms:
%o A091333                 alst[k-1] = n
%o A091333                 tocover.discard(k)
%o A091333         n += 1
%o A091333     return alst
%o A091333 print(aupton(77)) # _Michael S. Branicky_, Sep 28 2021
%Y A091333 Cf. A005245 (variant using + and *), A025280 (using +, *, and ^), A091334 (using +, -, *, and ^), A348089 (using +, -, *, /, and ^), A348262 (using + and ^).
%Y A091333 Cf. A348069, A362471, A362626.
%K A091333 nonn
%O A091333 1,2
%A A091333 _Jens Voß_, Dec 30 2003