|
%I #29 Mar 24 2024 10:48:50
%S 1,2,3,4,5,5,6,5,5,6,7,7,8,8,8,6,7,7,8,8,9,9,10,8,7,8,6,7,8,9,10,7,8,
%T 9,10,7,8,9,10,10,11,11,12,11,10,11,12,9,8,9,10,10,11,8,9,9,10,10,11,
%U 11,12,12,11,7,8,9,10,11,12,12,13,9,10,10,10,11,12,11,12,11,7,8,9,10,11,12,11
%N Complexity of n: number of 1's required to build n using +, * and ^.
%D R. K. Guy, Unsolved Problems Number Theory, Sect. F26.
%H Alois P. Heinz, <a href="/A025280/b025280.txt">Table of n, a(n) for n = 1..10000</a>
%H R. K. Guy, <a href="http://www.jstor.org/stable/2323338">Some suspiciously simple sequences</a>, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.
%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, 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>
%F a(n) = A005208(n) + 1.
%p with(numtheory):
%p a:= proc(n) option remember; `if`(n=1, 1, min(
%p seq(a(i)+a(n-i), i=1..n-1),
%p seq(a(d)+a(n/d), d=divisors(n) minus {1, n}),
%p seq(a(root(n, p))+a(p), p=divisors(igcd(seq(i[2],
%p i=ifactors(n)[2]))) minus {0,1})))
%p end:
%p seq(a(n), n=1..100); # _Alois P. Heinz_, Mar 08 2013
%t root[x_, n_] := With[{f = FactorInteger[x]}, Times @@ (f[[All, 1]]^(f[[All, 2]]/n))]; Clear[a]; a[n_] := a[n] = If[n == 1, 1, Min[Table[a[i] + a[n-i], {i, 1, n-1}], Table[a[d] + a[n/d], {d, Divisors[n][[2 ;; -2]]}], Table[a[root[n, p]] + a[p], {p, DeleteCases[Divisors[GCD @@ FactorInteger[n][[All, 2]]], 0|1]}]]]; Table[a[n], {n, 1, 100}] (* _Jean-François Alcover_, Mar 12 2014, after _Alois P. Heinz_ *)
%o (Python)
%o from math import gcd
%o from sympy import divisors, factorint, integer_nthroot
%o from functools import cache
%o @cache
%o def a(n):
%o if n == 1: return 1
%o p = min(a(i)+a(n-1) for i in range(1, n//2+1))
%o divs, m = divisors(n), n
%o if len(divs) > 2:
%o m = min(a(d)+a(n//d) for d in divs[1:len(divs)//2+1])
%o f = factorint(n)
%o edivs, e = divisors(gcd(*f.values())), n
%o if len(edivs) > 1:
%o e = min(a(integer_nthroot(n, r)[0])+a(r) for r in edivs[1:])
%o return min(p, m, e)
%o print([a(n) for n in range(1, 88)]) # _Michael S. Branicky_, Mar 24 2024 after _Alois P. Heinz_
%Y Cf. A003037, A005245, A005520, A005208.
%K nonn
%O 1,2
%A _N. J. A. Sloane_, _David W. Wilson_
|
