here's an obfuscated way to get powers of 3 from multiplying 1 by 2 and powers of two and two arrays (with a little addition in the mix). $a is what power of three to calculate. 
$a=24;@a=(1);sub d{push@a,map{2*$_}@a};
d for('1'.."$a");$b=$#a;$_=0;
push@b,$_+=$a[$#a-$b--] until($b==-1);
print$b[2**$a-1];

[download]
a simple note, it'll use 2*(2**$a) array elements, and is probably O(2**n) in memory usage and cpu time, so its probably one of the more ineffecient ways to calculate powers of three in existence

Replies are listed 'Best First'.
Re: Powers of three
by zshzn (Hermit) on Feb 07, 2006 at 02:35 UTC
    Neat!

    I wouldn't interpolate $a in the for loop. Or 1. Makes me kind of wonder what influenced you to do so.

[reply]
      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, (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)
[reply]
        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]
        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]

Back to Obfuscated Code