login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A217253 Number of minimal length formulas representing n only using addition, multiplication, exponentiation and the constant 1. 3

%I #25 Feb 22 2021 13:21:18

%S 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 24,96,328,18,36,164,472,4,8,24,80,144,288,224,560,216,72,144,432,56,

%U 8,52,232,72,144,8,16,16,32,48,96,256,512,656,32,20,40,120

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

%H Alois P. Heinz, <a href="/A217253/b217253.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>

%e 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 a(8) = 2: 11+111++^, 11+11+1+^.

%e a(9) = 2: 111++11+^, 11+1+11+^.

%e a(10) = 4: 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 b:= proc(n) option remember; local d, i, l, m, p, t;

%p if n=1 then [1, 1] else l, m:= infinity, 0;

%p for i to n-1 do t:= 1+b(i)[1]+b(n-i)[1];

%p if t=l then m:= m +b(i)[2]*b(n-i)[2]

%p elif t<l then l, m:= t, b(i)[2]*b(n-i)[2] fi od;

%p for d in divisors(n) minus {1, n} do t:= 1+b(d)[1]+b(n/d)[1];

%p if t=l then m:= m +b(d)[2]*b(n/d)[2]

%p elif t<l then l, m:= t, b(d)[2]*b(n/d)[2] fi od;

%p for p in divisors(igcd(seq(i[2], i=ifactors(n)[2])))

%p minus {0, 1} do t:= 1+b(p)[1]+b(root(n, p))[1];

%p if t=l then m:= m +b(p)[2]*b(root(n, p))[2]

%p elif t<l then l, m:= t, b(p)[2]*b(root(n, p))[2] fi od; [l, m]

%p fi

%p end:

%p a:= n-> b(n)[2]:

%p seq(a(n), n=1..100);

%t 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 a[n_] := b[n][[2]];

%t Array[a, 100] (* _Jean-François Alcover_, Mar 22 2017, translated from Maple *)

%Y Cf. A214836, A217250.

%K nonn

%O 1,3

%A _Alois P. Heinz_, Mar 16 2013

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 05:39 EDT 2024. Contains 371235 sequences. (Running on oeis4.)