From: "Tim Peters" 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 """