The Straight Dope

Go Back   Straight Dope Message Board > Main > General Questions

Reply
 
Thread Tools Display Modes
  #1  
Old 11-28-2000, 03:21 PM
C3 C3 is offline
Member
 
Join Date: Jan 2000
Posts: 4,040
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!
Reply With Quote
Advertisements  
  #2  
Old 11-28-2000, 03:28 PM
jeel jeel is offline
Guest
 
Join Date: Oct 2000
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?
Reply With Quote
  #3  
Old 11-28-2000, 03:33 PM
C3 C3 is offline
Member
 
Join Date: Jan 2000
Posts: 4,040
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.
Reply With Quote
  #4  
Old 11-28-2000, 03:56 PM
Enderw24 Enderw24 is offline
Member
 
Join Date: Sep 2000
Location: KC. MO -094 35.3 39 4.9
Posts: 10,219
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?!?
Reply With Quote
  #5  
Old 11-28-2000, 03:59 PM
jeel jeel is offline
Guest
 
Join Date: Oct 2000
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!
Reply With Quote
  #6  
Old 11-28-2000, 04:16 PM
Ptahlis Ptahlis is offline
Guest
 
Join Date: Apr 2000
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
Reply With Quote
  #7  
Old 11-28-2000, 04:25 PM
C3 C3 is offline
Member
 
Join Date: Jan 2000
Posts: 4,040
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!
Reply With Quote
  #8  
Old 11-28-2000, 04:39 PM
Cabbage Cabbage is offline
Guest
 
Join Date: Sep 1999
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)
Reply With Quote
  #9  
Old 11-28-2000, 04:49 PM
Lance Turbo Lance Turbo is offline
Guest
 
Join Date: Aug 1999
I too have never heard of semi-prime numbers. Are you sure that you're not thinking of relatively prime numbers?
Reply With Quote
  #10  
Old 11-28-2000, 06:50 PM
bibliophage bibliophage is offline
Charter Member
Charter Member
 
Join Date: Apr 2000
Location: Maine
Posts: 9,390
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
Reply With Quote
  #11  
Old 11-28-2000, 08:18 PM
Enderw24 Enderw24 is offline
Member
 
Join Date: Sep 2000
Location: KC. MO -094 35.3 39 4.9
Posts: 10,219
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?!?
Reply With Quote
  #12  
Old 11-28-2000, 09:13 PM
C3 C3 is offline
Member
 
Join Date: Jan 2000
Posts: 4,040
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?
Reply With Quote
  #13  
Old 11-28-2000, 09:20 PM
Cabbage Cabbage is offline
Guest
 
Join Date: Sep 1999
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)
Reply With Quote
  #14  
Old 11-28-2000, 10:07 PM
gazpacho gazpacho is offline
Charter Member
 
Join Date: Oct 1999
Posts: 5,088
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.
Reply With Quote
  #15  
Old 11-28-2000, 10:20 PM
Little Nemo Little Nemo is offline
Charter Member
 
Join Date: Dec 1999
Location: Western New York
Posts: 58,092
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.
Reply With Quote
  #16  
Old 11-28-2000, 10:25 PM
Little Nemo Little Nemo is offline
Charter Member
 
Join Date: Dec 1999
Location: Western New York
Posts: 58,092
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.
Reply With Quote
  #17  
Old 11-28-2000, 11:21 PM
gazpacho gazpacho is offline
Charter Member
 
Join Date: Oct 1999
Posts: 5,088
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/
Reply With Quote
  #18  
Old 11-29-2000, 01:13 PM
DrMatrix DrMatrix is offline
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.
Reply With Quote
  #19  
Old 11-29-2000, 01:55 PM
DrMatrix DrMatrix is offline
Charter Member
Charter Member
 
Join Date: Nov 1999
Location: New York State of Mind
Posts: 3,299
semi- not simi-
Reply With Quote
  #20  
Old 11-29-2000, 11:19 PM
Little Nemo Little Nemo is offline
Charter Member
 
Join Date: Dec 1999
Location: Western New York
Posts: 58,092
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?
Reply With Quote
  #21  
Old 11-30-2000, 10:47 PM
Little Nemo Little Nemo is offline
Charter Member
 
Join Date: Dec 1999
Location: Western New York
Posts: 58,092
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.
Reply With Quote
  #22  
Old 11-30-2000, 11:27 PM
Cabbage Cabbage is offline
Guest
 
Join Date: Sep 1999
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)
Reply With Quote
  #23  
Old 12-01-2000, 06:25 AM
AWB AWB is offline
Guest
 
Join Date: Jun 1999
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!
Reply With Quote
  #24  
Old 12-01-2000, 06:47 AM
waterj2 waterj2 is offline
Guest
 
Join Date: Mar 2000
Warning - Really bad pun

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



Bookmarks

Thread Tools
Display Modes

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 Jump


All times are GMT -5. The time now is 09:00 AM.


Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2014, vBulletin Solutions, Inc.

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

Send comments about this website to: webmaster@straightdope.com

Terms of Use / Privacy Policy

Advertise on the Straight Dope!
(Your direct line to thousands of the smartest, hippest people on the planet, plus a few total dipsticks.)

Publishers - interested in subscribing to the Straight Dope?
Write to: sdsubscriptions@chicagoreader.com.

Copyright 2013 Sun-Times Media, LLC.