login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A025280 Complexity of n: number of 1's required to build n using +, * and ^. 16
1, 2, 3, 4, 5, 5, 6, 5, 5, 6, 7, 7, 8, 8, 8, 6, 7, 7, 8, 8, 9, 9, 10, 8, 7, 8, 6, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 10, 11, 11, 12, 11, 10, 11, 12, 9, 8, 9, 10, 10, 11, 8, 9, 9, 10, 10, 11, 11, 12, 12, 11, 7, 8, 9, 10, 11, 12, 12, 13, 9, 10, 10, 10, 11, 12, 11, 12, 11, 7, 8, 9, 10, 11, 12, 11 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

REFERENCES

R. K. Guy, Unsolved Problems Number Theory, Sect. F26.

LINKS

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

R. K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.

J. Iraids, K. Balodis, J. Cernenoks, M. Opmanis, R. Opmanis and K. Podnieks, Integer Complexity: Experimental and Analytical Results. arXiv preprint arXiv:1203.6462, 2012. - From N. J. A. Sloane, Sep 22 2012

Index to sequences related to the complexity of n

FORMULA

a(n) = A005208(n) + 1.

MAPLE

with(numtheory):

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

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

       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..100);  # Alois P. Heinz, Mar 08 2013

MATHEMATICA

root[x_, n_] := With[{f = FactorInteger[x]}, Times @@ (f[[All, 1]]^(f[[All, 2]]/n))]; Clear[a]; a[n_] := a[n] = If[n == 1, 1, Min[Table[a[i] + a[n-i], {i, 1, n-1}], Table[a[d] + a[n/d], {d, Divisors[n][[2 ;; -2]]}], Table[a[root[n, p]] + a[p], {p, DeleteCases[Divisors[GCD @@ FactorInteger[n][[All, 2]]], 0|1]}]]]; Table[a[n], {n, 1, 100}] (* Jean-Fran├žois Alcover, Mar 12 2014, after Alois P. Heinz *)

CROSSREFS

Cf. A003037, A005245, A005520, A005208.

Sequence in context: A154940 A133344 A091334 * A096365 A319412 A200311

Adjacent sequences:  A025277 A025278 A025279 * A025281 A025282 A025283

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, David W. Wilson

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 January 17 19:58 EST 2019. Contains 319251 sequences. (Running on oeis4.)