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 23 = 3 * 2 * 1 --> Factorial equals 64 = 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

...

+ 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

...

+++ (( --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