Factoring database
 

Hello,

i think of programming a factor database with web interface to search and report factors, anybody knows if something similar already exists? Is there a need for something like this?

Syd

Certain projects have their own. The homogeneous cunningham project has a rather simple one. You can reserve a number, and then submit factors which you found. I think a lot of the actual tables in most projects are still manually updated (at least submitted data is checked by a human in some way.)

I haven't seen a "general system" created by someone, however.

I always like the idea of gathering data and automated processing.

Two things however: if you also want to store things like search statistics about cofactors, that might prove to be a hell of a job, taken into account that special numbers have special factors etc.

Secondly: if it were to be successful, I suppose such a generic database needs a lot of computing power to check things like primality of submitted factors.

[edit]
Do you have a draft of the design? I'd be happy to comment. I have some hobby-wise experience with creating a CMS and web interface driven apps.

[QUOTE=J.F.;153016]I always like the idea of gathering data and automated processing.

Two things however: if you also want to store things like search statistics about cofactors, that might prove to be a hell of a job, taken into account that special numbers have special factors etc.

Secondly: if it were to be successful, I suppose such a generic database needs a lot of computing power to check things like primality of submitted factors.

[edit]
Do you have a draft of the design? I'd be happy to comment. I have some hobby-wise experience with creating a CMS and web interface driven apps.[/QUOTE]I've a prototypical design for a PostgreSQL database to hold all factoring information in which I'm interested. The database is far from fully populated, not least because I find I keep having to modify the schema.

Paul

I've been slowly designing one for keeping up with my NFS factorizations as I learn more. Also, I've been working on something that will more intelligently split the workload between a few systems I have. Just doing the even/odd thing with factMsieve or factLat doesn't work well when one system is 64-bit dual core, the other is a dual P3. one is just 5x faster than the other and thus a lot of the lower ranges don't get sieved. I get these evenly spaced holes.

Last week I made a first draft schema for an SQL database for factorization information of interest to me. I was planning to use MS SQL because it's available to me and I use it at work. In the factorization part I'm still considering options for storing factors - large factors need a representation method and small factors could share it or could use a native integer representation.

I'm finally done with it, it was a hell of work! A lot more than i thought it would be.
The first difficult part was the scanner/parser, it has to modify the expressions used and notice if they are actually the same, take care of operator priority and so on. There is still one bug in it, x^y^z is taken as (x^y)^z, not x^(y^z) and maybe some i didnt notice.

Next comes the tricky part: Special numbers can have factors that are special numbers, too. If a factor is submitted, all numbers above also have this factor, numers below it also may have this factor. I simplified this a little bit by using 3 tables:
factor <factorid, shortform, Maybe longform, digits, type enum(prime, prp, composite, unknown_too_big)>
hasfactor <factorid, factorid>
cofactor <factorid, factorid>

hasfactor contains all factors of a factor which are prime or where no factors are known, if a factor has been factorized, it moves to cofactor.
If a factor is submitted, it looks up recursively and adds the factor to every number found, modifies its type, next it goes down recursively and checks which numbers divide it.

[URL]http://factorization.ath.cx/search.php[/URL]
If you give it a try, i'd be happy to read some comments :smile:

Ok, I'll post a quick one, what does it do?

I see a text box, and a button that says search.

Search for what?

[quote=joral;153430]Ok, I'll post a quick one, what does it do?

I see a text box, and a button that says search.

Search for what?[/quote]

It searches for factorizations. Enter "M509", "2^3001+1", "89745896326926391", "400!+1" or anything you like.

[QUOTE=Syd;153431]It searches for factorizations. Enter "M509", "2^3001+1", "89745896326926391", "400!+1" or anything you like.[/QUOTE]

I entered 2^41234123412341-1. It has factors (thanks, ewmayer), but the database answers "Number too big!" :smile:

It works fine, but maybe there should be a warning about limits of the search.

Luigi

[quote=ET_;153433]I entered 2^41234123412341-1. It has factors (thanks, ewmayer), but the database answers "Number too big!" :smile:

It works fine, but maybe there should be a warning about limits of the search.

Luigi[/quote]

Thats way too big, the limit is at about 100.000 digits. Added the warning :smile:

Syd

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? :smile:

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

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

[quote=ET_;153438]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? :smile:[/quote]

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 :smile:


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

Like this?

[QUOTE=Syd;153446]




Like this?[/QUOTE]

Impressive! :bow:

Luigi

Some interesting answers:
[code]
1
Status: Unknown

1-1
Status: Unknown

1-2+1
Error: Negative

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

have you added looking for algebraic factorizations

[quote=fivemack;153440]Thanks for writing this, it's a nice bit of work.

[/quote]
Thank you



[quote=fivemack;153440]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.[/quote]
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.

[quote=fivemack;153440]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) ?[/quote]
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

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.

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!

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.

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.

[quote=henryzz;153451]have you added looking for algebraic factorizations[/quote]

Not yet, maybe later.

[quote=fivemack;153467]You construct, using GMP and a product tree, twenty numbers
[/quote]

I tried it, but it takes ages to finish. I already have > 1M composite numbers with no factors known in the database, the server is way too slow.


[quote=10metreh;153568]
P.S. How far have you factored Mersenne numbers? There is still a C78 for M277.[/quote]

Everything up to C70 is factored now, I'm still trying to import the others

Syd

Well I've done M254 and someone's done M277 in the meantime.

All Mersennes up to M500 done.

How far have you ECM'd so far? What do you mean by low, medium and high limits? At a guess, 20, 25 and 30 digits, though I am bound to be wrong.

I see the workers are working harder now. They're in a race with me!

[quote=10metreh;153572]Well I've done M254 and someone's done M277 in the meantime.

All Mersennes up to M450 done.

How far have you ECM'd so far? What do you mean by low, medium and high limits? At a guess, 20, 25 and 30 digits, though I am bound to be wrong.[/quote]

low is ecm -one -c 5 -i 5000 -v 10000, medium ecm -one -c 20 -i 5000 -v 10000 and high is ecm -one -c 200 -i 5000 -v 10000.
Every composite is automatically assigned for low ecm.

[quote=10metreh;153572]
I see the workers are working harder now. They're in a race with me![/quote]

The workers found a factor table :smile:

[quote=Syd;153582]The workers found a factor table :smile:[/quote]

They didn't even know of factor tables or Alpertron's applet (which I was using)?

Mersennes done up to M550.

How much are you doing on near-Cunningham numbers (numbers of the form [tex]a^b + c[/tex], [tex]c[/tex] small)?

I'm taking a break now. The workers can do the rest.

[quote=10metreh;153585]They didn't even know of factor tables or Alpertron's applet (which I was using)?[/quote]

I imported some factor tables using the workers. First the mersenne.org's "factors.cmp", now I'm doing the cunningham tables. Which one should be next?

[QUOTE=Syd;153590]I imported some factor tables using the workers. First the mersenne.org's "factors.cmp", now I'm doing the cunningham tables. Which one should be next?[/QUOTE]

[URL="http://www.asahi-net.or.jp/~KC2H-MSM/mathland/matha1/"]http://www.asahi-net.or.jp/~KC2H-MSM/mathland/matha1/[/URL]

[url]http://primorial.unit82.com/tableplusone.html[/url]

[url]http://primorial.unit82.com/tableminusone.html[/url]

[url]http://www.mersenneforum.org/showthread.php?p=144571#post144571[/url]

Now it can display multiple numbers at once, here are some examples:

Display 2^1+1 to 2^100+1
2^x+1,1,100

Display Mersennes from 300 (to 300+100)
Mx,300

5^x-3^x+1,10000,10010

however, the number of results is limited to 100 at once.

Wow. That's fantastic. Basically, you have single-handedly replaced all current factorisation tables. All it needs now is a reservation engine :)

One tiny glitch: if I search for '1+x!,100,105' then click on '1+104!', the '+' doesn't get ecaped in the HTML, so it takes me to '1 104!'

[quote=fivemack;153617]Wow. That's fantastic. Basically, you have single-handedly replaced all current factorisation tables. All it needs now is a reservation engine :)

One tiny glitch: if I search for '1+x!,100,105' then click on '1+104!', the '+' doesn't get ecaped in the HTML, so it takes me to '1 104!'[/quote]

Thank you :smile:

Fixed that one. Now i'll try to fix the bugs R. Gerbicz reported ..

Just curious...how does the whole "assign number to workers" thing work? Is it some kind of system that automatically runs x amount of ECM curves on a given number (the specific amounts being as you described earlier in this thread)?

I noticed that when I tried taking an arbitrary C176 from the homogeneous Cunningham list and submitted it for ECM to low limits, it returned a message that says "Waiting for worker...". What exactly does this mean? Also, is it dynamic in some way? If I sit there and stare at the "Waiting for worker..." message will it eventually change to something else to show some sort of progress? :smile:

[quote=mdettweiler;153636]Just curious...how does the whole "assign number to workers" thing work? Is it some kind of system that automatically runs x amount of ECM curves on a given number (the specific amounts being as you described earlier in this thread)?

I noticed that when I tried taking an arbitrary C176 from the homogeneous Cunningham list and submitted it for ECM to low limits, it returned a message that says "Waiting for worker...". What exactly does this mean? Also, is it dynamic in some way? If I sit there and stare at the "Waiting for worker..." message will it eventually change to something else to show some sort of progress? :smile:[/quote]

It runs a few curves on the given number on one of the connected maschines. Once you click the button, it writes to a table what should be done and it shows up as "Waiting for worker". When a worker is idle, it picks up the work, updates the status to "Assigned to worker x", and if successfull, updates the factors. Unfortunately there is no automatic reload yet, but you may click search again to see it.

[quote=Syd;153639]It runs a few curves on the given number on one of the connected maschines. Once you click the button, it writes to a table what should be done and it shows up as "Waiting for worker". When a worker is idle, it picks up the work, updates the status to "Assigned to worker x", and if successfull, updates the factors. Unfortunately there is no automatic reload yet, but you may click search again to see it.[/quote]
Hmm...when I click "Search" it just gives me the normal report page, with no status whatsoever on the workers. (Or maybe it just finished since I first loaded the page? :smile:)

Edit: I just tried this again with the same C176, then immediately re-searched it after assigning it to a worker. It then reported back as "Assigned to Worker #2". :smile:

Edit2: And...presto! It's [URL="http://factorization.ath.cx/search.php?query=12%5E200%2B11%5E200"]found a P22 factor[/URL]! :grin:

[quote=mdettweiler;153644]Hmm...when I click "Search" it just gives me the normal report page, with no status whatsoever on the workers. (Or maybe it just finished since I first loaded the page? :smile:)
[/quote]
No, it so happens that I [I]pre-ran[/I] those 12+11.x searches just an hour ago, because I had a couple recent NFS factors in that family (x=169 and 182) (and because I was testing the f(x),101,200 capability). Cool!


It is probably worth mentioning that the table homog.cunnighams are ECMed very hard already - nothing will most likely be found by ECM what is not already known from Paul's tables. Check the progression of the ECM factor sizes in the [URL="http://www.leyland.vispa.com/numth/factorization/anbn/UPDATE.txt"]update[/URL] and [URL="http://www.leyland.vispa.com/numth/factorization/anbn/HISTORICAL.txt"]older[/URL] sections, and you will see that at least 35-40-digit factors may be now expected. Syd, you may want to put a flag field in the database of how much ECM is known to have been done (by your workers or external efforts) on specific composites and skip the ECM to low/medium/high limits, if requested by a button press (or even grey-out/inactivate those buttons on such flagged numbers). (So that the workers would not be run uselessly again and again.)

P.S. It would be nice if we could add algebraic factors at least manually. Example [B]12^190+11^190[/B]
Report factor(s): [COLOR=royalblue]...and we enter...[/COLOR] [B]12^38+11^38[/B]
(which is itself composite, but please evaluate it behind the scenes, look it up in the database and apply all found factors recursively, right? Just my 2 cents)

P.P.S. Added the p38 factor manually to the same [URL="http://factorization.ath.cx/search.php?query=12%5E200%2B11%5E200"]12+11.200[/URL]...

A couple more cheeky requests
 

Can we have fibonacci() and lucas() numbers? They have the same sort of divisor patterns as Cunningham numbers, and there are big tables of factors available for inhalation at [url]http://home.att.net/~blair.kelly/mathematics/fibonacci/fibonacci.txt[/url] and [url]http://home.att.net/~blair.kelly/mathematics/fibonacci/lucas.txt[/url].

Would it be possible to have a notation - ## or something - for 'product of the first N primes' rather than 'product of the primes less than N'; otherwise x#+1,100,130 gets rather repetitive.

Syd, you may want to parse some algebraic forms.
Well, [URL]http://factorization.ath.cx/search.php?query=273415711927335176935345351670676383%5E2[/URL]
Maybe, for starters, it would be nice to parse
[FONT=Courier New]a^n[/FONT]
[FONT=Courier New]a^n-b^n[/FONT]
[FONT=Courier New]a^odd+b^odd[/FONT]
and then progress to Aurife... ...ehh... Aurifeuillian! yes, I can. (I though I could. Chug, chug, chug...)

[QUOTE=Batalov;153685]and then progress to Aurife... ...ehh... Aurifeuillian! yes, I can. (I though I could. Chug, chug, chug...)[/QUOTE]
Well done! Your Aurifeuillian papers are in order.

I'm working on the numbers just above a googol. There are quite a few easy QS/SNFS numbers in the range from 10^100 to 10^100+100. I couldn't find a factor table for these, so I'm doing them.

[QUOTE=10metreh;153692]I'm working on the numbers just above a googol. There are quite a few easy QS/SNFS numbers in the range from 10^100 to 10^100+100. I couldn't find a factor table for these, so I'm doing them.[/QUOTE]

Amusingly, I worked on adding numbers in this range to the database a few days ago, building on my work in [url=http://www.research.att.com/~njas/sequences/A076848]A076848[/url].

Nice database. I did a search for 3^437-2^437 and then entered the remaining factors which I found. I did one at a time, but when I click on "Report" it just brings me back to the same page with no message about if the factor was successfully save or not. If I try to search again the new factors are not showing up.

So did this fail, or do you have some sort of process to verify the factors and they will appear at some later date?

[quote=CRGreathouse;153730]Amusingly, I worked on adding numbers in this range to the database a few days ago, building on my work in [URL="http://www.research.att.com/~njas/sequences/A076848"]A076848[/URL].[/quote]

And you missed out a C72 and a couple of C74s.

[QUOTE=10metreh;153744]And you missed out a C72 and a couple of C74s.[/QUOTE]

Oh yes, I certainly didn't finish. And the earlier work I did only found one factor per number, so my work from last week was mainly splitting some of the remaining numbers with msieve and/or some ECM program (mostly gmp-ecm).

[quote=CRGreathouse;153747]Oh yes, I certainly didn't finish. And the earlier work I did only found one factor per number, so my work from last week was mainly splitting some of the remaining numbers with msieve and/or some ECM program (mostly gmp-ecm).[/quote]

The combined time for a C72 and two C74s is only about 20 minutes even on my slow computer. Why didn't you do them?

As these are SNFS numbers, I would ECM to lower limits (25 digits rather than 30).

ATM I'm doing a C97 from my aliquot sequence, so I won't do the C8x's straight away.

[QUOTE=10metreh;153838]The combined time for a C72 and two C74s is only about 20 minutes even on my slow computer. Why didn't you do them?[/QUOTE]

Because my time was the scarce resource, not computing power.

Thank you for your comments!

Looks like there is a lot of work to do. First I'll rewrite the parser, the current one is not 100% clean code, hard to debug, this may take a few days.

Here we go :smile:

Things that should work now:
Fibonacci sequence
fib(x)
fibonacci(x)
or short Ix

Lucas numbers
lucas(x)
Lx

product of the first N primes
x##

The bugs R. Gerbicz mentioned
(and a few more)


I'd be happy if you give it a try

[QUOTE=Syd;154048]
I'd be happy if you give it a try[/QUOTE]

So I just tried submitting a factor and now it provides some feedback which is great. I'm getting the message:

[B]Waiting for worker ... (unknown)[/B]

The page refreshes itself fairly often but the message has stayed that way for maybe 15-20 minutes now. Does that mean it has been queued up and at some point one one of the worker machines becomes available it will be processed? Or did something go wrong and the (unknown) means it did not get scheduled anywhere so will never get processed?

[quote=Jeff Gilchrist;154060]So I just tried submitting a factor and now it provides some feedback which is great. I'm getting the message:

[B]Waiting for worker ... (unknown)[/B]

The page refreshes itself fairly often but the message has stayed that way for maybe 15-20 minutes now. Does that mean it has been queued up and at some point one one of the worker machines becomes available it will be processed? Or did something go wrong and the (unknown) means it did not get scheduled anywhere so will never get processed?[/quote]

Just forgot to start the workers again ..

[QUOTE=Syd;154062]Just forgot to start the workers again ..[/QUOTE]

Ok so now when I enter a factor, no message shows up, and the factor does not show up in the list of factors either.

I got a similar problem earlier. When I submitted a factor that finished the number, the submitted factors appeared in the form "Factor submitted: XXX" and in the factorization but the number was still "Composite, factors known" rather than "Composite, fully factored". If I searched for that number again the problem would be sorted.

[quote=10metreh;154160]I got a similar problem earlier. When I submitted a factor that finished the number, the submitted factors appeared in the form "Factor submitted: XXX" and in the factorization but the number was still "Composite, factors known" rather than "Composite, fully factored". If I searched for that number again the problem would be sorted.[/quote]
i wouldnt be surprised if what you are seeing is something to do with waiting for the final cofactor to have its primality checked

[QUOTE=Syd;153590]I imported some factor tables using the workers. First the mersenne.org's "factors.cmp", now I'm doing the cunningham tables. Which one should be next?[/QUOTE]

Homogenous Cunningham Tables:
[url]http://www.leyland.vispa.com/numth/factorization/anbn/main.htm[/url]

Does the database check if reported factors are composite?

[quote=Andi47;154177]Does the database check if reported factors are composite?[/quote]

It does a probable primality test, yes. I haven't found any composite factors for the database yet, but all the other numbers are tested, so I presume reported factors will as well.

The workers seem to have problems with highly composite (and very smooth) (co-)factors that contain lots of p4 factors - it seems that "ecm to low limits" finds the whole lot of tiny factors and thus can't split the number. Perhaps the trial factoring limit should be raised to 10000.

Msieve trial factors to 100k...

[quote=Andi47;154253]The workers seem to have problems with highly composite (and very smooth) (co-)factors that contain lots of p4 factors - it seems that "ecm to low limits" finds the whole lot of tiny factors and thus can't split the number. Perhaps the trial factoring limit should be raised to 10000.[/quote]

I'd say 1e6. The ECM system is odd as well. I'd just do TF to 1e6, then do ECM to 15, 20, 25 etc. digits followed by QS/NFS.

BTW, is there a factor table for numbers near a googol?

Bug?
 

Sometimes when I report a (valid) factor, I get an error message:

[code]Error: Expression (^ is infix)[/code]

In most cases the factor is accepted anyway, but it's annoying when I get the error message every time when I import a factor of M10080 (and for some other Mersennes).

[QUOTE=henryzz;153451]have you added looking for algebraic factorizations[/QUOTE]

[QUOTE=Syd;153571]Not yet, maybe later.[/quote]

I extend this question to Aurifeuillians. And the database does not recognize them:

[code]2^1925-2^963+1

Short forms
No short forms found
[/code]

Syd, I suggest looking at the code for Alpertron's applet and finding the part which deals with algebraics and Aurifeuillians. It might help.

Line 3 in post #27 (near-Cunninghams) has gone unanswered.

Thank you very much for your comments, they show up a lot more bugs than i expected.

First - the one i accidently missed:

[quote]How much are you doing on near-Cunningham numbers (numbers of the form ?[/quote]The template for these numbers exists, thats all so far. These numbers are the next ones to import once the other bugs are fixed.

[quote]
I got a similar problem earlier. When I submitted a factor that finished the number, the submitted factors appeared in the form "Factor submitted: XXX" and in the factorization but the number was still "Composite, factors known" rather than "Composite, fully factored". If I searched for that number again the problem would be sorted.[/quote]Currently the number status is not updated during the page request itself, but right after it. This is indeed confusing, will change it soon.

[quote] Does the database check if reported factors are composite? [/quote]Yes, they are tested if <= 1000 digits.

[quote]Error: Expression (^ is infix)[/quote]Thats a wired one, couldn´t track it down yet.

[quote]I extend this question to Aurifeuillians. And the database does not recognize them:[/quote]It wont recognize most of them yet. Thats another todo point.


The factoring limits: Will add this to the workers


Thank you again

Syd

Is there a factor table for the near-Cunninghams? I couldn't find one.

When "assigned to worker X (sieve)" appears, does this mean SIQS and what programs are you using? I saw it appear on a C97 that was far easier by SNFS.

[quote=10metreh;155302]
When "assigned to worker X (sieve)" appears, does this mean SIQS and what programs are you using? I saw it appear on a C97 that was far easier by SNFS.[/quote]

I use msieve (MPQS) for sieving. The "old" code was quite buggy, it sometimes even assigned C>100 to msieve, without doing ECM first. The limit should be at about 80 digits, maybe its already working now.

Syd

Someone (CRGreathouse, was it you?) has finished the range 10^100+x,1,100, so I will soon start the 10^100-x,1,100 range. Nice new database layout!

Syd, what processors do your workers have? For some processors, yafu is faster at sieving.

[quote=10metreh;155569]Nice new database layout!

Syd, what processors do your workers have? For some processors, yafu is faster at sieving.[/quote]

Thank you :smile: But its still far away from being done. The "workers" are all running on my Q6700 + one on the server

[quote=Syd;155585]Thank you :smile: But its still far away from being done. The "workers" are all running on my Q6700 + one on the server[/quote]

I think yafu is faster for that processor.

is there a page that tells us what the workers are doing

Next update, now it does *some* algebraic factorizations,


[quote]How much are you doing on near-Cunningham numbers (numbers of the form [IMG]http://mersenneforum.org/cgi-bin/mimetex.cgi?a%5Eb%20+%20c[/IMG], [IMG]http://mersenneforum.org/cgi-bin/mimetex.cgi?c[/IMG] small)?[/quote]Added them, a<1000, b<130, c<8, maybe more later.

[quote]P.S. It would be nice if we could add algebraic factors at least manually. Example [B]12^190+11^190[/B]
Report factor(s): [COLOR=royalblue]...and we enter...[/COLOR] [B]12^38+11^38[/B]
(which is itself composite, but please evaluate it behind the scenes, look it up in the database and apply all found factors recursively, right? Just my 2 cents)[/quote]Now you can add them manually. However, i'm working on adding them automatically, which is much harder than i expected.
The factors are applied automatically

[quote]there are big tables of factors available for inhalation at [URL="http://home.att.net/%7Eblair.kelly/mathematics/fibonacci/fibonacci.txt"]http://home.att.net/~blair.kelly/mat.../fibonacci.txt[/URL] and [URL="http://home.att.net/%7Eblair.kelly/mathematics/fibonacci/lucas.txt"]http://home.att.net/~blair.kelly/mat...acci/lucas.txt[/URL].[/quote]Inhaled :smile:

[quote]I did one at a time, but when I click on "Report" it just brings me back to the same page with no message about if the factor was successfully save or not. If I try to search again the new factors are not showing up.

So did this fail, or do you have some sort of process to verify the factors and they will appear at some later date?[/quote]The import failed, this was due to a bug in GCD/preprocessing of factors, under certain conditions it dropped some factors. I hope i fixed that one ..

[quote] is there a page that tells us what the workers are doing
[/quote]No, not yet

Hope you all started well into the new year :smile:

Syd

I noticed a small glitch following the Fermat factors link
[url]http://factorization.ath.cx/search.php?query=2%5E%282%5Ex%29%2B1%2C1[/url]

Also, did you give a look at Kamada's webpages?

[url]http://homepage2.nifty.com/m_kamada/math/factorizations.htm[/url] ?

Luigi

Great work.

Tip/request: [URL="http://www.garlic.com/%7Ewedgingt/mersenne.html"]Will Edgington[/URL] has lots of Mersenne factors. I'd really like to see them imported. If it is too much work for you, perhaps I might find some time soon to spam some factors to your server ;).

Q: is there a way for us users to promote PrP factors to Prime? For instance, M31 and M61 are currently marked PrP.

PS: I see that Will hasn't updated his data since 5 oct... hmmm.

i would suggest using "pfgw -tc" for primality tests

There is a bug in your multipage code which causes this to happen:

I searched for "2^293-x,1701,2000" for my 2-brilliant search.

A page came up with the results from 1701 to 1801. However, when I click on "Next page", I get the results from 3701 to 3801, not the expected results from 1802 to 1902 or something similar.

[quote=ET_;157059]I noticed a small glitch following the Fermat factors link
[URL]http://factorization.ath.cx/search.php?query=2%5E%282%5Ex%29%2B1%2C1[/URL]
[/quote]

Seems like the debug mode was still active

[quote]
Also, did you give a look at Kamada's webpages?

[URL]http://homepage2.nifty.com/m_kamada/math/factorizations.htm[/URL] ?
[/quote]

Yep, this is the place where everything started for me :smile: I'm currently importing these factors.

[QUOTE]
Tip/request: [URL="http://www.garlic.com/%7Ewedgingt/mersenne.html"]Will Edgington[/URL] has lots of Mersenne factors. I'd really like to see them imported. If it is too much work for you, perhaps I might find some time soon to spam some factors to your server ;).[/QUOTE]

Inhaled them. However, if someone wants to spam some factors to the server, i have no problem with that.

[QUOTE]
Q: is there a way for us users to promote PrP factors to Prime? For instance, M31 and M61 are currently marked PrP. [/QUOTE]

Now you can. Well there is still a small bug in it, the status will not show up instantly, like when you submit the last factor.

would it be possible to have the usage table above the list of factor tables
edit: i think that has now been done

[quote=henryzz;158541]would it be possible to have the usage table above the list of factor tables[/quote]

Sure it is :smile:

I don't think it is wise to have those 'is definitely prime' buttons out in the open. I'm afraid this is somehow gonna lead to pollution (unintentional, spiders, intentional) of your fine database, which would be a shame imo.

Perhaps you can mark primes from 'trusted' sources upon import? An alternative would be to add some sort of user registration and input history, so errors can be tracked. Other ideas?

About the Mersenne factorizations: did you by any chance forget to input lowM.txt? I had a look at M5000 - it contained all factors from M2500 (from factoredM.txt), but missed the two smallest ones from lowM.txt. After having inputted them, the digit count of the remaining cofactor is still off btw.

User registration together with input history, login and so on is a quite complex task, but eventually I can even use it together with some reservation/ECM efforts tool.

But maybe .. how complex is it to prove a number definitely prime, say up to 1000 digits with ECPP? Are any tools available?

Indeed, i forgot to import the factors from lowM.txt. In case of M5000, can you tell me which factors are missing?

For primality proving, the tool of choice is [url="http://www.ellipsa.net/index.html"]Primo[/url], though I don't know how amenable it is to batch input.

[quote=jasonp;158711]For primality proving, the tool of choice is [URL="http://www.ellipsa.net/index.html"]Primo[/URL], though I don't know how amenable it is to batch input.[/quote]
Yesterday I went through a lot of the PRP's in the database and manually proved them prime with PARI/GP's isprime() function--it was able to do many of them instantaneously, and only the ones >100 digits or so took even just a few seconds apiece to do.

At any rate, from what I can tell, PARI would be much more scriptable, and it probably wouldn't be too hard to set up into the existing worker system so that primality-proving jobs could be queued up and fed to all the workers like is already done with ECM and TF work.

i just want to reach the link in post #7 but at work it's blocked by our webfilter:

[code]
URL: http://factorization.ath.cx/search.php

URL-Kategorien: Malware
[/code]

any chance to change this?

try here: [url]http://filterdb.iss.net/urlcheck/[/url]

[quote=Syd;158625]In case of M5000, can you tell me which factors are missing?[/quote]

Since M2500 is fully factored, they must originate from 2^2500+1, which currently shows a 665 digit composite (after I hit ECM-medium to remove a few digits).
Edgingtons data suggests that the composite can be reduced to 580 digits. I don't know where to look for the remaining 85 digits of prime(s) - the Cunningham tables only go to 2400.

[edit]
I had a look at M2398. It showed a 530-digit composite (id=21276431). However, several implied factors from M767 were missing. After having 'submitted' them, the digit count agrees with Edgington.
I suggest doing something like
[code]
forall factors f of Mx
submit f to M(kx) with k=2,3,...[/code]

[quote=mdettweiler;158717]At any rate, from what I can tell, PARI would be much more scriptable, and it probably wouldn't be too hard to set up into the existing worker system so that primality-proving jobs could be queued up and fed to all the workers like is already done with ECM and TF work.[/quote]

Thats an awesome library, I'm done with just a few lines of extra code like you said. Though it would be nice to have those primo primality certificates for download.

[QUOTE] any chance to change this?

try here: [URL]http://filterdb.iss.net/urlcheck/[/URL][/QUOTE]

Thats weired

[code]3 x 5^5 x 11 x 17 x 31 x 41 x 101 x 251 x 401 x 601 x 1801 x 4001 x 4051 x 7001
x 8101 x 28001 x 61681 x 96001 x 160001 x 268501 x 340801 x 1074001 x 2020001 x 2787601
x 3775501 x 22624001 x 37177501 x 107580001 x 229668251 x 831172501 x 2259150001
x 3173389601 x 14321535001 x 269089806001 x 1481124532001 x 619324035675566251
x 1277297679372570001 x 4710883168879506001 x 47970133603445383501
x 94291866932171243501 x 5519485418336288303251 x 232983411264923603130001
x 573759820507018639639785001 x 983262166270913562877993411320001
x 633746672116596658276533517443227501
x 18152902839291497575027462639977160832701118299213751
x 246053469753590746981511859818675718355368494592178751
x 23072017280360209143853190404178284560740949254655131346786858037350918591251 x
8877945148742945001146041439025147034098690503591013177336356694416517527310181938001 x
167151693059203651258538223678521800139589649629368247829683865124002155584217612884019447563002501 x
45712845832064476909251288412537780542141386629649967711230003222863831555000707453689906421700439212068044560931077031315106846707799052501 x
2952514364581316337639834904034501808253955768505847014917395820453653708312223506491002496302532891440120688361870627195018283686594739576042156463430228261599130139157586670190936850324484407773053651741800071409643774842685094764505897386290434816137207257527045648890038980443489148266586061742881796117450662972816739833595245680317687294799762715910575282701475446274531684090484014335382380426254949454811556963459149908837253490252431670151904810696439528202733056843409785493492110147847556186485233154284233119314768888487458979069953852588599421726292742704836614070001(the C580)[/code]

are the known prime factors of M5000.

Error in my previous post: I believe M2398 should be M2301. Doesn't matter much.

@10metreh: aha, may I ask where did you come across that 85 digit prime?

2,500+ | 2,2500+
2,100+ | 2,500+
2,500+/2,100+ factors easily -> p85 comes from there.

p140 and p99 come from 1250L,M of course
[code]1250L (10M,50L,250M) 37177501.831172501.633746672116596658276533517443227501.P99
M (2,10L,50M,250L) 5*.14321535001.P140
[/code]
I bet it was done years ago.

This is wonderful! Another two tables to inhale are

[URL="http://xyyxf.at.tut.by/results.txt"]http://xyyxf.at.tut.by/results.txt[/URL]
[URL="http://xyyxf.at.tut.by/results2.txt"]http://xyyxf.at.tut.by/results2.txt[/URL]

I tried pasting a product of factors into the advanced reporting box, but that didn't seem to work.

[quote=10metreh;158741]are the known prime factors of M5000.[/quote]

Thank you and 10metreh and Batalov, again learned something new :smile:

[quote]I tried pasting a product of factors into the advanced reporting box, but that didn't seem to work. [/quote]The code behind the advanced factoring box is quite simple, it looks for something like "N:", "N=", "Input number is", "factoring", takes the integer behind this one as reference and tries to submit all other integers in text as factors. Most of them are actually no factors and get sorted out during first pass "does not divide".
Yet the box does not accept any short forms, this is something to work on.

edit:
forall factors f of Mx
submit f to M(kx) with k=2,3,...
implemented this code and it actually adds some of the missing links, but will take some days to finish

[quote=frmky;158760][URL]http://xyyxf.at.tut.by/results.txt[/URL]
[URL]http://xyyxf.at.tut.by/results2.txt[/URL]
[/quote]

Hope I inhaled your files correctly.

Now the advanced report box accepts these files directly, the lines must have the form:
(Expression) = (Expression) * (Expression) * ...

Please dont submit more than ~5.000 factors at once, php may run out of memory, and give the page some time to load, dont just click again.

Have fun with it :smile:

[quote=Syd;158768]Hope I inhaled your files correctly.[/quote]

I think you inhaled them ok, -- even the newest results are there...
[URL="http://factorization.ath.cx/search.php?query=124%5E65%2B65%5E124"]http://factorization.ath.cx/search.php?query=124%5E65%2B65%5E124[/URL]
:w00t:


P.S. There's a x^y-y^x database somewhere - ask Torbjorn Alm:
[URL]http://tech.groups.yahoo.com/group/xyyxf/message/1408[/URL]

[QUOTE=kar_bon;158720]i just want to reach the link in post #7 but at work it's blocked by our webfilter:

[code]
URL: http://factorization.ath.cx/search.php

URL-Kategorien: Malware
[/code]

any chance to change this?

try here: [url]http://filterdb.iss.net/urlcheck/[/url][/QUOTE]

it works fine now!

this Database is a great work!

perhaps i can do such thing for my RieselDatabase at [url]www.rieselprime.de[/url].

what about future plans?

- links, where those factors came from
- some stats: how many factors at all, for special digit-length, special patterns (like 19999...)

Thank you kar_bon!

Well, future plans. A reservation system would be nice, next to storing ECM/TF/P+-1 efforts.
Then, a "real" domain, but I still dont know which one.
Statistics are also a good idea :smile:

[QUOTE=Syd;158761]
forall factors f of Mx
submit f to M(kx) with k=2,3,...
implemented this code and it actually adds some of the missing links, but will take some days to finish[/QUOTE]

This is a brute force response to the abundancy of algebraic factors. Keepers of specialized tables usually list only the primitive factors and require users to understand the algebraic structure to find the full factorization.

Your logic will also locate non-primitive factors for any a^n-1 or a^n-b^n. Restricting k to odd values, it also works for (a^n+1) and (a^n+b^n). Fibonacci numbers and Lucas numbers also have algebraic structure that can be exploited.

[quote=J.F.;158748]Error in my previous post: I believe M2398 should be M2301. Doesn't matter much.

@10metreh: aha, may I ask where did you come across that 85 digit prime?[/quote]

Alpertron's applet automatically searches the Cunningham tables. I thought they went further than 2400.

Please scroll down the page that contains the applet and you will see the sources of the factors (these are tables maintained by Will Edgington and Richard Brent).