Determining Maximum Pool Sets Using Binomial Coefficients On Linux and Unix

Hey There,



How's this for some light Monday reading? ;) Actually, the title sounds a lot worse than the concept or its application. In fact, if you read the equation in its "native form," above, it looks like gibberish, unless you're really into mathematics or engineering ;) For our purposes, we'll reduce it to something that looks like regular mathematics (which it is) and tie it back into our series of posts from last week. This is what the derivation looks like in English, assuming n=4 and k=3 (no math involved ;). In fact, if you understand the concept of deriving factorials, this is really fairly basic:

The binomial coefficient of 4 over 3 is derived, in steps, by:

a. the factorial of 4 divided by the factorial of 3 times the factorial of 4 minus 3 (Complete statement)
b. 24 divided by 6 times 1.
c. 24 divided by 6.
d. 4

Maybe it's just as confusing. I can't tell ;)

Our objective in this whole set of exercises, again is: Given a Number Pool of "x through y," create the maximum possible Fixed List Length variations of our Fixed List that contain some variation of our Guaranteed Combination, without any duplication (i.e. 1, 2, 3 is equal to 2, 3, 1 and would only count as one match), and return the results. Please check out the original post on Number Pools And Guaranteed Combinations Within Fixed Lists for definitions of the different parts of our Objective.

On its face, this post doesn't seem to fit into what we've been doing lately, but (I promise) it will actually make a difference in the end :)

The equation, shown above (and in plain numerals and English below ;) has many practical applications. For our case (which I believe is what it's most commonly used for) we're going to use it to determine how many unique Y-length sets (or lists) we can derive from a X-length pool (or larger list). To put this into ordinary, and manageable perspective, you could use this equation to determine how many unique sets of 3 numbers you could find in a list of 6 numbers (1, 2, 3, 4, 5, and 6). The answer would be 20 and you could prove this to yourself easily (without mathematics) by just writing out the unique combinations on paper. Something like this, except with no computer or web browser involved ;)

123 124 125 126 = 4
134 135 136 = 7
145 146 = 9
156 = 10
234 235 236 = 13
245 246 = 15
256 = 16
345 346 = 18
356 = 19
456 = 20

We'll be using this equation, to check and ensure that we have the smallest reduced set of Fixed List Length variations of our Fixed List that contain some variation of our Guaranteed Combination, when we think we're finally finished. If we've done our job well, the numbers should match. If we haven't, well... it'll really all be my fault and I'll be sure to give myself a good mental lashing ;)

For the meantime, I've attached a simple Perl script, which should work on most distro's of Linux and/or Unix, to the bottom of this post so that you can check out the power of binomial coefficient mangling and, perhaps, put it to some good use (although we, in no way, endorse this as a method to improve your odds at gambling... So little time and so many disclaimers ;)

You can run the Perl script simply, without arguments, as it will prompt you for them (unless you retool it yourself, which is totally cool, if you want to), like so:

host # ./binco.pl
Enter Larger Pool Number: 6
Enter Smaller Set Number: 3
Binomial Coefficient of 6 over 3 = 20

Cheers,





This work is licensed under a
Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License

#!/usr/bin/perl

# 
# binco.pl - More fun with numbers :)
#
# 2008 - Mike Golvach - eggi@comcast.net
#
# Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License
#

print "Enter Larger Pool Number: ";
chomp($x=(<STDIN>));
print "Enter Smaller Set Number: ";
chomp($y=(<STDIN>));
$z=$x - $y;

$fact1 = fact($x);
$fact2 = fact($y);
$fact3 = fact($z);
$fact4 = $fact3 * $fact2;

$binco = $fact1 / $fact4;
print "Binomial Coefficient of $x over $y = $binco\n";

sub fact        {
        my $number = @_[0];
        $fact = $number;
        for ($factless1 = $number -1; $factless1 > 1; $factless1--)     {
                $fact *= $factless1;
        }
        return $fact;
}

, Mike

---

Please note that this blog accepts comments via email only. See our Mission And Policy Statement for further details.

---

Shell Scripting, Factorial Primes And Huge Number Computations On Linux And Unix

Hey There,

I know it's the weekend when I don't get any hate mail regarding posts like yesterday's on producing prime numbers with the bash shell ;)

One truth about prime numbers is that, except for 5, no number ending in 5 can be a prime. Logic dictates that it will, of course, be divisible by itself and by the number 5, thereby removing it from the prime pool. Another thing you may have noticed is the output from the script itself which showed that it found 35 to be a "prime number." It also missed quite a few after 19 (23, 29 and 31, to be specific).

There's a reason I let it go; and not just so I'd have something easy to write about on a "Lazy Sunday" ;) I actually tested this script both on an OpenBSD box and Cygwin for Windows (Unfortunately, I have no Unix computers at my disposal on the weekends, but Linux is just as capable an OS). Neither one could get past 19, when listing out primes; both related to the same two basic problems. The two situations that resulted, when trying to determine higher primes, both had to do with my system limitations, so you might have been able to get higher numbers than I did before the script went South on you :)

The first issue is the theorem we used to determine the primes. Since Wilson's Theorem depends on factorial computation in order to determine a number's prime status, each succeeding number requires an additional operation, which make the numbers required to test divisibility grow at an alarming rate.

For instance, the factorials of 2, 3 or 4 are trivial:

2 = 2 * 1 --> Factorial equals 2
3 = 3 * 2 * 1 --> Factorial equals 6
4 = 4 * 3 * 2 * 1 --> Factorial equals 24

and you can see how the numbers can begin to get large very quickly.

The second issue is the capacity of the Linux or Unix operating system to handle extremely large numbers. Although both of my systems are running 32 bit OS's, the 64 bit OS will have to eventually fail as well. On a 32 bit system, the magic number 20 is where the wrap-around occurs and the numbers become so large that the system can misinterpret them as negative something-or-other. Here are my two example outputs (truncated):

For Cygwin on 32 bit XP, you can see this in the script when you invoke bash with the -x flag, as it hits the breaking point at the number 22 (soooo close to 23 ;)

...
+ count=22
+ '[' 22 -le 22 ']'
++ prime_number 22
++ local prime=22
++ p_minus_1=21
+++ factorial 21
+++ local factorial_count=21
+++ '[' 21 -eq 0 ']'
+++ (( factor=20 ))
+++ (( 20 >= 1 ))
+++ factorial_count=420
+++ (( --factor ))
+++ (( 19 >= 1 ))
+++ factorial_count=7980
+++ (( --factor ))
...
+++ (( --factor ))
+++ (( 2 >= 1 ))
+++ factorial_count=-4249290049419214848
...

at this point, the test for divisibility becomes unreliable, at best.

On OpenBSD, 32 bit, the results were exactly the same:

...
+++ (( --factor ))
+++ (( 2 >= 1 ))
+++ factorial_count=-4249290049419214848
...

Naturally, then, every number tested for "prime status" by our prime number shell script, beginning with 22 couldn't be tested correctly, resulting in many more surprising results like 35 ;)

In any event, hopefully, the script helped make at least one method to determine primes more accessible or understandable. As we noted, also, in yesterday's post, no one has been able to define the largest prime number yet. Yesterday's script gives you a pretty clear idea of the reason. When faced with an infinite number of integers, the requirements for calculation, alone, make this an impossible task. But, basically, the reasons all boil down to the same thing (although, if you look around the web, there are a few unprovable - in the absolute sense - theories that claim the number can be known):

The nature of integers is infinite. If you think of the highest number you can and add 1, you're one step closer to being frustrated for the rest of your life ;)

Also, for clarity's sake, since the mathematics in my head don't always match what I type, I thought I'd save you some paraphrasing and just dump two definitions here on the page; for composite numbers and relative primes (with my side-notes and apologies):

Relative Primes: The integers a and b are relatively prime if they have no common factor other than 1 or, equivalently, if their greatest common divisor is 1 (Note that this was correctly defined yesterday, but not thoroughly enough, since I didn't mention the fact that, although the numbers can't be primes and must have the greatest common factor of 1, I neglected to mention that neither pair of numbers could have any other common factors. A fairly large distinction, but lost in the mix when I was typing. For instance, 6 and 35 are relative primes, while 6 and 36 aren't, since they both share a common factor of being divisible by 3. ...My mind can be a terrible thing ;)

Composite Numbers: These are any positive integers which have a positive divisor other than one or themselves (While these can be derived by multiplying any two prime numbers, which I pointed out, the less complicated definition is that composite numbers are any number that isn't a prime. The multiplication of any 2 primes to create a composite is more of a cool little frill than a necessity. It's a lot easier to wrap your head around when you look at it that way ;)

But, as promised, with regards to composites , we won't put a script out, so much as a description of a method, since the same mathematical boundaries would be hit performing this operation:

1. Run yesterday's script, or pick up a prime number table that will start with 2; the first real prime (check out yesterday's post on producing prime numbers for the reasons 1 and 0 aren't considered primes).

2. Remove every number in the prime table from the larger set of all numbers.

Voila: You have all of the composite numbers, although you will most probably never ever find them all ;)

Here's to another month or so of non-math-related posts ;)

Cheers,

, Mike

Shell Script To Produce Prime Numbers On Linux And Unix

Hey There,

You might recall (quite a while back) the last time we put out a Linux or Unix script involving a somewhat-complex mathematical formula. The most recent post had to deal with factorial generation and the only other mostly-math post we did prior to that was about generating Fibonacci numbers up to any user-defined limit.

Today we're going to look at a similar issue, and develop a similar script. This time we'll work on something that, on its face, seems a bit easier to figure out. Today we're going to create a script that will list out all "prime" numbers up to a user-defined limit. We'll stay away from "relative primes" since (by definition) any two numbers, that aren't primes, share a greatest common factor (Sometimes referred to as the lowest common denominator in fractions) of 1. So non-prime numbers like 9 (1 x 3 x 9) and 25 (1 x 5 x 25) are considered relative primes. The definition basically applies to any numbers that aren't primes. You could easily derive those just by removing all the prime numbers from the positive integer set you define when you invoke the script, which can be easily done, like this:

host # ./primes.sh 100

Composite numbers are the result of the multiplication of prime numbers. We'll take a look at scripting out composites for our next post. It should be a natural extension of today's script.

It's interesting to note, though, that the number 1 is not considered a prime, because it only has one factor: itself. All other numbers, that are available for prime status, have two factors: themselves and themselves divided by 1 (with the result being a positive integer). Of course, the number 1 divided by 1 is zero; therefore, it only has one factor and it's not a prime. It is also not considered a composite. We'll be avoiding the dreaded zero today, as well, since it's neither a prime nor a composite either.

With all that muck out of the way (I hope ;), let's take a look at defining prime numbers on a formula-based scale. There is an excellent reference online at mathforum.org that goes into detail about many different ways (some better, some worse) to go about deriving primes to the nth degree. For our purposes, we're going to dispense with the Greek alphabet and look at solving the problem as purely as possible, even though that might not be the "most efficient" way to do it. Sometimes (especially if you're not a math wizard, like me), understanding how to generate numbers that meet certain criteria, is more important than applying advanced mathematical formulae which, for all I know, may or may not even be completely valid. If you're ever up for twisting your brain into a knot, try to absolutely prove any advanced mathematical formula. For kicks, ask an advanced mathemetician to do the same ;)

For those of you who are curious (since there are so many theorems out there), our script today is based on Wilson's Theorem, which basically states:

An integer p > 1 is prime if and only if the factorial (p - 1)! + 1 is divisible by p

In other words, if you take your chosen number, subtract 1 from that, get the factorial value (which we've gone through in more detail in our post regarding factorial generation) of the resulting subtraction and then add 1 to it, the number is only prime if the modulus (or remainder) of that resulting number's division by the original number is equal to 0 (or, depending on how you prefer to think of it, if the resulting number is absolutely divisible by the original number).

I hope you enjoy this script. I wangled the factorial function so that it's quite a bit faster than the "bash" method shown in our factorial generation post from earlier on. In fact, here's a look at the time savings from Linux running on a now-obsolete PC :)

host # time ./primes.sh.bak 35
Generating Prime Numbers Up To 35

2 3 5 7 11 13 17 19 35

All Set!


real    3m21.994s
user    0m18.445s
sys     0m40.857s

host # time ./primes.sh 35
Generating Prime Numbers Up To 35

2 3 5 7 11 13 17 19 35

All Set!


real    0m8.173s
user    0m1.464s
sys     0m2.407s

Note that this script can't find the highest prime number (I don't think anyone's figured that out yet), but it can figure out the highest prime number your system is capable of calculating. Close enough ;)

Cheers,





This work is licensed under a
Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License

#!/bin/bash

#
# primes.sh - find all prime numbers up to a certain number
# 2008 - Mike Golvach - eggi@comcast.net
#
# Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License
#

factorial ()  {
 local factorial_count=$1
 if [ "$factorial_count" -eq 0 ]
 then
  factorial_count=1
 fi
 for (( factor=$((factorial_count -1)); $factor >= 1; --factor ))
 do
  factorial_count=$(($factorial_count * $factor))
 done
 echo $factorial_count
}

prime_number ()  {
 local prime=$1
 p_minus_1=$(($prime - 1))
 fact_p_minus_1=`factorial "$p_minus_1"`
 fact_plus_1=$(($fact_p_minus_1 + 1))
 echo $fact_plus_1
}

highest_number=$1

if [ -z $highest_number ]
then
 echo
 echo "Usage: $0 highestNumber"
 echo
 exit 1
fi

if [ $highest_number -eq 0 ]
then
 echo
 echo "Sorry.  0 is not a prime number"
 echo
 exit 0
elif [ $highest_number -eq 1 ]
then
 echo
 echo "Sorry.  0 and 1 are not prime numbers"
 echo
 exit 0
fi

echo "Generating Prime Numbers Up To $highest_number"
if [ $highest_number -eq 2 ]
then
 echo
 echo -n "2" 
else
 echo
 echo -n "2 3 " 
fi

count=4
while [ $count -le $highest_number ]
do
 prime_return=`prime_number "$count"`
 prime_test=$(($prime_return % count))
 if [ $prime_test -eq 0 ]
 then
  echo -n "$count "
 fi
 count=$(($count + 1))
done

echo
echo
echo "All Set!"
echo

exit 0

, Mike

Simple Factorial Generation - Perl versus Bash

Hey there,

I've seen this floating around the boards, so I thought I'd add my 2 cents. Lots of folks (more homework? When will it end?) are looking for scripts to help them find the factorial of any given number.

For those of you who may not know, the factorial of a number is the number itself multiplied by all the numbers from 1 up to that number. So, the factorial of 3 is: 1 times 2 times 3 = 6

Some of the scripts I see are severely convoluted, so I thought I'd put this up here as a little homework help. It can be solved with Perl in 10 lines (Could be less if I wasn't so hung up on formatting ;)

Interestingly enough - it can be done with the same amount of lines in Linux's bash shell, like so (assuming a recursive function). Or, as I wrote in a previous post, you "could" do it in 1 ;)

factorial ()  {

local number=$1
if [ "$number" -eq 0 ]
then
    factorial=1
else
    let "next = number - 1"
    factorial $next
    let "factorial = $number * $?"
fi
return $factorial
}

This work is licensed under a
Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License

#!/usr/bin/perl

#
# 2007 - Mike Golvach - eggi@comcast.net
#
# Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License
#

print "factorial of: ";
chomp($factorial = <STDIN>);
$number = $factorial;
if ( $factorial == 0 ) {
 $factorial = 1;
}
for ( $factor = $factorial - 1; $factor >= 1; --$factor ) {
 $factorial *= $factor;
}
printf("Factorial of %d is : %g\n", $number, $factorial);

Enjoy,

, Mike

linux unix internet technology



l