|
|
A025280
|
|
Complexity of n: number of 1's required to build n using +, * and ^.
|
|
22
|
|
|
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, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
REFERENCES
|
R. K. Guy, Unsolved Problems Number Theory, Sect. F26.
|
|
LINKS
|
|
|
FORMULA
|
|
|
MAPLE
|
with(numtheory):
a:= proc(n) option remember; `if`(n=1, 1, min(
seq(a(i)+a(n-i), i=1..n-1),
seq(a(d)+a(n/d), d=divisors(n) minus {1, n}),
seq(a(root(n, p))+a(p), p=divisors(igcd(seq(i[2],
i=ifactors(n)[2]))) minus {0, 1})))
end:
|
|
MATHEMATICA
|
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 *)
|
|
PROG
|
(Python)
from math import gcd
from sympy import divisors, factorint, integer_nthroot
from functools import cache
@cache
def a(n):
if n == 1: return 1
p = min(a(i)+a(n-1) for i in range(1, n//2+1))
divs, m = divisors(n), n
if len(divs) > 2:
m = min(a(d)+a(n//d) for d in divs[1:len(divs)//2+1])
f = factorint(n)
edivs, e = divisors(gcd(*f.values())), n
if len(edivs) > 1:
e = min(a(integer_nthroot(n, r)[0])+a(r) for r in edivs[1:])
return min(p, m, e)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|