mersenneforum.org (https://www.mersenneforum.org/index.php)
-   FactorDB (https://www.mersenneforum.org/forumdisplay.php?f=94)
-   -   What are the odds of a semiprime (https://www.mersenneforum.org/showthread.php?t=27074)

 MattcAnderson 2021-08-14 13:35

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'

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

 Dr Sardonicus 2021-08-14 14:00

[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 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?
<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

$$\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 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].

 bur 2021-08-16 12:45

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?

 charybdis 2021-08-16 13:12

[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].

 Dr Sardonicus 2021-08-16 15:36

[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 $$\nu$$ Primfaktoren zusammengesetzt sind[/i], Gött. Nachr. Math.-Phys. Kl. (1911), 361–381.

 bur 2021-08-23 05:25

It was at wikipedia or at stackexchange, in either instance maybe I got something wrong. Thanks for the links!

 MattcAnderson 2021-09-06 00:31

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

 Happy5214 2021-09-06 07:54

[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).

 MattcAnderson 2021-09-07 14:20

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

 Dr Sardonicus 2021-09-07 16:53

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 [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^70-6240221)/269383)
%1 = [1364961305782585979207, 1; 27196278181038383265924982533012091561386259, 1][/code]

Whoever has been submitting these numbers to factordb are IMO no better than saboteurs.

 Happy5214 2021-09-14 10:31

[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 P-1 or the user provides it.

All times are UTC. The time now is 07:48.