cp's OEIS Frontend

A214843 Number of formula representations of n using addition, exponentiation and the constant 1.

%I A214843 #33 Feb 22 2021 12:11:28
%S A214843 1,1,2,6,16,48,152,502,1694,5832,20420,72472,260096,942304,3441584,
%T A214843 12658128,46842920,174289108,651610504,2446686568,9222628592,
%U A214843 34886505168,132387975040,503857644160,1922782984688,7355686851696,28203617340756,108368274550664
%N A214843 Number of formula representations of n using addition, exponentiation and the constant 1.
%H A214843 Alois P. Heinz, <a href="/A214843/b214843.txt">Table of n, a(n) for n = 1..1000</a>
%H A214843 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 A214843 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 A214843 Wikipedia, <a href="https://en.wikipedia.org/wiki/Postfix_notation">Postfix notation</a>
%H A214843 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%e A214843 a(1) = 1: 1.
%e A214843 a(2) = 1: 11+.
%e A214843 a(3) = 2: 111++, 11+1+.
%e A214843 a(4) = 6: 1111+++, 111+1++, 11+11++, 111++1+, 11+1+1+, 11+11+^.
%e A214843 a(5) = 16: 11111++++, 1111+1+++, 111+11+++, 1111++1++, 111+1+1++, 111+11+^+, 11+111+++, 11+11+1++, 111++11++, 11+1+11++, 1111+++1+, 111+1++1+, 11+11++1+, 111++1+1+, 11+1+1+1+, 11+11+^1+.
%e A214843 All formulas are given in postfix (reverse Polish) notation but other notations would give the same results.
%p A214843 with(numtheory):
%p A214843 a:= proc(n) option remember; `if`(n=1, 1,
%p A214843        add(a(i)*a(n-i), i=1..n-1)+
%p A214843        add(a(root(n, p))*a(p), p=divisors(igcd(seq(i[2],
%p A214843            i=ifactors(n)[2]))) minus {0, 1}))
%p A214843     end:
%p A214843 seq(a(n), n=1..40);
%t A214843 a[1] = 1; a[n_] := a[n] = Sum[a[i]*a[n-i], {i, 1, n-1}] + Sum[a[n^(1/p)] * a[p], {p, Divisors[GCD @@ FactorInteger[n][[All, 2]]] ~Complement~ {0, 1} } ];
%t A214843 Table[a[n], {n, 1, 40}] (* _Jean-François Alcover_, Nov 06 2017, after _Alois P. Heinz_ *)
%Y A214843 Cf. A213924, A214833, A214836.
%K A214843 nonn
%O A214843 1,3
%A A214843 _Alois P. Heinz_, Mar 08 2013