08/01/2014, 05:04 PM

(08/01/2014, 03:25 PM)Gottfried Wrote: 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

~ Jay Daniel Fox