PRP-test issue

[pxp]

A PRP-test on a 74685-digit Leyland number submitted December 21 is still "in queue" two days later while a 76029-digit Leyland number submitted four hours later got PRP'd within the day.

[DukeBG]

There are 9,068 PRP tests queued right now. Someone is overzealous with that button. FactorDB shouldn't be forced to PRP numbers that big. Anyone is better advised to run such PRPs on their own hardware.

[pxp]

Originally Posted by DukeBG

There are 9,068 PRP tests queued right now. Someone is overzealous with that button. FactorDB shouldn't be forced to PRP numbers that big. Anyone is better advised to run such PRPs on their own hardware.

FactorDB has a built-in limit on the size of numbers it is willing to PRP so it isn't forced to do anything. As to the number of tests in the queue, I don't know how they come about or how big the numbers are but I have never had a PRP test on a number (and I have submitted one every three or four days on average for the last four years) take more than a few hours. And I run the PRP tests in Mathematica before I ever try them in FactorDB so I already know their status. The FactorDB result is simply a clickable reference to the number in an online compilation.

But you're missing the point. There is a number supposedly "in queue for a PRP-test" since 21 December 2019 but I have added four more numbers to that queue since then (two just yesterday) and all four have been PRP'd in a matter of hours. So the number "in queue" is apparently not really in queue since it has become obvious that it will never get to the front. It was this matter to which I wanted to bring attention in case anyone else had a similar experience.

[axn]

FactorDB PRP queue is LIFO. So the ones that are submitted recently gets processed before the older ones. Currently 9043 numbers are in queue. Noone knows where your number is within that queue. When the queue runs down to 0, yours would have been done as well.

Go to http://factordb.com/status.php and look at the pending column against the "Combined N-1/N+1-method" line (under Primality Proofs section) to keep track of the queue size.

Oh, and btw, when there are certificates to be processed, that gets priority, so the PRP queue will have to wait even further.

[retina]

Originally Posted by axn

FactorDB PRP queue is LIFO.

That's a stack.

Perhaps the confusion here is the incorrect term "queue".

[axn]

Originally Posted by retina

That's a stack.

Perhaps the confusion here is the incorrect term "queue".

You're correct. That is not the expected behavior of "queue", but it is what it is. Note that factor db itself doesn't use any terminology -- it is just a term that we used in the discussion.

[Dr Sardonicus]

I also tried finding the number on the list of numbers with unknown status. I eventually succeeded, and also found an obviously-related number. The list is sorted by number of digits only. I had to resort to trial-and-error to fill in the "Digits" field to bring the requisite number of digits into range. The filled-in fields didn't copy-paste; I had to fill them in in the quoted portion.

Why the number of digits that worked, worked, is a mystery to me.

Select range
Type U
Digits 74537
Per page [1..5000] 100
Skip first [0..50000] 49800

<snip>

1100000001419038845 3927^20780+20780^3927<74685> 74685
1100000001124344011 (2^248137+1)/2466453988659<74685> 74685
1100000001095527907 ((42^23008+1)^2-2)/189744822551<74685> 74685
1100000001285702986 7876323509...29<74685> 74685
1100000001197804384 3672515801...31<74685> 74685
1100000001233661196 (2^372156+1)/(2^124052+1)/241<74685> 74685
1100000001236671432 1683512024...11<74685> 74685
1100000001420823039 (3927^20780+20780^3927+1)/2<74685>
<snip>

[MDaniello]

That massive number of tests in stack made me wonder if someone was "clearing" some digit interval in the Unknown status list. Given that is taking a really long time to test those numbers, they should be far down the list. (Question: is PRP testing time exponential in number size? By size i mean digits)

By looking at the distribution graph i found this.
I then checked some numbers in the list on either side of the dips in the graph for PRP button availability: The numbers between 149012 and 149142 digits are in the stack, while numbers above 149159 digits are not. (Apparently, you can't PRP test numbers with 150 kilodigits and bigger)

Of course i didn't check each number, just randomly sampled them in those intervals. Because the bulk of the numbers are beetween 149041 and 149142 digits (around 100 bins, and for each bin we have numbers in a range from 30 to 70, the total number of numbers (sorry for the repetition) is expected to be beetween 3000 and 7000. So, either i missed something/overapproximated in my back-of-the-envelope calculation, or a significative part, but not all of the numbers in th stack, are >149 kilodigits.

[paulunderwood]

Originally Posted by MDaniello

(Question: is PRP testing time exponential in number size? By size i mean digits)

It is O(log(n)^2*log(log(n))) (if my memory serves me correctly). A rule of thumb is if the number is twice as long it takes 4 times as long to PRP test.

[DukeBG]

Originally Posted by axn

Note that factor db itself doesn't use any terminology -- it is just a term that we used in the discussion.

Are you sure?

But I agree that not only this should have been called a stack, or rather actually implemented as a queue, not as a stack, it also should have been auto-reordered to have smallest numbers served first, like it actually does for primality certificates processing. Oh well.

FactorDB has a built-in limit on the size of numbers it is willing to PRP so it isn't forced to do anything.

Sure, it has a size limitation, but just because it's capable of doing some PRP tests in reasonable time doesn't mean it should.

If you've only submitted these two numbers, that's no problem. Someone else who submitted 9K numbers (by which i mean "added to the queue for PRP processing"), a lot of which, I presume, take 10-20 minutes each, is a problem. There's always more than enough smallest "status=unknown" numbers for FDB to auto-work on, people asking for their numbres to be worked on first is an avenue I believe should be much more limited. Or uploading residues should be implemented in some way, though I don't think there's a reliable way to check them without doing a full test again which kinda defeats the purpose.

[axn]

Originally Posted by DukeBG

Are you sure?

Originally Posted by DukeBG

it also should have been auto-reordered to have smallest numbers served first, like it actually does for primality certificates processing. Oh well.

There is one use case where it makes sense to do the latest one first --when we have a PRP and we want to do another prp test on it with a different base interactively, we want it to be done immediately instead of going into a queue. Otherwise I agree.

Originally Posted by DukeBG

There's always more than enough smallest "status=unknown" numbers for FDB to auto-work on

FactorDB auto PRP test is limited to < 20,000 digits. Why? The numbers around this size takes 5-10 seconds only. IMO, it should've auto worked on everything under 100k digits (smallest ones moving to the top of the queue, natch). Currently, the only way to make FactorDB work on these smaller unknowns is to submit them.