[Tutor] how to write an algorithm for sequence [puzzling over a sequence]

[Danny Yoo]

On Tue, 11 Feb 2003, Danny Yoo wrote:

>
>
> On Wed, 12 Feb 2003, reavey wrote:
>
> > I'm stumped. I made up this sequence and I can't figure out a method.
> > the sequence is 1,5,7,15,19,35, 43, 75...
>
> Hi Reavey,
>
>
> This isn't quite Python either, but I'll give it a shot.  *grin*
>
> Hmmm... I don't see anything immediate from the sequence above either.


That was a fun puzzle.  I've got it.  *grin*


If you don't want to ruin it for yourself, do not read the message below.


*** spoiler space ahead ***










































*** spoiler space ***

If we take the original sequence:

    [1, 5, 7, 15, 19, 35, 43, 75]

and we'd like to figure out a way to predict the next number, a good way
to start is to take differences between adjacent elements:

###
>>> def differences(seq):
...     for i in range(0, len(seq)-1):
...         print seq[i+1] - seq[i],
...
>>> differences([1, 5, 7, 15, 19, 35, 43, 75])
4 2 8 4 16 8 32
###


Pattern recognition time.  If we look at this in a twisty enough way, we
won't be able to resist seeing a pattern emerging.... if we write the
sequence in a zigzaggy sort of fashion.


Let's write the entries on the "even"  indices on the top, and the "odd"
entries on the bottom:


4 2 8 4 16 8 32 --->

                    4   8   16   32
                      2   4    8

And this should strike a chord: the sequence of differences is just a
shuffling of the powers of 2 against itself!


###
>>> def shuffle(s1, s2):
...     pairs = zip(s1, s2)
...     results = []
...     for p in pairs:
...         results.append(p[0])
...         results.append(p[1])
...     return results
...
>>> powers_of_two = [2**n for n in range(10)]
>>> l1 = powers_of_two[2:]
>>> l2 = powers_of_two[1:]
>>> shuffle(l1, l2)
[4, 2, 8, 4, 16, 8, 32, 16, 64, 32, 128, 64, 256, 128, 512, 256]
###


Success!  But why should we pay so much attention to differences?
Because, if we can figure out how the differences work, we can figure out
how the original sequence works.  Let's see why.  As a concrete example,
we see that the next difference that's coming up after 32 is 16.

[4, 2, 8, 4, 16, 8, 32, 16, ...]
                       ^^^^

So we plug 16 at the bottom of our little "differences" diagram we drew up
before:

    1   5   7   15   19   35   43   75
      4   2   8    4   16    8    32

[plug in 16] ==>


    1   5   7   15   19   35   43   75
      4   2   8    4   16    8    32  16


Now the next number on the top, our original sequence, is easy to
calculate:

###
>>> 75 + 16
91
###


Let's say this in formal mathy language.  First, we'll label the top row
the "sequence" row, and let's label the bottom the "difference" row.
Now, since we've named them, let's say the relationship between the two
rows:

    sequence(0) = 1           ## the first number in the sequences row is
                              ## always 1.


    sequence(n) = sequence(n-1) + difference(n-1)

                              ## And any other number is just the
                              ## the number to the left, plus
                              ## the difference number on the right
                              ## side.




Here is a formula I'll conjure up that gives us the "n'th" difference
number:

###
>>> def secretFormula(n):
...     return ((-1)**n + 1) * 2**((n+2)/2)
...
>>> [secretFormula(n) for n in range(10)]
[4, 0, 8, 0, 16, 0, 32, 0, 64, 0]
>>> def secretFormula2(n): return secretFormula(n-3)
...
>>> [secretFormula2(n) for n in range(10)]
[0.0, 2.0, 0.0, 4, 0, 8, 0, 16, 0, 32]
>>> def d(n):
...     return int(secretFormula(n) + secretFormula2(n))
...
>>> [d(n) for n in range(10)]
[4, 2, 8, 4, 16, 8, 32, 16, 64, 32]
###



And with this, we're pretty much set:

###
>>> def sequence(n):
...     if n == 0: return 1
...     return sequence(n-1) + d(n-1)
...
>>> sequence(0)
1
>>> sequence(1)
5
>>> sequence(2)
7
>>> [sequence(n) for n in range(10)]
[1, 5, 7, 15, 19, 35, 43, 75, 91, 155]
###


We can continue going on, but I think I'll stop here.  But now I've got a
hankering to start reading Concrete Mathematics again.  *grin*


Hope this helps!