cp's OEIS Frontend

A217253 Number of minimal length formulas representing n only using addition, multiplication, exponentiation and the constant 1.

%I A217253 #25 Feb 22 2021 13:21:18
%S A217253 1,1,2,7,18,4,8,2,2,4,12,36,72,16,72,14,28,4,8,8,48,24,48,8,18,36,4,8,
%T A217253 24,96,328,18,36,164,472,4,8,24,80,144,288,224,560,216,72,144,432,56,
%U A217253 8,52,232,72,144,8,16,16,32,48,96,256,512,656,32,20,40,120
%N A217253 Number of minimal length formulas representing n only using addition, multiplication, exponentiation and the constant 1.
%H A217253 Alois P. Heinz, <a href="/A217253/b217253.txt">Table of n, a(n) for n = 1..10000</a>
%H A217253 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 A217253 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 A217253 Wikipedia, <a href="https://en.wikipedia.org/wiki/Postfix_notation">Postfix notation</a>
%H A217253 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%e A217253 a(6) = 4: there are 58 formulas representing 6 only using addition, multiplication, exponentiation and the constant 1. The 4 formulas with minimal length 9 are: 11+111++*, 11+11+1+*, 111++11+*, 11+1+11+*.
%e A217253 a(8) = 2: 11+111++^, 11+11+1+^.
%e A217253 a(9) = 2: 111++11+^, 11+1+11+^.
%e A217253 a(10) = 4: 1111++11+^+, 111+1+11+^+, 111++11+^1+, 11+1+11+^1+.
%e A217253 All formulas are given in postfix (reverse Polish) notation but other notations would give the same results.
%p A217253 with(numtheory):
%p A217253 b:= proc(n) option remember; local d, i, l, m, p, t;
%p A217253       if n=1 then [1, 1] else l, m:= infinity, 0;
%p A217253         for i to n-1 do  t:=  1+b(i)[1]+b(n-i)[1];
%p A217253           if t=l then    m:= m +b(i)[2]*b(n-i)[2]
%p A217253         elif t<l then l, m:= t, b(i)[2]*b(n-i)[2] fi od;
%p A217253         for d in divisors(n) minus {1, n} do t:= 1+b(d)[1]+b(n/d)[1];
%p A217253           if t=l then    m:= m +b(d)[2]*b(n/d)[2]
%p A217253         elif t<l then l, m:= t, b(d)[2]*b(n/d)[2] fi od;
%p A217253         for p in divisors(igcd(seq(i[2], i=ifactors(n)[2])))
%p A217253           minus {0, 1} do t:= 1+b(p)[1]+b(root(n, p))[1];
%p A217253           if t=l then    m:= m +b(p)[2]*b(root(n, p))[2]
%p A217253         elif t<l then l, m:= t, b(p)[2]*b(root(n, p))[2] fi od; [l, m]
%p A217253       fi
%p A217253     end:
%p A217253 a:= n-> b(n)[2]:
%p A217253 seq(a(n), n=1..100);
%t A217253 b[1] = {1, 1}; b[n_] := b[n] = Module[{d, i, l, m, p, t}, {l, m} = { Infinity, 0}; For[i=1, i <= n-1, i++, t = 1 + b[i][[1]] + b[n - i][[1]]; Which[t==l, m = m + b[i][[2]]*b[n-i][[2]], t<l, {l, m} = {t, b[i][[2]] * b[n-i][[2]]}]]; Do[t = 1 + b[d][[1]] + b[n/d][[1]]; Which[t==l, m = m + b[d][[2]]*b[n/d][[2]], t<l, {l, m} = {t, b[d][[2]]*b[n/d][[2]] }], {d, Divisors[n] ~Complement~ {1, n}}]; Do[t = 1 + b[p][[1]] + b[Floor[ n^(1/p)]][[1]]; Which[t==l, m = m + b[p][[2]]*b[Floor[n^(1/p)]][[2]], t<l, {l, m} = {t, b[p][[2]]*b[Floor[n^(1/p)]][[2]]}], {p, Divisors[ GCD @@ FactorInteger[n][[ All, 2]]] ~Complement~ {0, 1}}]; {l, m}];
%t A217253 a[n_] := b[n][[2]];
%t A217253 Array[a, 100] (* _Jean-François Alcover_, Mar 22 2017, translated from Maple *)
%Y A217253 Cf. A214836, A217250.
%K A217253 nonn
%O A217253 1,3
%A A217253 _Alois P. Heinz_, Mar 16 2013