login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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
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, 24, 96, 328, 18, 36, 164, 472, 4, 8, 24, 80, 144, 288, 224, 560, 216, 72, 144, 432, 56, 8, 52, 232, 72, 144, 8, 16, 16, 32, 48, 96, 256, 512, 656, 32, 20, 40, 120 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Edinah K. Ghang, Doron Zeilberger, Zeroless Arithmetic: Representing Integers ONLY using ONE, arXiv:1303.0885 [math.CO], 2013

Shalosh B. Ekhad, Everything About Formulas Representing Integers Using Additions, Multiplication and Exponentiation for integers from 1 to 8000

Wikipedia, Postfix notation

Index to sequences related to the complexity of n

EXAMPLE

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+*.

a(8) = 2: 11+111++^, 11+11+1+^.

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

a(10) = 4: 1111++11+^+, 111+1+11+^+, 111++11+^1+, 11+1+11+^1+.

All formulas are given in postfix (reverse polish) notation but other notations would give the same results.

MAPLE

with(numtheory):

b:= proc(n) option remember; local d, i, l, m, p, t;

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

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

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

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

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

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

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

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

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

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

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

      fi

    end:

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

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

MATHEMATICA

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}];

a[n_] := b[n][[2]];

Array[a, 100] (* Jean-Fran├žois Alcover, Mar 22 2017, translated from Maple *)

CROSSREFS

Cf. A214836, A217250.

Sequence in context: A013092 A174311 A220396 * A268837 A104310 A301325

Adjacent sequences:  A217250 A217251 A217252 * A217254 A217255 A217256

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Mar 16 2013

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 27 02:49 EDT 2020. Contains 337380 sequences. (Running on oeis4.)