Records for complete factorisation

[Jens K Andersen]

I have just created a page with another type of records for complete factorizations:
Largest Consecutive Factorizations
"This page lists the largest known case of k consecutive numbers for which the complete prime factorization is known. Only records with at least 500 digits are listed."
There are no restrictions on constructed numbers or factor sizes - but k=1 is not included!

[ewmayer]

Originally Posted by Brian-E

It's nice to see that (according to Wikipedia) the top complete factorisation feat for non-constructed composites is a Mersenne number (2^1039-1). I suppose the difficulty of this factorisation is measured by the prime factor of 80 decimal digits which was found.

It might be nice to see, but it's also wrong. There are many composite Mersennes larger than this which have been completely factored.

Originally Posted by Jens K Andersen

I have just created a page with another type of records for complete factorizations

Your page confuses me - I see a bunch of large primes. Primes aren't "factorizations" any more than 1 is (nontrivially) "prime."

[Jens K Andersen]

Originally Posted by ewmayer

Your page confuses me - I see a bunch of large primes. Primes aren't "factorizations" any more than 1 is (nontrivially) "prime."

I have added this to the page: "The prime factorization of a prime is the prime itself, so a known prime has known prime factorization."
This is the definition I'm used to and I thought it was standard. Are you saying that a prime has no prime factorization?

[ewmayer]

Originally Posted by Jens K Andersen

Are you saying that a prime has no prime factorization?

In the sense of which we normally speak of factoring records and complete factorizations, no it does not -- a prime is a trivial complete factorization, in that it has just one proper factor.

The fact that the computational complexities of primality proving [proved to be in P] and factoring [believed NP] are radically different also makes it inappropriate to treat the 2 tasks as somehow being interchangeable.

[Jens K Andersen]

I did say "another type of records for complete factorizations". For the purpose of my page, consecutive numbers which all have completely known prime factorization, I don't think it would make sense to disallow primes. And some of the factorizations are n = 2*p which is about as trivial as n = n. But it's hard to find several large consecutive numbers with simple factorizations, for example the record for k=7 where no second largest factor is above 12 digits:
n = 21247003564*2411#-1 = c1037

n+0 = 12906420959*p1027
n+1 = 2^2*103*51570397*2411#, where 2411# = 2*3*5*7*...*2411
n+2 = 2524541*p1031
n+3 = 2*5002841*6245491249*p1020
n+4 = 3*485475518243*p1025
n+5 = 2^2*(5311750891*2411#+1)
n+6 = 5*3691*23063^2*2961991*19076087*3778442561*p1001

(n+5)/4 = 5311750891*2411#+1 is one of millions of probable primes found by Markus Frind and Paul Underwood during an AP8 search. They kindly gave me access to them so I could go for 7 consecutive titanic factorizations with limited computing power.

[R.D. Silverman]

Originally Posted by Jens K Andersen

I did say "another type of records for complete factorizations". For the purpose of my page, consecutive numbers which all have completely known prime factorization, I don't think it would make sense to disallow primes. And some of the factorizations are n = 2*p which is about as trivial as n = n. But it's hard to find several large consecutive numbers with simple factorizations, .

Of course it is hard. If it were easy, it wouldn't be worth doing.

I also do not believe that primes should be included.

[wblipp]

It seems obvious to me that primes fit the definition of the page, which is "largest known case of k consecutive numbers for which the complete prime factorization is known." I agree that limiting it to composites would make it harder, but also makes the definition of the page awkward.

You could try "largest known case of k consecutive composite numbers for which the complete prime factorization is known," but then a stretch of 7 numbers with a prime in the middle would qualify as a stretch of 6 consecutive composite numbers.

So you would need "largest known case of k consecutive numbers which are all composite and for which the complete prime factorizations are all known." Uhg.

I say stick with the simple, clear definition. If somebody else want to make a site restricted to non-primes, offer to provide a link.

[Jens K Andersen]

Originally Posted by wblipp

I say stick with the simple, clear definition. If somebody else want to make a site restricted to non-primes, offer to provide a link.

Hereby offered. I allow trivial factorizations and don't see a good computational reason to disallow n = n when n = 2*p and n = 2^p are allowed and occur. All lists I have seen with prime factorizations of consecutive numbers include primes, for example http://mathworld.wolfram.com/PrimeFactorization.html.
People who dislike primes being their own prime factorization can think of the records as the largest known n for which is completely factored.
I have announced the record with 7 numbers (not including primes!) in more detail at [primeform] Re: Update on search for consecutive factored titanics. The record page is actually a response to a 5 year old question by Jack Brennen (who allowed primes): Consecutive numbers all factored.

[xilman]

Observation: finding Brilliant numbers generally requires rather a lot of factorization of consecutive numbers.


Paul

[fivemack]

Observation: finding Brilliant numbers generally requires rather a lot of factorization of consecutive numbers.

But generally not complete factorisation, since you don't look any more at numbers whose small prime factors you've sieved out.

I'm not sure how to estimate the number of numbers between 10^500 and 2*10^500 whose second-largest prime factor is less than 10^10; I can write down an enormous inclusion-exclusion-principle sum sum_{N not coprime to (10^10)!} (-1)^{number of divisors of N} pi(2*10^500/N)-pi(10^500/N) , and I can observe that the number of numbers 2^a*p is going to be a nice collapsing sequence

pi(N)-pi(N/2) [2*p]
+pi(N/2)-pi(N/4) [4*p]
+pi(N/4)-pi(N/8) [8*p] ... = pi(N)

but I'm not sure how to turn anything into an integral that can actually be used to estimate a probability. So I'm estimating it by running ecm on [10^500, 10^500+10^4]

[R.D. Silverman]

Originally Posted by fivemack

I'm not sure how to estimate the number of numbers between 10^500 and 2*10^500 whose second-largest prime factor is less than 10^10;

Look up Dickman's function. See Knuth Vol. 2