|
%I #19 Mar 22 2017 08:12:19
%S 1,3,5,7,9,11,13,9,9,11,13,15,17,19,21,11,13,15,17,19,21,23,25,21,13,
%T 15,11,13,15,17,19,13,15,17,19,15,17,19,21,23,23,25,23,25,25,27,29,25,
%U 17,19,21,23,25,23,25,27,27,27,25,27,29,31,27,13,15,17,19,21,23,25,27,23,23,25,27,29,31,33
%N Minimal lengths of formulas representing n only using addition, exponentiation and the constant 1.
%H Alois P. Heinz, <a href="/A213924/b213924.txt">Table of n, a(n) for n = 1..10000</a>
%H Shalosh B. Ekhad, <a href="http://www.math.rutgers.edu/~zeilberg/tokhniot/oArithFormulas3">Everything About Formulas Representing Integers Using Additions and Exponentiation for integers from 1 to 8000</a>.
%H Edinah K. Ghang, Doron Zeilberger, <a href="http://arxiv.org/abs/1303.0885v1">Zeroless Arithmetic: Representing Integers ONLY using ONE</a>, arXiv:1303.0885v1 [math.CO], 2013
%e There are 502 different formulas for n=8. Two of them have shortest length 9: 11+111++^, 11+11+1+^. Thus a(8) = 9.
%p with(numtheory):
%p a:= proc(n) option remember; 1+ `if`(n=1, 0, min(
%p seq(a(i)+a(n-i), i=1..n-1),
%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 12 2013
%t a[n_] := a[n] = 1 + If[n==1, 0, Min[Table[a[i]+a[n-i], {i, 1, n-1}], Table[ a[Floor[n^(1/p)]] + a[p], {p, Divisors[GCD @@ FactorInteger[n][[All, 2]]] ~Complement~ {0, 1}}]]]; Array[a, 100] (* _Jean-François Alcover_, Mar 22 2017, after _Alois P. Heinz_ *)
%Y Cf. A003037, A025280, A213923, A214843.
%K nonn
%O 1,2
%A _Jonathan Vos Post_, Mar 06 2013
|
