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 ksmooth 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 
[QUOTE=MattcAnderson;585623]<snip>
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 ksmooth number where k is, say, less than 10,000. One of you might know, what are the odds that a C100 is semiprime? <snip>[/QUOTE]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 [tex]\pi_{2}(x)\;\sim\;\frac{x\log\log(x)}{\log(x)}[/tex] Absent any other information, a 100digit number is about 5.4 times as likely to be a P[sub]2[/sub] 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 10[sup]100/3[/sup], it is certain to be a P[sub]2[/sub]. 
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=Dr Sardonicus;585626]The standard result for products of two primes is[/QUOTE]What does "standard result" mean? 
[QUOTE=bur;585747]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.[/quote]
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 [URL="https://en.wikipedia.org/wiki/Prime_omega_function"]here[/URL], [URL="https://en.wikipedia.org/wiki/Hardy%E2%80%93Ramanujan_theorem"]here[/URL] and [URL="https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Kac_theorem"]here[/URL]. 
[QUOTE=bur;585747][QUOTE=Dr Sardonicus;585626]The standard result for products of two primes is[/QUOTE]What does "standard result" mean?[/QUOTE]As cited e.g. [url=https://arxiv.org/pdf/1908.09503.pdf]here[/url], the asymptotic result was proved by Landau over a century ago.
E. Landau, [i]Sur quelques problèmes relatifs à la distribution des numbres premiers[/i], Bull. Soc. Math. France 28 (1900), 25–38. E. Landau, [i]Über die Verteilung der Zahlen, welche aus [tex]\nu[/tex] Primfaktoren zusammengesetzt sind[/i], Gött. Nachr. Math.Phys. Kl. (1911), 361–381. 
It was at wikipedia or at stackexchange, in either instance maybe I got something wrong. Thanks for the links!

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 
[QUOTE=MattcAnderson;587360]Also, I continue to factor composite numbers for factordb.com This is fun for me and useful for anyone who may want these results.[/QUOTE]
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). 
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 
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^706240221)/269383 and fed it to the PariGP [i]online calculator[/i]. (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^706240221)/269383) %1 = [1364961305782585979207, 1; 27196278181038383265924982533012091561386259, 1][/code] Whoever has been submitting these numbers to factordb are IMO no better than saboteurs. 
[QUOTE=Dr Sardonicus;587453]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.[/QUOTE] 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 P1 or the user provides it. 
All times are UTC. The time now is 18:16. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.