cp's OEIS Frontend

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

%I A214836 #38 Feb 22 2021 12:41:36
%S A214836 1,1,2,7,18,58,180,613,2076,7270,25752,92918,338432,1246092,4624536,
%T A214836 17290646,65047436,246079536,935484928,3571960668,13692523960,
%U A214836 52675401248,203299385584,786949008100,3054440440486,11884949139900,46351113658232,181153317512536
%N A214836 Number of formula representations of n using addition, multiplication, exponentiation and the constant 1.
%H A214836 Alois P. Heinz, <a href="/A214836/b214836.txt">Table of n, a(n) for n = 1..1000</a>
%H A214836 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 A214836 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 A214836 Wikipedia, <a href="https://en.wikipedia.org/wiki/Postfix_notation">Postfix notation</a>
%H A214836 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%e A214836 a(1) = 1: 1.
%e A214836 a(2) = 1: 11+.
%e A214836 a(3) = 2: 111++, 11+1+.
%e A214836 a(4) = 7: 1111+++, 111+1++, 11+11++, 111++1+, 11+1+1+, 11+11+*, 11+11+^.
%e A214836 a(5) = 18: 11111++++, 1111+1+++, 111+11+++, 1111++1++, 111+1+1++, 111+11+*+, 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+, 11+11+^1+.
%e A214836 All formulas are given in postfix (reverse Polish) notation but other notations would give the same results.
%p A214836 with(numtheory):
%p A214836 a:= proc(n) option remember; `if`(n=1, 1,
%p A214836        add(a(i)*a(n-i), i=1..n-1)+
%p A214836        add(a(d)*a(n/d), d=divisors(n) minus {1, n})+
%p A214836        add(a(root(n, p))*a(p), p=divisors(igcd(seq(i[2],
%p A214836            i=ifactors(n)[2]))) minus {0,1}))
%p A214836     end:
%p A214836 seq(a(n), n=1..40);
%t A214836 a[n_] := a[n] = If[n==1, 1, Sum[a[i]*a[n-i], {i, 1, n-1}] + Sum[a[d]*a[n/d], {d, Divisors[n] ~Complement~ {1, n}}] + Sum[a[n^(1/p)] * a[p], {p, Divisors[GCD @@ Table[i[[2]], {i, FactorInteger[n]}]] ~Complement~ {0, 1}}]]; Array[a, 40] (* _Jean-François Alcover_, Apr 11 2017, translated from Maple *)
%Y A214836 Cf. A025280, A214833, A214843, A217250, A217253.
%K A214836 nonn
%O A214836 1,3
%A A214836 _Alois P. Heinz_, Mar 07 2013