Group Abstract Group Abstract

Message Boards Message Boards

Is the "reverse factoring" counter behavior computationally irreducible?

Posted 7 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 7 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
Posted 7 years ago

Yes, it is possible to find a relation between the Sieve of Eratosthenes and the algorithm introduced in this discussion.

Proceeding in similar ways Sieve of Eratosthenes allows finding prime numbers while the algorithm finds the exact exponent of each factor in a number, so generating the sequence of all the positive numbers by neatly varying factors... It counts.

The "reverse factoring counter" counts in a counterintuitive way; it is an unreasonable way for the purpose of "finding the next number", but it would be great for the purpose of "knowing the factors of the next number".

Also, given an arbitrary prime, the algorithm can generate the corresponding column of the main table independently from the data in other columns (although it can do that only running from the beginning). "Interrelation of columns" occurs just to check the "next prime needed" condition; and this is the part where the algorithm has nothing new to say with respect to the Sieve of Eratosthenes.

I thank for the observation. I suppose that the Sieve of Eratosthenes behavior has been proven computationally irreducible. Perhaps it is possible to give an answer to the question of this discussion in a similar way.

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

In this discussion I've given an ECMA-262 definition of the algorithm that describes the behavior of what I called (to fit in title) the "reverse factoring" counter.

Now I give the URL of an HTML5 page showing that behavior by an embedded JavaScript implementation of that algorithm... http://www.comprendonio.info/I/UnlimitedInside/I/ReverseFactoringCounterBehavior.HTM

Observing the graph it seems impossible to predict the behavior, for example, from row 1001 to row 1200, without computing all the steps from the beginning (row 1).

Of course it is possible to factorize 1001 to find all the data of the row 1001; nevertheless it does not seem possible to operate any version of the reverse factoring counter from there forward (again, without running it from the beginning).

Also a reasoning must be done about the known algorithms to factorize positive numbers... Do they covertly embed the rule I set in my algorithm? (Or vice versa, do my algorithm covertly embed factoring rules?)

For sure, determining every data in the table from row 1001 to row 1200 by factoring numbers cannot be considered a prove of computational reducibility of the behavior shown by the reverse factoring counter.

Anyway the question in the title of this discussion remain open because some "partial predictions" are suggested by the numerical version of the table (in the linked page). I'm going to think about them.

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