Message Boards Message Boards

Is the "reverse factoring" counter behavior computationally irreducible?

Posted 6 years ago
POSTED BY: Alberto Orioli
5 Replies

Re: "I think there are many factorization contexts where iterating FactorInteger for consecutive numbers in a range is more time consuming than a single execution of a function (or "built-in symbol") based on the algorithm shown here."

For small numbers, in a range where sieving is effective, one might benefit from a pure sieve-based approach. Beyond several digits this will not be optimal. Beyond 20 or so digits it will not even be tractable.

POSTED BY: Daniel Lichtblau
Posted 6 years ago
POSTED BY: Alberto Orioli

What is called the "reverse factoring counter" appears to be a description, more or less, of the Sieve of Eratosthenes 1, 2.

POSTED BY: Daniel Lichtblau
Posted 6 years ago
POSTED BY: Alberto Orioli
Posted 5 years ago

I think it's time to report here an important development of the algorithm introduced in this discussion months ago.

The current version can do exactly what I've already written for example, determining every data in the table from row 1001 to row 1200 without computing all the steps from the beginning. (Also by means of a more complex prelude.)

So I give the URL of an HTML5 page embedding one JavaScript implementation of it... http://www.comprendonio.info/I/UnlimitedInside/I/ReverseFactoringCounterInARange.HTM

Of course it is possible to save and open a locally modified version of that page, for example with the purpose of showing results for a different range (by differently setting LowerLimit and UpperLimit).

It would be great to have, in Wolfram Language, a sort of FactorInteger suitable for a range of input positive numbers... I think there are many factorization contexts where iterating FactorInteger for consecutive numbers in a range is more time consuming than a single execution of a function (or "built-in symbol") based on the algorithm shown here. (I would be happy to support the developer for such a task!)

POSTED BY: Alberto Orioli
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract