From: "Tim Peters" <tim.one(AT)comcast.net>

About sequences A005421, A005245, A005520
-----------------------------------------

I'm working on the release of Python 2.4, and every now and
again pick a "more" sequence at random as a source of interesting
implementation stress tests 

Sequence A005421 is the following:
>
> %S A005421 1,1,1,1,2,3,2,6,6,7,14,16,20,34,42,56,84,108,152,214,295,
> %T A005421 398,569,763,1094,1475,2058,2878,3929,5493,7669,10501,14707,
> %U A005421
20476,28226,39287,54817,75619,105584,146910,203294,283764,394437,547485,7638
21,1061367
> %N A005421 Number of numbers of complexity n.
> %D A005421 D. A. Rawsthorne, How many 1's are needed?, Fib. Quart. 27
(1989), 14-17. ....
>

Eric Weisstein's page

    http://mathworld.wolfram.com/IntegerComplexity.html

gave more than enough to understand it:

    The complexity of an integer n is the least number of 1s needed to
    represent it using only additions, multiplications, and parentheses.

This does not allow juxtaposition of 1's to form larger integers, so, for
example,

    2 = 1+1

has complexity 2, but 11 does not ("pasting together" two 1's is not an
allowed operation).  There are other examples on that page.

Here is the Python program used to compute this.  

# Sloane A005421.

def drive(n, n2all, sofar):
    assert n > 0
    if n == 1:
        result = n2all[1]
    else:
        # Pick a spot, then + or *.
        # "Pick a spot" means pick the root of the expression tree,
        # with i 1's in the left child and n-i 1's in the right child.
        # Since + and * are commutative, only about half the
        # splittings need to be considered -- split (i, n-i) yields
        # the same sums and products as split (n-i, i).
        # Trickier:  we don't need to consider *all* ints that can be
        # formed with i 1's, we just need to consider the ints with
        # complexity i.  For if x+y or x*y is to have complexity n,
        # x must have complexity i and y complexity n-i (else the
        # same sum or product could produced with fewer than n 1's).
        # OTOH, if x has complexity i and y n-i, x+y or x*y may have
        # complexity < n.  For example, c(1)=1 and c(5)=5, but c(1*5)
        # and c(1+5) are both 5, not 6.
        result = set()
        push = result.add
        for i in range(1, n//2 + 1):
            for x in n2all[i]:
                for y in n2all[n-i]:
                    for z in x+y, x*y:
                        if z not in sofar:
                            push(z)
    return result

def main():
    # Map int n to set of ints k of complexity n.  This means k
    # requires at least n 1's to express, using + * and parens.
    n2all = {1: set([1])}
    # Set of all ints found so far.
    sofar = set([1])
    for n in range(1, 50):
        this = drive(n, n2all, sofar)
        n2all[n] = this
        sofar |= this
        print n, len(this), len(sofar)

main()

"""
1 1 1
2 1 2
3 1 3
4 1 4
5 2 6
6 3 9
7 2 11
8 6 17
9 6 23
10 7 30
11 14 44
12 16 60
13 20 80
14 34 114
15 42 156
16 56 212
17 84 296
18 108 404
19 152 556
20 214 770
21 295 1065
22 398 1463
23 569 2032
24 763 2795
25 1094 3889
26 1475 5364
27 2058 7422
28 2878 10300
29 3929 14229
30 5493 19722
31 7669 27391
32 10501 37892
33 14707 52599
34 20476 73075
35 28226 101301
36 39287 140588
37 54817 195405
38 75619 271024
39 105584 376608
40 146910 523518
41 203294 726812
42 283764 1010576
43 394437 1405013
44 547485 1952498
45 763821 2716319
46 1061367 3777686
47 1476067 5253753
48 2057708 7311461
49 2861449 10172910
"""