Perfect Number Finder

Has anyone made a perfect number finder in LSL? Cuz I was thinking of doing it in C# but I thought LSL might be more fun

For those of you playing the home game, a perfect number is a number such that *ahem* the sum of it's divisors, not including itself equals the number.

So, for example, 6 is a perfect number because the divisors of 6 are 1, 2, 3, and 6 and 1 + 2 + 3 = 6

This sounds like a fun challenge. If only I had paid more attention in math class

Ok, well let's start with the simple dumb version:

// return all the unique factors of n except n.  
// This is left as an exercise for the reader.
list factors(integer n) 

// sum all the elements in input.  
// All elements are assumed to be integers. 
// TILAAEFTR.
integer listSum(list input)

// return TRUE if n is perfect
integer isPerfect(integer n)
{
    return n == listSum(factors(n));
}

// find all perfect numbers (may take a while to run)
integer findPerfects()
{
    integer x = 1;
    while(TRUE)
    {
        if (isPerfect(x)) llSay(0, (string)x + " is Perfect");
        else llSay(0, (string)x + " ain't Perfect (but then, who is?)");
        x++;
    }
}

Now, let's optimize this. What kinds numbers can't possibly be perfect? Is there any way we can remember the results of previous calculations and use them later?

Alright, let's see. First of all let's start at 8589869056.

Next, consider this

So it's the same thing as looking for a Mersenne prime.

I think it might be easiest to just calculate only odd numbers, because that's cooler anyway.

/edit: oops, sorry, I gave a non-working script. Im pulling other numbers out as well...

Hehe cool. Of course, we really only need to do x + 2 but hey, thanks

Any other optimizations?

Ow... my brain.

Of the possible optimizations I can come up with, the only two that really stick involve halving lists to save a few operations in the code, and/or flat out skipping certain numbers entirely (ie. prime numbers).

Since Wednesday's code is already a good example, I'll shamelessly use it as a jumping-off point.

// return all the unique factors of n except n.  
// This is left as an exercise for the reader.
list factors(integer n) 

// sum all the elements in input.  
// All elements are assumed to be integers. 
// TILAAEFTR.
integer listSum(list input)

// return TRUE if n is perfect
integer isPerfect(integer n)
{
//Jeff's code gimping begins here!
list sum = factors(n);
//Why run the factors command multiple times? :)
//Note I erroneously use the list name "sum" -
//mostly because I borked the code while writing it
//and don't want to change the name back around. :rolleyes:
if(llGetListLength(sum) > 2 && (listSum(llList2List(sum, ((integer)(llGetListLength(sum)/2) + 1),llGetListLength(sum))) > (n/2)))
    return n == listSum(factors(n));
//If I didn't forget an operator or parenthesis,
//I'll be very impressed ))
}

// find all perfect numbers (may take a while to run)
integer findPerfects()
{
    integer x = 1;
    while(TRUE)
    {
        if (isPerfect(x)) llSay(0, (string)x + " is Perfect");
        else llSay(0, (string)x + " ain't Perfect (but then, who is?)");
        x++;
    }
}

So, what did I just do? Simply, it first checks to see if the number is prime (if it's two or fewer factors, skip it and save minimal time), THEN checks to see if adding the second half of the list is greater than half the given integer.

The first is pretty obvious as to why I do it, but why the second? Simply put, a lot of numbers (read as: most) do not have enough unique factors to "add up" to even half of what we want on the right side. On the other hand, since all factors are unique (we don't have 2,2,2,2, etc) - to have a number in the ballpark, half of the sucker must be greater on the right side.

Of course, my implementation is sloppy - numbers with an odd number of factors get the "royal" treatment by getting the middle value as a freebie - via truncation to an integer then the addition of one.

So, to bottom line the gibberish: My minor optimization would only read half the list for most numbers in trade for 1.5 times the runtime for the few numbers that might be perfect.

At least, I think.

Does this make me an official LSL nerd?

ok, since my last post I've updated my small script

 
default
{
    state_entry()
    {
        llSay(0, "Hello, Avatar!");
    }

    touch_start(integer total_number)
   {

         integer n = 1000; //n = amount of numbers to check between 1 and n
         integer i=1;
         integer j;
         integer c;
        
        
         while(i<=n)
         {
            c=0;
            for(j=1;j<=i;j++)
            {
              if(i%j==0)
                  c++;
             }
           if(c==2)
          llSay(0,(string) i);
           i++;
        }
    
    }
}
 

Now the only problem with this one is as you move up the number to check its gets slower. but it works

optimization though, I'm still working on.

/edit: ok you know.. I just realized 'perfect number finder' not 'prime number finder' well I've got a prime number finder. ok, I'm tired I'll finish up this tommorow.

Oooh, I'll play too. Runtime is about 2.5 seconds.

(PS. Good obervation Darwin)

// Finds all perfect #s smaller than 2^32. 
// Our limitation is the # of bits in an integer (32). 

// Turn on to find the factors
integer explicit = FALSE;

integer isPrime( integer n ) {
   integer max = (integer)llSqrt(n);
   integer i;

   if ( i == 2 )
      return TRUE;

   if ( n % 2 == 0 )
      return FALSE;

   for ( i=3; i<=max; i+=2 ){
      if ( n % i == 0 )
         return FALSE;
   }
   return TRUE;
}


// Assumes 2^(k-1) * (2^k-1) is a perfect number
printPerfect( integer k ) {
   integer n;
   integer max;
   integer i;
   string out;

   n = (integer) (llPow(2,k - 1)*(llPow(2,k) - 1));

   if ( !explicit )
      out = "k = " + (string)k + ", " + (string)n;
   else {
      max = n / 2;

      // Print out factors
      // This part can be optimized to consider only prime factors, and then
      // construct the list of all factors from the prime factors. That would
      // reduce our runtime to roughly O(sqrt n) from O(n)
      out = "k = " + (string)k + ", " + (string)n + " = 1 + 2 ";
      for ( i=3; i<=max; i++ ){
         if ( n % i == 0 )
            out += " + " + (string) i;
      }
   }

   llSay( 0, out );
}

default {
    state_entry() {
        // Euclid's algorithm to generate perfect numbers
        //  i.e. every perfect number is of the form 2^(k-1) * (2^k-1), for some k > 1,
        //  where 2^k - 1 is prime.
       integer k;

       llResetTime();    
            
       // Overflow 32-bit integer by 17
       for ( k=2; k<17; k++ ) {
          if ( isPrime( (integer)llPow(2,k) - 1 ) ) {
             printPerfect( k );
          }
       }
       
       llSay( 0, "Runtime: " + (string)llGetTime() + "s.");
    }
}

Looks cool Frans. When I get off my PocketPC I'm going to try to make a linked version using multiple prims so we can break the 32 bit barrier.

Of course not, what's the point?
Geeks.

Been there, done that. LSL is slow.
==Chris

Hmm, I'll agree with Chris here. So let's take this to C++

#include <ostream>
#include <iostream.h>
using namespace std;
int main()
{
int perfectnumber=0;
int b=0;

for(int i=1; i<100; i++)	
{
int just1index = 0;
		
				perfectnumber++;
				for(int k=2; k<perfectnumber; k++)
				 {
							
								int important=k;
				if(perfectnumber%important!=0)
				just1index++;
				if(just1index==perfectnumber-2)
				{
								cout << perfectnumber << " is perfect number " << endl;
								b++;
								if(b==4)
												return 0;
				}
				}

}
return 0;


}

Ok, so that's the "stupid version" in Wednesday's terms. Any optimizations?

NOTE: This has not actually been compiled yet.

Darwin: That looks like its trying to do prime numbers, not perfect numbers, same mistake I made, and it completely stops after it reaches 11m unless I did something wrong.

..fook. That's what you get for doing it on paper without thinking.

Sorry folks, that is NOT the C++ version. I have yet to write the C++ version of perfect number finding

You're too impatient to wait a measly 2.5 seconds to find all 32-bit perfect numbers?

Darwin, how does using link messages help you get passed the 32-bit barrier? You'd have to write up your own int data type.

My algorythim wasn't as optimized as yours
==Chris

Well still, imagine C#... that would take maybe .5 seconds.

BTW Francias, a bit later, I'm going to try to make it search for prime numbers even after it finds one...

Honestly, it's easier just to look up all the perfect numbers on the web up to the maximum place-value in SL, store them in a list, and be on your merry way. *grins*

Help we're surrounded by math geeks!

That takes all the fun out of it