Talk:Semiprime

wanna help

How is NINE a semi prime numbER???

please someone wanna tell me why NINE is or isnt semi prime?

It's semiprime because 9 = 3 x 3 is the product of two prime factors, namely 3 and 3. All squares of primes are semiprimes.

Probability

the probability that P is prime is 1/ln(P). Is there a similar result for semiprimes? (-Ozone-, Valentines Day(wrong computer for sig))

That's a good question. I don't know of any density result for semiprimes. I tried to come up with some stuff, but I don't know if it's correct. I'm sure there's something in the literature. Deco 19:46, 14 February 2006 (UTC)

Indeed it would be nice to have something about that on this page. Some information is available at (sequence A066265 in the OEIS) - number of semiprimes < 10^n ; it decreases from 33% for n=1 to 11.7% for n=14. — MFH:Talk 12:42, 1 October 2007 (UTC)

From this mathoverflow discussion, a crude result for asymptotic probability looks (from Gerry Myerson's answer) to be $\log(\log(x))/\log(x)+O(1/\log(x))$, shown by Landau; there are mentions of more recent results of Tenenbaum and of Hwang that may bear further reading.

Note that they deal with numbers having "distinct prime factors", but squares of primes are rare enough it doesn't make any significant difference if you allow them too. Hv (talk) 09:19, 16 January 2013 (UTC)

Can't prove what is by proving what it is not

the largest known semiprime will always be the square of the largest known prime, unless the factors of the semiprime are not known.

Can't prove it's a semiprime when the factors are not known. Is it conceivable someone will find a way? Yes but concievable is a weasel word. It is conceivable that you will inherite $1000000 tomorrow. I think it's not proper to present something as encyclopedic because it's conceivable unless it is commonly accepted. Please provide a source. -- NYCDA (talk) 18:28, 16 November 2007 (UTC)

Your use of "conceivable" is apparently referring to my edit summary in [1]. Edit summaries don't require sources and "conceivable" has never been in the article. The original article claim was "the largest known semiprime will always be the square of the largest known prime." I added "... unless the factors of the semiprime are not known." Whether or not a suitable way to prove large semiprimes is ever found, the claim with my addition is by definition correct so I don't think it requires a source. It might be formulated differently, but: Without a reliable source, I don't think the article should add a clarifying claim that there is currently no feasible semiprime proof method which would work above the largest known prime. The original claim will be false if somebody does prove a semiprime above the largest known prime. You reverted to the original claim which is unsourced and has unknown truth value. It essentially makes an unstated prediction that such a semiprime will never be found, where my addition makes no prediction either way.

It's possible to prove some small semiprimes without knowing their factors. For example, make a probable prime test to prove a number is composite without knowing a factor, and then do trial division to the cube root. If no factor is found then the number must be a semiprime. Such trial division is only feasible at small sizes where it would be easy to find the factors with known factorization methods, but who knows what else might be discovered later. I have seen a selfpublished (and thus unsuitable for Wikipedia) semiprime proof at a larger size where trial division is impossible: A proof of semiprimality at 35205 digits. But the author already knew the factorization without revealing the factors, and the method may be infeasible above the largest known prime. I have not checked the mathematics of the semiprime proof. -- PrimeHunter (talk) 19:33, 16 November 2007 (UTC)

I agree with PrimeHunter here. Both statements are unsourced, but PrimeHunter's is clearly mathematically accurate, whereas the original statement may become false if a semiprime with unknown factors were ever found. Dcoetzee 20:52, 17 November 2007 (UTC)

I have no objection is the prediction is commonly accepted. But if both statement can't be sourced, then I think it's better if it's reworded to

the largest known semiprime (today) is the square of the largest known prime.

Or

the largest known semiprime is (insert number here) which is the square of the largest known prime (insert number here)

If a semiprime is ever discovered with unknown factors, it can be changed in the future. I think it's better to remove both unsourced claims instead of countering one with another. NYCDA (talk) 16:55, 19 November 2007 (UTC)

Original Research

I believe

so the largest known semiprime will always be the square of the largest known prime, unless the factors of the semiprime are not known.

is OR since we all agree it can't be source but is mathmatically sound. I do not believe

Currently, the largest known semiprime is (232,582,657 − 1)2, which has over 19 million digits. This is the square of the largest known prime number; the square of any prime number is semiprime.

is "NOT" OR since a semiprime is the product of 2 primes and the square of a prime is certainlly the product of 2 primes. I would like to see "so the largest known semiprime will always be the square of the largest known prime, unless the factors of the semiprime are not known." removed from the wiki but the rest kept. Is that acceptable to everyone?NYCDA (talk) 18:07, 28 November 2007 (UTC) {edit: fixed a the typo}.

{edit: Added "NOT", that was what I meant. Sorry I left it out on the original post} NYCDA 20:50, 30 November 2007 (UTC)

The complete statement makes it clear that unless there is some way to show that numbers are semiprime without factoring them, the question of the largest known semi-prime is uninteresting since it will always be just the square of the largest known prime. OR or not, this is a trivial result. But if you leave out the second part, which is no more OR than the first, then a casual reader might think the result has more significance than it does. That's why I object to having just the first part. --agr (talk) 21:41, 28 November 2007 (UTC)

I just examined the external link http://mathworld.wolfram.com/Semiprime.html and it actually does claim: "The square of any prime number is by definition a semiprime. The largest known semiprime is therefore the square of the largest known prime."

MathWorld is usually considered a reliable source by Wikipedia but I suspect the editor didn't realize the possibility that semiprimes might be proved without knowing a factor. Or maybe "therefore" isn't meant to imply that it will always be so. Another source is http://primes.utm.edu/glossary/page.php?sort=Semiprime which says: "The largest known semiprime is always the square of the largest known prime." It's at The Prime Pages which I also normally consider a reliable source. (Note: I have corrected many errors in both MathWorld and the Prime Pages by mailing the editors) I don't like it but according to normal Wikipedia policies, it appears more appropriate to report this now sourced claim than to add the caveat about possibly unknown factors. But we don't have to mention all sourced claims so I suggest a compromise: Remove everything about the largest known semiprime, also the claim that it's currently the square of the largest known prime. PrimeHunter (talk) 23:09, 28 November 2007 (UTC)

I'd suggest replacing the paragraph with "Absent a test for semiprimality that doesn't require factoring, the largest known semiprime will always be the square of the largest known prime." and leave it at that. We are allowed to include informal proofs. Otherwise, I'd say drop the whole thing.--agr (talk) 23:45, 28 November 2007 (UTC) Update: I posted a correction to Mathworld and got the following interesting response :"...There are unfactored, proven semiprimes. For an example, see Don Reble's note at http://www.graysage.com/djr/isp.txt --Ed Pegg Jr" Therefore I withdraw my objection to NYCDA's original proposal.

I can think of one application of this result. One could use Reble's semiprime N as an RSA public key to write secret notes to the future, on the assumption that techniques will eventually be developed to factor this number (it's 3599 bits long), but not anytime soon. Of course one has to trust Reble not to have created N from factors he knew. Ideally there would be a way to generate such numbers with an algorithm that began at a random starting point.--agr (talk) 20:52, 29 November 2007 (UTC)

I'd go so far as to suggest that because many otherwise reliable sources make the claim that "the largest known semiprime is always the square of the largest known prime", we have an imperative to not only avoid repeating the misinformation but correct it. Part of the the mission of an encyclopedia is to dispel misinformation. However, since the possibility of a counterexample of that magnitude existing is not predicted or suspected, it would be appropriate to use wording that plays down this possibility, such as a parenthetical remark. I don't like the wording that refers to a "test for semiprimality" because it's entirely possible that a single semiprime may be proven semiprime by a technique that does not generalise. Dcoetzee 22:59, 29 November 2007 (UTC)

Good news! I mailed Professor Chris Caldwell, author of http://primes.utm.edu/glossary/page.php?sort=Semiprime at The Prime Pages, and he has changed it to say:

"The largest known factored semiprime is always the square of the largest known prime. Historically this has also been the largest proven semiprime. It is conceivable, but unlikely, that we may someday be able to show a larger number is composite, and has only two prime divisors.

Small examples of proven, unfactored, semiprimes can be easily constructed (these have been called interesting semiprimes). In 2005 Don Reble gave the following example.

2354024638195369096484615970884339..."

PrimeHunter 00:58, 2 December 2007 (UTC)

I have used the new source in [2]. PrimeHunter 01:14, 4 December 2007 (UTC)

I can live with it but I don't like the wording. I'm contradiction myself by saying I'm 100% sure unless ... so I'm not really 100% sure after all. How about changing it to

The square of any prime number is a semiprime. The largest known semiprime is the square of the largest known prime. It is conceivable that somebody could find a way to prove a larger number is a semiprime without knowing the two factors, but so far that has only happened for smaller semiprimes.

NYCDA (talk) 22:55, 5 December 2007 (UTC)

Sounds good, but for clarity I'd change the last clause to "but so far such a proof has only been given for smaller semiprimes" with a ref. Also, can we say that the largest square-free semiprime is the product of the largest known prime and the next largest known prime?--agr (talk) 02:26, 6 December 2007 (UTC)

I'm not sure how much of the existing paragraph NYCDA wants to keep. It already says "This is the square of the largest known prime." How about this:

As of 2007, the largest known semiprime is (2^32,582,657 − 1)², which has over 19 million digits. The square of any prime number is a semiprime. The largest known semiprime is the square of the largest known prime. It is conceivable that somebody could find a way to prove a larger number is a semiprime without knowing the two factors, but so far such a proof has only been given for smaller semiprimes.

agr wrote "the largest square-free semiprime is the product of the largest known prime and the next largest known prime". I'm certain this is true with "known" inserted in "the largest known square-free ...", but it's not directly sourced. If p < q are the largest known primes then there could theoretically be a proven semiprime with unknown factors between pq and q². It might be argued that [3] doesn't appear to allow this possibility. But if no source speaks about the largest known square-free semiprime or gives an upper limit for the largest proven semiprime without known factors, then I don't think we should do it. PrimeHunter (talk) 03:07, 6 December 2007 (UTC)

I think the new wording are fine. I don't think "the largest known square-free semiprime.." needs to be sourced if you want to add it to the article. This is just fact building on facts. There is no hyposis here. If we can show consenses then we wouldn't need to worry if someone raises an OR objection. NYCDA (talk) 19:43, 6 December 2007 (UTC)

Axiomatic?

"In fact, there are no numbers that are the product of two primes that have any composite factors".

Sounds obvious, like Playfair's parallel postulate. Any proof available?Koroke (talk) 00:11, 22 July 2013 (UTC)

This easily follows from the uniqueness of prime factorisation. If p, q are prime and the composite number r divides pq, then r = ab for some integers a, b > 1 (by definition of composite), and pq = abn for some integer n. Assume n > 1. Let P(n) mean the smallest prime factor of n. Then P(a)P(b)P(n) divides pq, or pq = P(a)P(b)P(n)m for some integer m. Then we have the product of two primes equal to a product of at least three primes, which contradicts uniqueness of factorisation. The only way out of the contradiction is to retract the assumption n > 1. Therefore n = 1, i.e. r = pq. 2.24.117.123 (talk) 18:29, 11 November 2015 (UTC)

Portrait and landscape rectangular images

"The number 1679 = 23 ⋅ 73 was chosen because it is a semiprime and therefore can only be arranged into a rectangular image in one way." But of course there are actually two ways: 1679 = 23 ⋅ 73 = 73 ⋅ 23. These correspond to the two rectangular page options on a printer: portrait and landscape. And similarly for all other nonsquare semiprimes. Is there a standard concise way to reword the statement to correct this? Perhaps by requiring the prime factors to be in ascending order? Dirac66 (talk) 21:07, 17 June 2018 (UTC)

There is only one rectangular image up to rotations and reflections of the image plane. —David Eppstein (talk) 05:45, 18 June 2018 (UTC)

Thanks. I have added your qualifying phrase to the article so that it is now mathematically correct. I placed it in parentheses so that the reader can skip it and still get the general idea. Dirac66 (talk) 19:37, 19 June 2018 (UTC)

Today, Hdjensofjfnen has been edit-warring to reinstate the false claim that there are exactly two images that can be obtained (there are eight, if you count rotations and reflections as different from each other for some reason but require the image to be axis-aligned, or infinitely many if you don't require it to be axis-aligned). I'm out of undoes before I hit WP:3RR (as is Hdjensofjfnen). Someone else want to take over? —David Eppstein (talk) 01:56, 21 September 2018 (UTC)

@David Eppstein: I really dislike that you call me ignorant on my talk page, and it seems to be you who's edit warring. Here's a better example: 101101010001001. 15 is a semiprime (3 x 5). Now:

101

101

010

001

001

is distinct from

10110

10100

01001. Hdjensofjfnen (If you want to trout me, go ahead!) 03:44, 21 September 2018 (UTC)

Ok, I take it back. Your better example is much more convincing. There is only one shape of rectangle but there are two different ways of arranging the dots into it. —David Eppstein (talk) 06:22, 21 September 2018 (UTC)

@David Eppstein: Thank you for being receptive. Hdjensofjfnen (If you want to trout me, go ahead!) 15:07, 21 September 2018 (UTC)