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!)
A274061 Number of 1's required to build n using +, * and concatenation of 1's, where the result of concatenation is interpreted as a binary string. 1
1, 2, 2, 3, 4, 4, 3, 4, 4, 5, 6, 5, 6, 5, 4, 5, 6, 6, 7, 7, 5, 6, 7, 6, 7, 8, 6, 6, 7, 6, 5, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 7, 8, 8, 6, 7, 8, 7, 6, 7, 8, 8, 9, 8, 9, 7, 8, 9, 9, 7, 8, 7, 6, 7, 8, 8, 9, 9, 9, 8, 9, 8, 9, 10, 8, 9, 9, 10, 11, 9, 8, 9, 10, 8, 9, 10, 9, 9, 10, 8, 9, 9, 7, 8, 9, 8, 9, 8, 9, 9 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Like A005245, but concatenation of ones is allowed and their results are treated as binary representations of integers. Hence 3 can be represented as 11, 7 as 111 and so on.

The largest number with complexity n is 2^n-1 (A000225), the concatenation of n 1's. This follows from (2^m-1)(2^n-1) < 2^(m+n)-1 for m, n >= 1.

LINKS

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

Jeremy Tan, Python program

EXAMPLE

n . minimal expression . number of 1's

1...1....................1

2...1+1..................2

3...11...................2

4...11+1.................3

5...11+1+1...............4

6...11*(1+1).............4

7...111..................3

8...111+1................4

9...11*11................4

10..11*11+1..............5

11..11*11+1+1............6

12..11*(11+1)............5

13..11*(11+1)+1..........6

14..111*(1+1)............5

15..1111.................4

16..1111+1...............5

17..1111+1+1.............6

18..11*11*(1+1)..........6

19..11*11*(1+1)+1........7

20..(11+1+1)(11+1).......7

21..111*11...............5

MAPLE

with(numtheory):

a:= proc(n) option remember; (k-> `if`(2^k=n+1, k,

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

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

    end:

seq(a(n), n=1..120);  # Alois P. Heinz, Jun 09 2016

MATHEMATICA

a[n_] := a[n] = Function[k, If[2^k == n+1, k, Min[Table[a[d] + a[n/d], {d, Divisors[n] ~Complement~ {1, n}}], Table[a[i] + a[n-i], {i, 1, n/2}]]]] @ Floor[Log[2, n+1]];

Array[a, 100] (* Jean-Fran├žois Alcover, Mar 27 2017, after Alois P. Heinz *)

CROSSREFS

Cf. A005245, A133344.

Sequence in context: A325954 A243503 A069581 * A284009 A326846 A243220

Adjacent sequences:  A274058 A274059 A274060 * A274062 A274063 A274064

KEYWORD

nonn

AUTHOR

Jeremy Tan, Jun 08 2016

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 30 23:44 EDT 2020. Contains 337440 sequences. (Running on oeis4.)