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!)
A217250 Minimal length of formulas representing n only using addition, multiplication, exponentiation and the constant 1. 3
1, 3, 5, 7, 9, 9, 11, 9, 9, 11, 13, 13, 15, 15, 15, 11, 13, 13, 15, 15, 17, 17, 19, 15, 13, 15, 11, 13, 15, 17, 19, 13, 15, 17, 19, 13, 15, 17, 19, 19, 21, 21, 23, 21, 19, 21, 23, 17, 15, 17, 19, 19, 21, 15, 17, 17, 19, 19, 21, 21, 23, 23, 21, 13, 15, 17, 19 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

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

FORMULA

a(n) = 2*A025280(n)-1.

EXAMPLE

a(6) = 9: there are 58 formulas representing 6 only using addition, multiplication, exponentiation and the constant 1. The formulas with minimal length 9 are: 11+111++*, 11+11+1+*, 111++11+*, 11+1+11+*.

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

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

a(10) = 11: 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):

a:= proc(n) option remember; 1+ `if`(n=1, 0, min(

      seq(a(i)+a(n-i), i=1..n/2),

      seq(a(d)+a(n/d), d=divisors(n) minus {1, n}),

      seq(a(root(n, p))+a(p), p=divisors(igcd(seq(i[2],

          i=ifactors(n)[2]))) minus {0, 1})))

    end:

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

MATHEMATICA

a[n_] := a[n] = 1 + If[n==1, 0, Min[Table[a[i] + a[n-i], {i, 1, n/2}] ~Join~ Table[a[d] + a[n/d], {d, Divisors[n] ~Complement~ {1, n}}] ~Join~ Table[a[Floor[n^(1/p)]] + a[p], {p, Divisors[GCD @@ FactorInteger[n][[ All, 2]]] ~Complement~ {0, 1}}]]];

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

CROSSREFS

Cf. A025280, A213923, A213924, A214836, A217253.

Sequence in context: A274988 A265509 A265527 * A213923 A218452 A007731

Adjacent sequences:  A217247 A217248 A217249 * A217251 A217252 A217253

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 April 6 15:05 EDT 2020. Contains 333276 sequences. (Running on oeis4.)