Re: Powers of three

Replies are listed 'Best First'.
Re^2: Powers of three by simcop2387 (Acolyte) on Feb 07, 2006 at 07:55 UTC
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 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 if we take only bit 0, (20) 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)	[reply]
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]