cp's OEIS Frontend

A217250 Minimal length of formulas representing n only using addition, multiplication, exponentiation and the constant 1.

%I A217250 #35 Feb 22 2021 13:21:35
%S A217250 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 A217250 15,11,13,15,17,19,13,15,17,19,13,15,17,19,19,21,21,23,21,19,21,23,17,
%U A217250 15,17,19,19,21,15,17,17,19,19,21,21,23,23,21,13,15,17,19
%N A217250 Minimal length of formulas representing n only using addition, multiplication, exponentiation and the constant 1.
%H A217250 Alois P. Heinz, <a href="/A217250/b217250.txt">Table of n, a(n) for n = 1..10000</a>
%H A217250 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 A217250 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 A217250 Wikipedia, <a href="https://en.wikipedia.org/wiki/Postfix_notation">Postfix notation</a>
%H A217250 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%F A217250 a(n) = 2*A025280(n)-1.
%e A217250 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 A217250 a(8) = 9: 11+111++^, 11+11+1+^.
%e A217250 a(9) = 9: 111++11+^, 11+1+11+^.
%e A217250 a(10) = 11: 1111++11+^+, 111+1+11+^+, 111++11+^1+, 11+1+11+^1+.
%e A217250 All formulas are given in postfix (reverse Polish) notation but other notations would give the same results.
%p A217250 with(numtheory):
%p A217250 a:= proc(n) option remember; 1+ `if`(n=1, 0, min(
%p A217250       seq(a(i)+a(n-i), i=1..n/2),
%p A217250       seq(a(d)+a(n/d), d=divisors(n) minus {1, n}),
%p A217250       seq(a(root(n, p))+a(p), p=divisors(igcd(seq(i[2],
%p A217250           i=ifactors(n)[2]))) minus {0, 1})))
%p A217250     end:
%p A217250 seq(a(n), n=1..120);
%t A217250 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 A217250 Array[a, 120] (* _Jean-François Alcover_, Mar 22 2017, translated from Maple *)
%Y A217250 Cf. A025280, A213923, A213924, A214836, A217253.
%K A217250 nonn
%O A217250 1,2
%A A217250 _Alois P. Heinz_, Mar 16 2013