Re^2: Powers of three

honestly i don't remember it was written in my statistics class at 9am
i'm also partially curious as to why the program works, i know what its doing, i worked it out by hand before writing it in perl

It's originally derived from the pascal triangle, you know this thing

if we take only bit 0, (2**0) we get this

       1
      1 1
     1 0 1
    1 1 1 1 
   1 0 0 0 1
  1 1 0 0 1 1
 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1

add up each row and we get this series

1, 2, 2, 4, 2, 4, 4, 8, ...

after thinking about it for a few minutes i realised how to generate that series
start with a list @a = (1);

#my code does this all in d() with a push and a map, ain't perl grand
1. take list @a and produce a copy of it in @d
2. double all the values in @d
3. push @b onto @a
4. goto step 1

this will produce the series above now we add all the values in the list to those before the current value (not recursively, just a simple cumulative sum) and we get

1, 3, 5, 9, 11, 15, 19, 27, ...

this is @b in my program, if you look closely at 2**$n-1 we now have 3**$n.
what i'm having a little trouble understanding is why does this produce powers of three from doubling numbers (and adding them together), maybe someone with a math degree can tell me why, also i don't know for sure that it will always give powers of 3. But i've tested it up do 24 on my computer (that used about 150MB of ram, i haven't tried higher yet)

Comment on Re^2: Powers of three

Replies are listed 'Best First'.
Re^3: Powers of three by truedfx (Monk) on Feb 07, 2006 at 18:04 UTC
A simple explanation of why it works, since you wondered: If you continue your triangle, you end up with this: 1 1 1 1 0 1 1 1 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 1 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 You probably see a pattern by now, but if not, change all the 0s to spaces, and all the 1s to #s: # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # No matter how far down you go, you always end up with a triangle, and you can continue by copying that triangle to its bottom left and right sides. This is easy to see, but I can't find the words that actually explain it, so please take a look for yourself if you have doubts about that. Now take a look at this: the first row has 1 as its sum. This triangle-point is copied twice, so the first 2 * 1 rows have 3 * 1 as their sum. This triangle is copied twice, so the first 2 * 2 * 1 rows have 3 * 3 * 1 as their sum. The first 2^3 * 1 rows have 3^3 * 1 as their sum. I'm sure you get the idea by now :) It's not proof, but hopefully it's good enough.	[reply]
Re^3: Powers of three by tweetiepooh (Hermit) on Feb 10, 2006 at 11:09 UTC
Nice code. Logically the state of any point is an XOR of its two parents taking a missing parent to be 0. (and seeding with a 1 at the point)	[reply]