My favorite integer sequence

[jaydfox]

I've got the generating rule in terms of a matrix.

Hmm, I hadn't thought of doing it that way. Interesting... I've been analyzing the information flow, and came up with code to generate the sequence which does not need to store all the previous entries.

Here is an illustration of the data flow (calculations from Excel spreadsheet):
   

The naive implementation calculates the nth entry by considering the n-1 entry and the n/2 entry, so it has to keep at least n/2 entries in memory. The version below only keeps log_2(n) entries.

Below is SAGE (python) code.

Code:

size = 6
parts = [1]*size
print 0, parts[0]
for k in xrange(1, 2^(size-1)):
    for b in xrange(size-2, 0, -1):
        mask = (2^b) - 1
        if k&mask == 0:
            parts[b] += parts[b+1]
    parts[0] += parts[1]
    print k, parts[0]

Here is the output for validation:

Code:

0 1
1 2
2 4
3 6
4 10
5 14
6 20
7 26
8 36
9 46
10 60
11 74
12 94
13 114
14 140
15 166
16 202
17 238
18 284
19 330
20 390
21 450
22 524
23 598
24 692
25 786
26 900
27 1014
28 1154
29 1294
30 1460
31 1626