mersenneforum.org What are the odds of a semiprime
 Register FAQ Search Today's Posts Mark Forums Read

 2021-08-14, 13:35 #1 MattcAnderson     "Matthew Anderson" Dec 2010 Oregon, USA 100810 Posts What are the odds of a semiprime Hi again all, I have been helping factordb.com for some time now. There is a -report factors- text box, and I have given the database a few of them. On the Status menu option, I click on 'composite numbers without known factors' list link. Right now my personal computer is working on an 81 digit number. This C81 might be a semiprime, that is a product of two primes, or possibly a k-smooth number where k is, say, less than 10,000. One of you might know, what are the odds that a C100 is semiprime? Regards, Mattcanderson
2021-08-14, 14:00   #2
Dr Sardonicus

Feb 2017
Nowhere

536910 Posts

Quote:
 Originally Posted by MattcAnderson Right now my personal computer is working on an 81 digit number. This C81 might be a semiprime, that is a product of two primes, or possibly a k-smooth number where k is, say, less than 10,000. One of you might know, what are the odds that a C100 is semiprime?
If your number were the product of primes < 10000 your program would have it factored by now, I would hope.

The standard result for products of two primes is

$\pi_{2}(x)\;\sim\;\frac{x\log\log(x)}{\log(x)}$

Absent any other information, a 100-digit number is about 5.4 times as likely to be a P2 as it is to be a prime.

A significant lower bound on the smallest factor will change the odds. For example, if a C100 has no prime factors less than 10100/3, it is certain to be a P2.

2021-08-16, 12:45   #3
bur

Aug 2020
79*6581e-4;3*2539e-3

48910 Posts

In that regard, the number of distinct prime factors of n can be estimated by 1.38*log(n)/log(log(n)), I think - though that seems quite large for small numbers. Composites < 100 mostly habe less than 3 distinct factors.

For the estimated number of prime factors (not necessarily distinct) I couldn't find a formula, just that it is the big Omega prime function. Is there a similarly simple estimate?

Quote:
 Originally Posted by Dr Sardonicus The standard result for products of two primes is
What does "standard result" mean?

Last fiddled with by Dr Sardonicus on 2021-08-16 at 15:31 Reason: Attributing quote

2021-08-16, 13:12   #4
charybdis

Apr 2020

25116 Posts

Quote:
 Originally Posted by bur In that regard, the number of distinct prime factors of n can be estimated by 1.38*log(n)/log(log(n)), I think - though that seems quite large for small numbers. Composites < 100 mostly habe less than 3 distinct factors.
I have no idea where you've got this, because it's completely wrong. The actual expectation is around log log n, whether we count repeated prime factors or not. See here, here and here.

2021-08-16, 15:36   #5
Dr Sardonicus

Feb 2017
Nowhere

7·13·59 Posts

Quote:
Originally Posted by bur
Quote:
 Originally Posted by Dr Sardonicus The standard result for products of two primes is
What does "standard result" mean?
As cited e.g. here, the asymptotic result was proved by Landau over a century ago.

E. Landau, Sur quelques problèmes relatifs à la distribution des numbres premiers, Bull. Soc. Math. France 28 (1900), 25–38.

E. Landau, Über die Verteilung der Zahlen, welche aus $\nu$ Primfaktoren zusammengesetzt sind, Gött. Nachr. Math.-Phys. Kl. (1911), 361–381.

 2021-08-23, 05:25 #6 bur     Aug 2020 79*6581e-4;3*2539e-3 48910 Posts It was at wikipedia or at stackexchange, in either instance maybe I got something wrong. Thanks for the links!
 2021-09-06, 00:31 #7 MattcAnderson     "Matthew Anderson" Dec 2010 Oregon, USA 17608 Posts Thanks for the informative replies. Also, I continue to factor composite numbers for factordb.com This is fun for me and useful for anyone who may want these results. Matt Last fiddled with by MattcAnderson on 2021-09-06 at 00:35 Reason: added enthusiasm
2021-09-06, 07:54   #8
Happy5214

"Alexander"
Nov 2008
The Alamo City

3×7×37 Posts

Quote:
 Originally Posted by MattcAnderson Also, I continue to factor composite numbers for factordb.com This is fun for me and useful for anyone who may want these results.
I hope and pray that by "factor[ing] composite numbers for factordb.com," you mean submitting factors for numbers already on the site (a great and undervalued service to the factoring community) and not adding brand new numbers with full or partial factorizations (which is considered spam unless the numbers are part of a useful set, like a useful aliquot sequence or numbers of certain special forms, and bloats the database in any case).

 2021-09-07, 14:20 #9 MattcAnderson     "Matthew Anderson" Dec 2010 Oregon, USA 3F016 Posts Yes Happy5214, I take numbers from under the status menu in factordb.com. These are numbers that factordb.com wants full prime factorizations for. I find full prime factorization and submit my results in the box on the website. Regards, Matt
 2021-09-07, 16:53 #10 Dr Sardonicus     Feb 2017 Nowhere 14F916 Posts The list of "Composites without known factors" has a bunch of ludicrously small numbers (the smallest is 22 decimal digits IIRC), and page after page of 65 decimal digit numbers of the form (10^70 - A)/B. As an example, I took 1100000002659432902 (10^70-6240221)/269383 and fed it to the Pari-GP online calculator. (I was curious if it would take too long or fail for some other reason.) It did have to increase the stack size, but even so, it got the answer: Code: ? factor((10^70-6240221)/269383) %1 = [1364961305782585979207, 1; 27196278181038383265924982533012091561386259, 1] Whoever has been submitting these numbers to factordb are IMO no better than saboteurs.
2021-09-14, 10:31   #11
Happy5214

"Alexander"
Nov 2008
The Alamo City

77710 Posts

Quote:
 Originally Posted by Dr Sardonicus The list of "Composites without known factors" has a bunch of ludicrously small numbers (the smallest is 22 decimal digits IIRC), and page after page of 65 decimal digit numbers of the form (10^70 - A)/B. [...] Whoever has been submitting these numbers to factordb are IMO no better than saboteurs.
I wonder if anyone would be willing to put up cash to help clear the backlog (toward e.g. cloud time or a dedicated factoring box attached to the server) in exchange for Syd enacting meaningful and effective measures to end this incessant deluge of spam? Possible measures that I can think of include an IP address/range blacklist, a flood limit (e.g. 100 new IDs per hour, with exceptions given for approved accounts/programs and numbers given with full valid factorizations), and not storing query results in the database for users/IPs who are beyond their limit or are blacklisted unless the factorization can be dispatched with TF/rho/minimal P-1 or the user provides it.

Last fiddled with by Happy5214 on 2021-09-14 at 10:32 Reason: First part kind of a question

 Similar Threads Thread Thread Starter Forum Replies Last Post ONeil ONeil 8 2020-12-06 06:45 ONeil ONeil 2 2020-12-01 04:14 enzocreti enzocreti 3 2020-09-02 16:35 danaj Computer Science & Computational Number Theory 12 2018-10-14 03:16 tal Msieve 31 2011-05-22 18:17

All times are UTC. The time now is 06:06.

Tue Jan 25 06:06:10 UTC 2022 up 186 days, 35 mins, 0 users, load averages: 1.38, 1.36, 1.33