Strange Numbers

[alexander]

turtle, its because 562949735317504/21801856=25821184

 

btw, i've been working on a we app for you i will pm you details, i will gladly develop it further for you (if anyone else is interested, let me know)

[modest]

Hey, the big brains are just falling out of the woodwork

 

Alexander!

 

Here's what we need. Super-fast program to factor numbers, sum all factors that don't include the number itself, check to see if the sum is 12 greater than the number (abundant by 12 they say), if so... check if the number is not divisible by six, if that's the case then print the number. Also check if the number is divisible by six and a prime, if so, print number.

 

This code does the job (please do NOT make fun of my coding... I am not a coder and I realize it probably looks very ugly):

 

use Term::ReadKey;

$startValue="$ARGV[0]";                                            
$endValue="$ARGV[1]";                                              
ReadMode 4;

for ($n = $startValue; ($n < $endValue) && (not defined ($key = ReadKey(-1))); ++$n){                        
 $divisorSum = 1;
 for ($checkFactor = 2; $checkFactor < sqrt($n); ++$checkFactor){   
   if ((int($n/$checkFactor))==($n/$checkFactor)){
     $divisorSum += ($n/$checkFactor)+$checkFactor;
   } 
 }
 if (int(sqrt($n))==sqrt($n)){                                     
     $divisorSum += sqrt($n);
 }
 if ($divisorSum==$n+12){                                                   
   if (int($n/6) == $n/6){                                        
     $checkPrime = $n/6;                                            
     $prime = 1;
     for ($i = 2; $i < (sqrt($checkPrime)+1) && $prime; ++$i){
       if (int($checkPrime/$i)==$checkPrime/$i){                    
         $prime = 0;
         print "number ",$n," is abundant by 12, with factors 6 & ",$checkPrime, " which is not prime n";
       }          
     }
   }
   if (int($n/6) != $n/6){                                          
   print "number ",$n," is abundant by 12 and not divisible by 6 n"; 
   }
 }
}

if ($key) {print "The program was terminated at n = ", $n;}
else {print "Done checking ",$startValue," - ",$endValue;} 
ReadMode 0;

 

When input is 1 - 150,000 the output is,

 

number 24 is abundant by 12, with factors 6 & 4 which is not prime
number 54 is abundant by 12, with factors 6 & 9 which is not prime
number 304 is abundant by 12 and not divisible by 6
number 127744 is abundant by 12 and not divisible by 6
Done checking 1 - 150000

 

The problem is, PERL (and Java, I would also assume) are simply too slow when these numbers get in the billions. I've been trying to put this in C++, but I'm having trouble using bigint and bigfloat classes, as the built in double float and double int are too small.

 

The best two options I've found are:

 

The GNU MP Bignum Library

 

SourceForge.net: C++ BigInt class: C++ BigInt class

 

I can't get the former to build properly for XP with my processor and I haven't had time yet to properly look at the second. GMP has a function for checking primality and some other factor-like functions that would make this work at break-neck speeds, but like I said, I'm just not a programmer and I've got no time at the moment.

 

Uhhhh.... That's all I got

 

~modest

[alexander]

well, i can rewrite this in bc code for arbitrary precision, and it's fast enough to be able to deal with numbers in ranges you are looking at, and it is arbitrary precision, so it is limited by the hardware it is running on...

 

now, if there is a need, i can fire up my bohemith at work to crunch for you guys, but we will have maybe a weekend of computing before they will make me shut it down... (bohemith = octal Xeon 3.0 with 36 gigs of ram)

[alexander]

i'm putting together a linux HPC cluster for the computing needs here... i am starting it with 2 machines this weekend, but it will grow, i have a few machines coming from friends locally, and i am negotiating 2 more machines from a friend a few states away. I started a thread on the project http://hypography.com/forums/computer-science/18405-building-an-hpc-cluster.html

[modest]

I've been playing with the Numberator myself and I am awed at the effort put into it... wow... speechless.

 

I'm not sure why 2 would run with similar speed as 1. My only guess would be that you have a dual-core processor, but mine doesn't seem to help in that regard. But, no, a bunch running at the same time would definitely hurt the performance of each since its the processor that's straining to keep up.

 

I'm wondering myself... do you know if any of the other abundant / deficient numbers have methods for finding them like perfect numbers have in the way of [math]2^{(n-1)}(2^n-1)[/math]?

 

~modest

[TheBigDog]

Excellent finding Turtle. I am planning the Numberator 2K9. It will incorporate this change, among many others. It will represent the "state of the art" as far as my programming skills are concerned. Over the next couple weekends.

 

Bill

[alexander]

TBD, is there any way you can port it to MPI? (c++ or fortran, or anything openmpi supports?)

 

i am nearly finished with setting up the cluster for this, hopefully another week or so will weild an 8 node parallel cluster for the numberating needs... And if you dont have a cluster you can still run it with mpirun on a single node (this will however better utilize resources with threading and all)

[TheBigDog]

TBD, is there any way you can port it to MPI? (c++ or fortran, or anything openmpi supports?)

 

i am nearly finished with setting up the cluster for this, hopefully another week or so will weild an 8 node parallel cluster for the numberating needs... And if you dont have a cluster you can still run it with mpirun on a single node (this will however better utilize resources with threading and all)

 

Clearly there is a gap between my state of the art and yours. I will post the code with ample comments. It is going to be in vb.net. My plan is to allow multiple parallel search operations through dividing into blocks and having a multi-threaded search feature. It will also store all of the results in a sql database for vastly improved analysis. Since the search will be on a background thread the UI will run at full speed all the time. You may even be able to set up the search as a low priority service that simply runs while your computer is on, and allows you to jump in and see the progress whenever you wish. Plus some use configurable settings for optimizing the search.

 

Bill

[alexander]

ok so i will have to rewrite the code from the ground up for mpi c++... sounds like fun... your code will be vastly helpful in making this work. i'll throw the results into sqlite or something. you know we could then write a php analysis, web-based front end for analyzing the results or dumping them in the clear form, also build graphs, well whatever you can imagine... but web-based...

[alexander]

wait, i got it, i think i know what to do now...

 

turtle, is this what you are looking for (specs)

 

Program would run through numbers, from 1 to say the last 5000 digit number

it will first check if the number is prime... if it is, label it as prime, go on

it will then find all the factors of the number

it will add all the factors and see if the result is abundant, defficient or special (abundant by exactly 12)

if the number is abundant or defficient, lable and continue

if the number is strange, then test if the number/6 is a prime

 

the results will be kept in the database, i will then write a quick reporting interface for it that will allow you to see if your theory is correct?

[alexander]

maybe 5000 digits is a bit much... how many do you think we have to go to to prove the strange number sequence?

[Bombadil]

Reading through some of your posts I noticed something that I think may make it easer for you to find some of the Strange Anomalies. In particular what I have proven or at least what I think I have proven is that whenever the number

 

[math]2^{n+1}-13[/math]

 

is prime the number

 

[math]2^n(2^{n+1}-13)[/math]

 

is a Strange Anomaly. Now I can’t test this but if I am right and I have proven this, that may be even better. Now I’m not going to prove this right now but If you can’t figure out why I think this is the case I will. But I think that someone will figure it out now that I have pointed it out.

[alexander]

pssht i can test for a prime in less ticks then that, remember primes above 3 fall in the category of 6*n+1 or 6*n-1, so why not exploit that simply by doing this (ps you dont need to know c++ to figure out what this is doing):

 

bool is_prime(int num)
{
   //lets see we need to check for a couple of things first
   if ( num==2 || num==3 || num==5 || num==7 )
   {
        return true;
   }
   if (num==1 || num%2==0 || num%3==0 || num%5==0 || num%7==0)
   {
       return false;
   }

   if((num+1)%6==0 || (num-1)%6==0)
   {
       return true;
   }
   return false;
}

 

Turtle, ok, i'll make it a proggy for this specific application...

 

Also the factoring algorithm will be more efficient if it only finds the first half of all the factors... you can then multiply the sum by 3 to get the sum of all the factors. (if my math mind is treating me correctly)

 

Turtle, if you can come up with an algorithm... especially if you can come up with a parallel computing factoring algorithm, or at least a general program workflow, it will be very helpful (step by step pseudocode would be great...)

[alexander]

oh no, i am sorry, i was wrong... that would not work with the whole times 3 thing... no, but generating 1/2 the factors then using them to find the sum would be a hell of a lot faster...

 

but you say that there is a problem for perfect squares... how is it reflected?

[TheBigDog]

I have a final paper for school to write this week. Then I have some free time coming. The Numberator 2K9 will take much of the old Numberator, but use some tricks to make it more efficient at the brute force search. It will be able to have multiple search threads happening, and a will assign blocks on numbers to each thread. I imagine a UI that allows you to define how long a thread stays alive, and an estimate is made by the program to decide how many numbers to assign. So you could define it to have 20 threads, and each one to last for one minute. It would use statistics from the searching speed to assign a block of numbers that should last for the allotted time. The user can tweak performance by dialing up or down the number of simultaneous thread and how long they last. I am also researching the best way to use very large numbers in vb.net.

 

The beauty is that all of the searching becomes a background operation. The user can do analysis of numbers up front without stalling the process. And the time to load the data from the database into the tool is going to all but disappear.

 

Alex, I will break down the basic functions that I use for the math, hopefully well enough to make it simple to recreate them in whatever language you choose. I am probably going to create my own class similar to the Math class in .net with all of the Numberator stuff built right in. f(x), IsPrime, factors, etc.

 

While we are at it we can build a list of known primes. The Numberator actually does this, but keeps them in memory as it runs, then "rediscovers" them the next time it runs. Having a list makes the "IsPrime" function much faster since it compares the list to the target to determine if it needs to search for more primes to complete the factoring (if the largest prime on the list is less than the sqrt of the target).

 

Bill

[alexander]

I have found a problem for the prime number checker above... please refer to Finally Learning C++ thread in CS, i have both the updated, fixed code and testing data... if you are interested...

[Bombadil]

Back on Bombadilly's equation. It does generate 5 of the 6 Strange Anomalies we have found, but it does not give 54, which is 6*9. I ran [math]2^n+1-13[/math] out to n= 36 & found no more Primes. This is not to say we won't find anymore, but this all has the flavor of my equation last week working to only a certain point. I think what is wrong is that we won't get any more Primes because our methods relied on a common difference? :shrug:

That's all I got.

 

Well if they’re not there, they’re not there but I suspect that the formula will produce more strange anomalies it just might take a while before we find them. After trying to make my own program to find the next one I came up with n = 56 but it takes to long to make sure it produces a prime for me to check it. Anyway here is how I came up with the equation in the first place.

 

If we consider the equation

 

[math]2^np+12=\sum_{i=0}^{n}2^i+\sum_{i=1}^{n}2^{n-i}p[/math]

 

Where 2^np is how we represent the number of interest with p being a prime and the right side being the sum of its factors you will notice that

 

[math]\sum_{i=0}^{n}2^i+\sum_{i=1}^{n}2^{n-i}p=2^{n+1}-1+(2^{n}-1)p[/math]

 

Substituting this in the first equation and rearranging it we get

 

[math]2^{n+1}-13 =p[/math]

 

This looks right to me maybe I have missed something.