Remember Me?

 Straight Dope Message Board Remember Me?

#1
11-28-2000, 04:21 PM
 C3 Member Join Date: Jan 2000 Posts: 4,109
A woman that my husband works with has a kid who is studying "semi-prime" numbers. This is not something that Gen-X liberal arts people in my neck of the woods have heard of...some sort of "new math" I take it. The co-worker gave the definition of semi-prime as a number divisible by itself, 1, and one other number (for instance, 9....1X9 and 3X3). I did a search on Google, however, and found a definition of semi-prime to be a number with only two sets of factors (for instance, 33...1X33 and 3X11).

Which is correct? Any extraneous knowledge on this subject is also welcome! Thanks!
#2
11-28-2000, 04:28 PM
 jeel Guest Join Date: Oct 2000 Posts: 188
Sounds like they are both right!

For example: 6 has factors 2,3 and 6,1 (just two sets of factors: same as your second definition) but one of the sets is the number itself and 1. (Same as your first definition)

There is no way you can have a number that has two sets of factors without one of the sets being the number itself and 1!

Of course 6 also has the factors -2,-3 and -6,-1

So.....???? Who knows what the definition of semi-prime is good for?
#3
11-28-2000, 04:33 PM
 C3 Member Join Date: Jan 2000 Posts: 4,109
Actually, they're not the same thing. The first definition includes three numbers: the number itself, 1, and one other number. So in the example "9", there are two sets of factors, but only 3 numbers (1, 3, 9). With the second definition, there is a possibility of 4 numbers: 1, 3, 11, 33. I guess the first definition is just more restrictive.
#4
11-28-2000, 04:56 PM
 Enderw24 Member Join Date: Sep 2000 Location: KC. MO -094 35.3 39 4.9 Posts: 10,583
I don't know which is the correct definition, C3, the first or the second. However, I can tell you that either definition yields an infinite number of numbers.

Assuming that the true definition of semi-prime numbers is the first one, the only numbers available are odd, square numbers whose square root = a prime number. Seems like a small amount, huh? But another way to put it is: take any prime, multiply it by itself, and you get a semi-square number. Since there are an infinite number of primes, there must, logically, be an infinite number of semi-primes.

There is, on average, a prime number once out of every seven numbers. That's, IMO, quite astonishing. This is true no matter how far up the ladder you go (and they've found primes with almost TEN MILLION numbers contained in it).

Here's where math goes fuzzy because I'm not bothering to figure it out. If there's a prime number once every seven, it seems safe to assume that semi-prime numbers occur, on average, once in every 49 numbers. But, while that may in fact be correct, that is as close to a WAG as I can get so don't spout it off as fact.
__________________
Puedo tenerz las hamburguesas conz queso?!?
#5
11-28-2000, 04:59 PM
 jeel Guest Join Date: Oct 2000 Posts: 188
Quote:
 Originally posted by C3 Actually, they're not the same thing. The first definition includes three numbers: the number itself, 1, and one other number. So in the example "9", there are two sets of factors, but only 3 numbers (1, 3, 9). With the second definition, there is a possibility of 4 numbers: 1, 3, 11, 33. I guess the first definition is just more restrictive.
I may have read the first definition a bit wrong. When you say that they are divisible by 1 and "only one" other number...now I get it. But still, I teach algebra at a community college. I have still never heard of Semi-Prime numbers before within our curriculum!
#6
11-28-2000, 05:16 PM
 Ptahlis Guest Join Date: Apr 2000 Posts: 1,186
What, may I ask, would be the use of such a number set? What's it good for?
__________________
You are the true Lord of the Dance- no matter what those idiots at work say. -- Weird Al
#7
11-28-2000, 05:25 PM
 C3 Member Join Date: Jan 2000 Posts: 4,109
Quote:
 Originally posted by Ptahlis What, may I ask, would be the use of such a number set? What's it good for?
Oh, Good Lord, who the hell knows?! I didn't think I'd ever use Venn Diagrams either, but, lo and behold, right here in this very thread...a set and a subset! I am definitely the wrong person to ask, though, about the relevance of random math definitions!
#8
11-28-2000, 05:39 PM
 Cabbage Guest Join Date: Sep 1999 Location: Radford, VA Posts: 2,387
Quote:
 There is, on average, a prime number once out of every seven numbers. That's, IMO, quite astonishing. This is true no matter how far up the ladder you go (and they've found primes with almost TEN MILLION numbers contained in it).
Actually, that's not true. If we let pi(n) be the number of prime numbers less than or equal to n, the prime number theorem says pi(n) approaches n/log(n) asymptotically. So, there tend to be n/log(n) primes for every n numbers, and that ratio, 1/log(n), goes to zero as n goes to infinity.

As for semi primes, I'm a grad student in math, and I've never heard that term before, so I doubt it's very common. Maybe some text book made it up as a topic for class. If it's a nonstandard topic, then you may likely find many different definitions for it, depending on the source.
__________________
...ebius sig. This is a moebius sig. This is a mo...
(sig line courtesy of WallyM7)
#9
11-28-2000, 05:49 PM
 Lance Turbo Guest Join Date: Aug 1999 Location: Asheville, NC Posts: 2,551
I too have never heard of semi-prime numbers. Are you sure that you're not thinking of relatively prime numbers?
#10
11-28-2000, 07:50 PM
 bibliophage Charter Member Charter Member Join Date: Apr 2000 Location: Maine Posts: 10,253
A search of Dr. Math turns up nothing. I suspect that it's just something some math teacher teaches for the sake of teaching it, not because it's at all useful. But I'm not going to go out on a limb and say it's not useful, just that I can't think of any use for it. All I know is that I got through differential and integral calculus and differential equations and multivariate calculus classes in college without ever hearing of the concept of a semi-prime number. I never did take a numbers theory class, and if it is important, that's probably where it would turn up. I have to wonder what grade this kids is in who's studying it.

One definition is found here: http://www.mcn.net/~jimloy/semiprim.html
#11
11-28-2000, 09:18 PM
 Enderw24 Member Join Date: Sep 2000 Location: KC. MO -094 35.3 39 4.9 Posts: 10,583
After reading Cabbages' post and reviewing a site on the internet dedicated to prime numbers, I'm going to have to retract my previous statement. Prime numbers, while stretching to infinity, do, in fact, get smaller in frequency the farther up the chain one goes.

http://www.utm.edu/research/primes/glossary has a glossary of terms, and semi-prime isn't one of them. Check it out though, the site is quite informative.
__________________
Puedo tenerz las hamburguesas conz queso?!?
#12
11-28-2000, 10:13 PM
 C3 Member Join Date: Jan 2000 Posts: 4,109
Thanks for the links...I'll study them tomorrow a.m. when I have more time. We're going to make this kid a star!

For anyone who's curious, my husband estimates that the son of his co-worker is 12 (but maybe 11). We think this is something the teacher probably stuck in the lesson to give the kids something to do. The actual assignment was to come up with 4 numbers greater than 35 that are semi-prime numbers. He's set...we gave him 49, 121, 169, & 361. Does that sound good?
#13
11-28-2000, 10:20 PM
 Cabbage Guest Join Date: Sep 1999 Location: Radford, VA Posts: 2,387
Yep, that looks good. Of all the definitions given here for semi-primes (actually, I think there were only two), any prime squared fits the definition. So just keep squaring some primes to get as many as you like!
__________________
...ebius sig. This is a moebius sig. This is a mo...
(sig line courtesy of WallyM7)
#14
11-28-2000, 11:07 PM
 gazpacho Guest Join Date: Oct 1999 Posts: 5,635
Semi prime numbers are numbers that are the product of 2 prime numbers.

They are incredibly usefull and I can't beleive that this thread has been up for this long without somebody giving the use.

Semi prime numbers make up the basis of how secure web sites work. Exchanging really large semi prime numbers is how secure website are secure without a key having to be sent in a non public manor. I will try and find my texts on the subject and post something better.
#15
11-28-2000, 11:20 PM
 Little Nemo Charter Member Join Date: Dec 1999 Location: Western New York Posts: 75,602
Quote:
 The co-worker gave the definition of semi-prime as a number divisible by itself, 1, and one other number (for instance, 9....1X9 and 3X3).
Quote:
 Assuming that the true definition of semi-prime numbers is the first one, the only numbers available are odd, square numbers whose square root = a prime number. Seems like a small amount, huh? But another way to put it is: take any prime, multiply it by itself, and you get a semi-square number. Since there are an infinite number of primes, there must, logically, be an infinite number of semi-primes.
They're somewhat more common than this. The definition doesn't restrict itself only to the squares of prime numbers. Any number that could be expressed as P to the Nth power, where P is a prime number and N is any integer greater than one, is a semi-prime number (assuming that this definition is correct). So for every prime number there would be an infinite amount of corresponding semi-prime numbers.
#16
11-28-2000, 11:25 PM
 Little Nemo Charter Member Join Date: Dec 1999 Location: Western New York Posts: 75,602
Darn the lack of an edit feature. When I read my post, I realized I was wrong. The definition would restrict semi-prime numbers only to the squares of primes. Otherwise the lesser exponents of the prime would also be factors. So ignore what I posted above.
#17
11-29-2000, 12:21 AM
 gazpacho Guest Join Date: Oct 1999 Posts: 5,635
Searching for crypo stuff on the web is a real hassle because there is so much out there. But most of the stuff is just a rehash of listing popular encryption schemes or adds for companies which will sell you encrpytion software.

The basic algorithm for RSA encryption:
Choose to really big prime numbers called P and Q. Then choose another number E.

E must have no common denominators with (P-1)*(Q-1).

Use P and Q to find N N=Q*P

N is a semi prime number becuase it has two factors p and q which are prime numbers.

Find D where (E*D) mod((P-1)*(Q-1))

x mod y is the remainder of x/y.

D and N are you private key which only you know.

Publish N and E to every one this is your public key.

If someone else wants to send you a message they use the N and E you have published.

To encrypt your message convert you message to a string of numbers which are not bigger than N.

take this string of numbers and make a new string of numbers with the formula:

C=M^E(mod N)

M one of the string of numbers
C is the corisponding new number

They then send you the string of new numbers

To decrypt the message

M=(C^D) mod (N)

This works because is is very har to find P and Q given N if P and Q are really big.

Here is a sort of goofy RSA simulator. There may be some dumb pop up window associated with going to the site.

http://my.netian.com/~dubs37/english/
#18
11-29-2000, 02:13 PM
 John Kentzel-Griffin Charter Member Charter Member Join Date: Nov 1999 Location: New York State of Mind Posts: 3,299
A simi-prime number is just an optimistic simi-composite number.
__________________
That's not a tau neutrino in my pocket; I've got a hadron.
#19
11-29-2000, 02:55 PM
 John Kentzel-Griffin Charter Member Charter Member Join Date: Nov 1999 Location: New York State of Mind Posts: 3,299
semi- not simi-
#20
11-30-2000, 12:19 AM
 Little Nemo Charter Member Join Date: Dec 1999 Location: Western New York Posts: 75,602
Quote:
 There is, on average, a prime number once out of every seven numbers. That's, IMO, quite astonishing. This is true no matter how far up the ladder you go (and they've found primes with almost TEN MILLION numbers contained in it).
After my previous post, I should avoid higher mathematics, but what the hell.

Ignoring my mistake on the definition, consider the numbers that can be defined by the expression P to the Nth power. Every number generated by this expression would be unique, so I'm going to stand by my previous assertion that for every prime number there are an infinite and unique set of exponents of that number.

Now if this is true, how can one out of seven integers be prime? If that were true then only six out of every seven numbers in not a prime which leads to the conclusion that every prime number can only have a maximum of six numbers that are products of it.

Maybe dealing with infinite sets has thrown me totally off base, but does this make any sense?
#21
11-30-2000, 11:47 PM
 Little Nemo Charter Member Join Date: Dec 1999 Location: Western New York Posts: 75,602
A few hours after writing my last post, I was reading the new issue of Scientific American. By an amzing coincidence, they had an article on the spacing of prime numbers. This said that the ratio of 1:6 (2x3) only holds for the first few hundred primes. It then drops to 1:30 (2x3x5) and later to 1:210 (2x3x5x7) and so on. So primes do become rarer.
#22
12-01-2000, 12:27 AM
 Cabbage Guest Join Date: Sep 1999 Location: Radford, VA Posts: 2,387
Yeah, not only do the primes become rarer, but their "density" goes to zero the farther you go out. See my earlier post a ways up the page.
__________________
...ebius sig. This is a moebius sig. This is a mo...
(sig line courtesy of WallyM7)
#23
12-01-2000, 07:25 AM
 AWB Guest Join Date: Jun 1999 Location: San Antonio, TX Posts: 5,519
I finally found a definition of semiprime numbers: A semiprime (also called a 2-almost prime) is an integer that is the product of exactly two primes (possibly the same).

So it looks like everyone was right.

I got this from Jim Loy's Mathematics Page.
__________________
Merry Christmas from Courtney, the cutest child in the world!
#24
12-01-2000, 07:47 AM
 waterj2 Guest Join Date: Mar 2000 Location: Jamaica Plain, MA Posts: 6,061

Quote:
 Originally posted by DrMatrix semi- not simi-
Yeah, a simi-prime is one without opposable thumbs.

 Bookmarks

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Main     About This Message Board     Comments on Cecil's Columns/Staff Reports     General Questions     Great Debates     Elections     Cafe Society     The Game Room     Thread Games     In My Humble Opinion (IMHO)     Mundane Pointless Stuff I Must Share (MPSIMS)     Marketplace     The BBQ Pit

All times are GMT -5. The time now is 08:55 PM.

 -- Straight Dope v3.7.3 -- Sultantheme's Responsive vB3-blue Contact Us - Straight Dope Homepage - Archive - Top

Send questions for Cecil Adams to: cecil@straightdope.com