|
%I #47 Apr 29 2023 08:10:09
%S 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 11,10,11,11,11,10,11,11,11,11,12,11,12,12,11,12,12,11,12,12,12,12,12,
%U 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 Number of 1's required to build n using +, -, *, and parentheses.
%C 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 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 Janis Iraids, <a href="/A091333/b091333.txt">Table of n, a(n) for n = 1..10000</a>
%H 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 Janis Iraids, <a href="/A091333/a091333.c.txt">A C program to compute the sequence</a>
%H 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 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%e 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 (Python)
%o from functools import cache
%o @cache
%o def f(m):
%o if m == 0: return set()
%o if m == 1: return {1}
%o out = set()
%o for j in range(1, m//2+1):
%o for x in f(j):
%o for y in f(m-j):
%o out.update([x + y, x * y])
%o if x != y: out.add(abs(x-y))
%o return out
%o def aupton(terms):
%o tocover, alst, n = set(range(1, terms+1)), [0 for i in range(terms)], 1
%o while len(tocover) > 0:
%o for k in f(n) - f(n-1):
%o if k <= terms:
%o alst[k-1] = n
%o tocover.discard(k)
%o n += 1
%o return alst
%o print(aupton(77)) # _Michael S. Branicky_, Sep 28 2021
%Y Cf. A005245, A025280, A091334, A348069, A362471, A362626.
%K nonn
%O 1,2
%A _Jens Voß_, Dec 30 2003
|
