mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FactorDB

Reply
 
Thread Tools
Old 2021-08-14, 13:35   #1
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

2·5·89 Posts
Default 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
MattcAnderson is offline   Reply With Quote
Old 2021-08-14, 14:00   #2
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3·5·331 Posts
Default

Quote:
Originally Posted by MattcAnderson View Post
<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>
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.
Dr Sardonicus is offline   Reply With Quote
Old 2021-08-16, 12:45   #3
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

39810 Posts
Default

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 View Post
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
bur is offline   Reply With Quote
Old 2021-08-16, 13:12   #4
charybdis
 
charybdis's Avatar
 
Apr 2020

22×3×41 Posts
Default

Quote:
Originally Posted by bur View Post
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.
charybdis is offline   Reply With Quote
Old 2021-08-16, 15:36   #5
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3·5·331 Posts
Default

Quote:
Originally Posted by bur View Post
Quote:
Originally Posted by Dr Sardonicus View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2021-08-23, 05:25   #6
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

6168 Posts
Default

It was at wikipedia or at stackexchange, in either instance maybe I got something wrong. Thanks for the links!
bur is offline   Reply With Quote
Old 2021-09-06, 00:31   #7
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

11011110102 Posts
Default

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
MattcAnderson is offline   Reply With Quote
Old 2021-09-06, 07:54   #8
Happy5214
 
Happy5214's Avatar
 
"Alexander"
Nov 2008
The Alamo City

75810 Posts
Default

Quote:
Originally Posted by MattcAnderson View Post
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).
Happy5214 is offline   Reply With Quote
Old 2021-09-07, 14:20   #9
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

2×5×89 Posts
Default

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
MattcAnderson is offline   Reply With Quote
Old 2021-09-07, 16:53   #10
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3×5×331 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Old 2021-09-14, 10:31   #11
Happy5214
 
Happy5214's Avatar
 
"Alexander"
Nov 2008
The Alamo City

2·379 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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
Happy5214 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Semiprime Squared Prime Test ¿ ONeil ONeil 8 2020-12-06 06:45
Semiprime and Prime Generator ONeil ONeil 2 2020-12-01 04:14
...factorial(n) plus/minus 1 is semiprime enzocreti enzocreti 3 2020-09-02 16:35
Semiprime counting danaj Computer Science & Computational Number Theory 12 2018-10-14 03:16
Factored my first SemiPrime -Some Questions tal Msieve 31 2011-05-22 18:17

All times are UTC. The time now is 00:42.


Sat Oct 16 00:42:22 UTC 2021 up 84 days, 19:11, 0 users, load averages: 1.85, 2.39, 2.23

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.