|
%I #35 Feb 22 2021 13:21:35
%S 1,3,5,7,9,9,11,9,9,11,13,13,15,15,15,11,13,13,15,15,17,17,19,15,13,
%T 15,11,13,15,17,19,13,15,17,19,13,15,17,19,19,21,21,23,21,19,21,23,17,
%U 15,17,19,19,21,15,17,17,19,19,21,21,23,23,21,13,15,17,19
%N Minimal length of formulas representing n only using addition, multiplication, exponentiation and the constant 1.
%H Alois P. Heinz, <a href="/A217250/b217250.txt">Table of n, a(n) for n = 1..10000</a>
%H Edinah K. Ghang and Doron Zeilberger, <a href="https://arxiv.org/abs/1303.0885">Zeroless Arithmetic: Representing Integers ONLY using ONE</a>, arXiv:1303.0885 [math.CO], 2013.
%H Shalosh B. Ekhad, <a href="http://www.math.rutgers.edu/~zeilberg/tokhniot/oArithFormulas2">Everything About Formulas Representing Integers Using Additions, Multiplication and Exponentiation for integers from 1 to 8000</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Postfix_notation">Postfix notation</a>
%H <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%F a(n) = 2*A025280(n)-1.
%e a(6) = 9: there are 58 formulas representing 6 only using addition, multiplication, exponentiation and the constant 1. The formulas with minimal length 9 are: 11+111++*, 11+11+1+*, 111++11+*, 11+1+11+*.
%e a(8) = 9: 11+111++^, 11+11+1+^.
%e a(9) = 9: 111++11+^, 11+1+11+^.
%e a(10) = 11: 1111++11+^+, 111+1+11+^+, 111++11+^1+, 11+1+11+^1+.
%e All formulas are given in postfix (reverse Polish) notation but other notations would give the same results.
%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/2),
%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..120);
%t a[n_] := a[n] = 1 + If[n==1, 0, Min[Table[a[i] + a[n-i], {i, 1, n/2}] ~Join~ Table[a[d] + a[n/d], {d, Divisors[n] ~Complement~ {1, n}}] ~Join~ Table[a[Floor[n^(1/p)]] + a[p], {p, Divisors[GCD @@ FactorInteger[n][[ All, 2]]] ~Complement~ {0, 1}}]]];
%t Array[a, 120] (* _Jean-François Alcover_, Mar 22 2017, translated from Maple *)
%Y Cf. A025280, A213923, A213924, A214836, A217253.
%K nonn
%O 1,2
%A _Alois P. Heinz_, Mar 16 2013
|
