[Tutor] how to write an algorithm for sequence [puzzling over
a sequence]
Emanuel R Woiski
woiski@dem.feis.unesp.br
Wed Feb 12 06:40:04 2003
--------------040807080007070703050706
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
I guess the sequence is such as:
a[0] = 1
if n > 0
a[n] = a[n-1] + 2**(n + 3)/2 odd n
a[n] = a[n-1] + 2**n/2 even n
regards
woiski
Danny Yoo escreveu:
>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!
>
>
>_______________________________________________
>Tutor maillist - Tutor@python.org
>http://mail.python.org/mailman/listinfo/tutor
>
>
>
>
--------------040807080007070703050706
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html;charset=ISO-8859-1">
<title></title>
</head>
<body>
I guess the sequence is such as: <br>
a[0] = 1 <br>
if n > 0 <br>
a[n] = a[n-1] + 2**(n + 3)/2 odd n <br>
a[n] = a[n-1] + 2**n/2 even n <br>
<br>
regards<br>
<br>
woiski<br>
<br>
Danny Yoo escreveu:<br>
<blockquote type="cite"
cite="midPine.LNX.4.44.0302111929480.28496-100000@hkn.eecs.berkeley.edu">
<pre wrap="">
On Tue, 11 Feb 2003, Danny Yoo wrote:
</pre>
<blockquote type="cite">
<pre wrap="">
On Wed, 12 Feb 2003, reavey wrote:
</pre>
<blockquote type="cite">
<pre wrap="">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...
</pre>
</blockquote>
<pre wrap="">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.
</pre>
</blockquote>
<pre wrap=""><!---->
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:
###
</pre>
<blockquote type="cite">
<blockquote type="cite">
<blockquote type="cite">
<pre wrap="">def differences(seq):
</pre>
</blockquote>
</blockquote>
</blockquote>
<pre wrap=""><!---->... for i in range(0, len(seq)-1):
... print seq[i+1] - seq[i],
...
</pre>
<blockquote type="cite">
<blockquote type="cite">
<blockquote type="cite">
<pre wrap="">differences([1, 5, 7, 15, 19, 35, 43, 75])
</pre>
</blockquote>
</blockquote>
</blockquote>
<pre wrap=""><!---->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!
###
</pre>
<blockquote type="cite">
<blockquote type="cite">
<blockquote type="cite">
<pre wrap="">def shuffle(s1, s2):
</pre>
</blockquote>
</blockquote>
</blockquote>
<pre wrap=""><!---->... pairs = zip(s1, s2)
... results = []
... for p in pairs:
... results.append(p[0])
... results.append(p[1])
... return results
...
</pre>
<blockquote type="cite">
<blockquote type="cite">
<blockquote type="cite">
<pre wrap="">powers_of_two = [2**n for n in range(10)]
l1 = powers_of_two[2:]
l2 = powers_of_two[1:]
shuffle(l1, l2)
</pre>
</blockquote>
</blockquote>
</blockquote>
<pre wrap=""><!---->[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:
###
</pre>
<blockquote type="cite">
<blockquote type="cite">
<blockquote type="cite">
<pre wrap="">75 + 16
</pre>
</blockquote>
</blockquote>
</blockquote>
<pre wrap=""><!---->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:
###
</pre>
<blockquote type="cite">
<blockquote type="cite">
<blockquote type="cite">
<pre wrap="">def secretFormula(n):
</pre>
</blockquote>
</blockquote>
</blockquote>
<pre wrap=""><!---->... return ((-1)**n + 1) * 2**((n+2)/2)
...
</pre>
<blockquote type="cite">
<blockquote type="cite">
<blockquote type="cite">
<pre wrap="">[secretFormula(n) for n in range(10)]
</pre>
</blockquote>
</blockquote>
</blockquote>
<pre wrap=""><!---->[4, 0, 8, 0, 16, 0, 32, 0, 64, 0]
</pre>
<blockquote type="cite">
<blockquote type="cite">
<blockquote type="cite">
<pre wrap="">def secretFormula2(n): return secretFormula(n-3)
</pre>
</blockquote>
</blockquote>
</blockquote>
<pre wrap=""><!---->...
</pre>
<blockquote type="cite">
<blockquote type="cite">
<blockquote type="cite">
<pre wrap="">[secretFormula2(n) for n in range(10)]
</pre>
</blockquote>
</blockquote>
</blockquote>
<pre wrap=""><!---->[0.0, 2.0, 0.0, 4, 0, 8, 0, 16, 0, 32]
</pre>
<blockquote type="cite">
<blockquote type="cite">
<blockquote type="cite">
<pre wrap="">def d(n):
</pre>
</blockquote>
</blockquote>
</blockquote>
<pre wrap=""><!---->... return int(secretFormula(n) + secretFormula2(n))
...
</pre>
<blockquote type="cite">
<blockquote type="cite">
<blockquote type="cite">
<pre wrap="">[d(n) for n in range(10)]
</pre>
</blockquote>
</blockquote>
</blockquote>
<pre wrap=""><!---->[4, 2, 8, 4, 16, 8, 32, 16, 64, 32]
###
And with this, we're pretty much set:
###
</pre>
<blockquote type="cite">
<blockquote type="cite">
<blockquote type="cite">
<pre wrap="">def sequence(n):
</pre>
</blockquote>
</blockquote>
</blockquote>
<pre wrap=""><!---->... if n == 0: return 1
... return sequence(n-1) + d(n-1)
...
</pre>
<blockquote type="cite">
<blockquote type="cite">
<blockquote type="cite">
<pre wrap="">sequence(0)
</pre>
</blockquote>
</blockquote>
</blockquote>
<pre wrap=""><!---->1
</pre>
<blockquote type="cite">
<blockquote type="cite">
<blockquote type="cite">
<pre wrap="">sequence(1)
</pre>
</blockquote>
</blockquote>
</blockquote>
<pre wrap=""><!---->5
</pre>
<blockquote type="cite">
<blockquote type="cite">
<blockquote type="cite">
<pre wrap="">sequence(2)
</pre>
</blockquote>
</blockquote>
</blockquote>
<pre wrap=""><!---->7
</pre>
<blockquote type="cite">
<blockquote type="cite">
<blockquote type="cite">
<pre wrap="">[sequence(n) for n in range(10)]
</pre>
</blockquote>
</blockquote>
</blockquote>
<pre wrap=""><!---->[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!
_______________________________________________
Tutor maillist - <a class="moz-txt-link-abbreviated" href="mailto:Tutor@python.org">Tutor@python.org</a>
<a class="moz-txt-link-freetext" href="http://mail.python.org/mailman/listinfo/tutor">http://mail.python.org/mailman/listinfo/tutor</a>
</pre>
</blockquote>
<br>
</body>
</html>
--------------040807080007070703050706--