A217250 Minimal length of formulas representing n only using addition, multiplication, exponentiation and the constant 1.
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
Offset: 1
Keywords
Examples
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.
Links
- Alois P. Heinz, Table of n, a(n) for n = 1..10000
- Edinah K. Ghang and 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
Programs
-
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 *)
Formula
a(n) = 2*A025280(n)-1.