Factoring database

[ET_]

Nice work indeed!

10000! prints the actual known factors, ending with a 5532-digits number whose status is unknown. Is it correct? No one factored it?

Not a bug, just a question.

A (typographical) bug is presented when I click on the 35660-digits long expansion of 10000!
I guess it's a bug related to the browser I use (Firefox 2.0): the related link is overwritten, I guess due to bad visualization properties of Firefox itself.

Hint: would it be possible/feasible/worth trying to use a fixed length and add a [newline ] after it?

Luigi

[fivemack]

Thanks for writing this, it's a nice bit of work.

I see you haven't inhaled the most recent version of the Cunningham tables (I'm cheeky, I search for the factorisations I did most recently ...), but that gives the opportunity to use the submit-factor interface.

I see you handle submissions of composite factors correctly (actually, it's slightly strange; I submitted a product of several largish factors of 2^2310-1, it recorded one of them, I submitted the same product again and it recorded a different one); I would appreciate some sort of error message if I put in a factor which doesn't divide the claimed number, rather than just getting the original page back.

Do you have enough compute power on that server to do ~20 large GCDs per number submitted, so that you can submit a factor and it gets applied to every cofactor that it divides (IE you just say '903888164009442693590288077' rather than having to tell it that that divides 2^1606+1) ?

[Syd]

Originally Posted by ET_

Nice work indeed!

10000! prints the actual known factors, ending with a 5532-digits number whose status is unknown. Is it correct? No one factored it?

Yes thats correct. 10000! was not in the database before, so its added during the search and quick-factored to 2000, like every other number. Obviously searching plain factorials makes no sense anyway

Originally Posted by ET_

would it be possible/feasible/worth trying to use a fixed length and add a [newline ] after it?

Like this?

[ET_]

Originally Posted by Syd

Like this?

Impressive!

Luigi

[R. Gerbicz]

Some interesting answers:

1
Status: Unknown

1-1
Status: Unknown

1-2+1
Error: Negative 

5*7/(2+3)
Error: Not divisable

[henryzz]

have you added looking for algebraic factorizations

[Syd]

Originally Posted by fivemack

Thanks for writing this, it's a nice bit of work.

Thank you

Originally Posted by fivemack

I see you haven't inhaled the most recent version of the Cunningham tables (I'm cheeky, I search for the factorisations I did most recently ...), but that gives the opportunity to use the submit-factor interface.

I see you handle submissions of composite factors correctly (actually, it's slightly strange; I submitted a product of several largish factors of 2^2310-1, it recorded one of them, I submitted the same product again and it recorded a different one); I would appreciate some sort of error message if I put in a factor which doesn't divide the claimed number, rather than just getting the original page back.

Actually it should add all factors that can be recovered from the numbers reported. Maybe the factor reported was quite small (<72 digits)? In that case the server runs msieve in background and adds the factors automatically.

Originally Posted by fivemack

Do you have enough compute power on that server to do ~20 large GCDs per number submitted, so that you can submit a factor and it gets applied to every cofactor that it divides (IE you just say '903888164009442693590288077' rather than having to tell it that that divides 2^1606+1) ?

How is that supposed to work? I definitely cant test the submitted factor against every number in db.
The Server is a duron 900/512MB

Syd

[fivemack]

You construct, using GMP and a product tree, twenty numbers

N1 = product {0th bit of composite-ID is 1} C
N2 = product {1st bit of composite-ID is 1} C
N3 = product {2nd bit of composite-ID is 1} C
N4 = product {3rd bit of composite-ID is 1} C
...

then, if you have a prime input, you can compute the GCDs (N1,p) through (N20,p), and that gives you the identity of the composite number that it divides. At least, provided that it divides only one composite number.

(you can check which composite numbers share factors by a similar kind of process: suppose you expect the density to be pretty small:

* label each number with a random integer in {1..100}
* compute the hundred products of numbers with each label
* compute the GCD of each pair of products
* if it's 1, you know no two numbers in the sets with the given label share a factor
* if it's prime, see which numbers with the given label it divided
* if it's composite, check whether it equals one of the numbers in the sets, and if not then perform the whole random-labelling process on the subsets with the two labels that appeared last time

* repeat with different labelling until the answers consistently come out as all 1
)

I suppose this may still be too slow, it's 30 seconds or so on the K8/2200 I use for testing. Quite fun to implement, though. I did it with the ~10000 cofactors of partition numbers to check that there weren't any unexpected shared primes.

[fivemack]

Wow, that's much niftier than I expected.

I put in 10^100+6, it said 2*5000000..0003, I put in 5*10^99+3 and it listed it as fully factored, I went back to 10^100+6 and it's now recorded as fully factored!

[Batalov]

It is nice.
I added to our 2^925+1 project's state. The p33 was missing. The composite that we are splitting is a c217.
...and it immediately showed up.

[10metreh]

I notice 10^100+13 has a composite C94 factor. I did that one a few days ago by chance. Sadly I deleted my logfile and will do the whole thing again.

Edit: Just remembered I do have it. Problem solved! I have submitted the factor.

P.S. How far have you factored Mersenne numbers? There is still a C78 for M277.