# Is the "reverse factoring" counter behavior computationally irreducible?

Posted 1 year ago
1541 Views
|
5 Replies
|
0 Total Likes
|
 Dear reader, this is my first post in this forum, as a consequence of a quick interaction with the Twitter account @WolframResearch.The main purpose is to verify the computational irreducibility of the behavior described by the algorithm I'm going to introduce here. So I hope in a response from some "A New Kind of Science" expert.But the algorithm, neatly varying factors, generates the increasing sequence of positive numbers, in the context of my study about an infinite-dimensional discrete space; so discussion of other aspects you possibly find interesting will also be welcome. var F F = function ( Limit ) { var Coordinates var Expand var Index var Numbers var Quantity var Value Numbers = new Array ( ) Numbers [ 0 ] = 1 Expand = function ( Coordinate ) { var Index var Quantity var Value Quantity = Coordinate . Exponents . length Value = Coordinate . Base - 1 while ( Value -- ) for ( Index = 0 ; Index < Quantity ; ++ Index ) Coordinate . Exponents [ Coordinate . Exponents . length ] = Coordinate . Exponents [ Index ] ++ Coordinate . Exponents [ Coordinate . Exponents . length - 1 ] } Coordinates = new Array ( ) Coordinates [ 0 ] = new Object ( ) Coordinates [ 0 ] . Base = 2 Coordinates [ 0 ] . Exponents = new Array ( ) Coordinates [ 0 ] . Exponents [ 0 ] = 0 Coordinates [ 0 ] . Exponents [ 1 ] = 1 for ( Quantity = 1 ; Quantity < Limit ; ++ Quantity ) { Value = 0 for ( Index = 0 ; Index < Coordinates . length ; ++ Index ) { if ( Coordinates [ Index ] . Exponents . length <= Quantity ) Expand ( Coordinates [ Index ] ) Value += Coordinates [ Index ] . Exponents [ Quantity ] } if ( ! Value ) { Coordinates [ Index ] = new Object ( ) Coordinates [ Index ] . Base = Quantity + 1 Coordinates [ Index ] . Exponents = new Array ( ) for ( Value = 0 ; Value < Quantity ; ++ Value ) Coordinates [ Index ] . Exponents [ Value ] = 0 Coordinates [ Index ] . Exponents [ Value ] = 1 } Numbers [ Quantity ] = 1 for ( Index = 0 ; Index < Coordinates . length ; ++ Index ) for ( Value = 0 ; Value < Coordinates [ Index ] . Exponents [ Quantity ] ; ++ Value ) Numbers [ Quantity ] *= Coordinates [ Index ] . Base } return Numbers } That is an ECMA-262 definition of the algorithm, that generates, up to a given limit, the sequence of all the positive numbers by neatly selecting the respective prime factors.This means every JavaScript programmer can try it copying the code in an HTML document, as part of a suitable JavaScript tag.To understand it imagine a table showing in each row a positive number and the exponents of the powers of its prime factors... positive number | power of 2 | power of 3 | power of 5 | power of 7 | power of 11 ----------------+------------+------------+------------+------------+------------ 1 | 0 | 0 | 0 | 0 | 0 ----------------+------------+------------+------------+------------+------------ 2 | 1 | 0 | 0 | 0 | 0 ----------------+------------+------------+------------+------------+------------ 3 | 0 | 1 | 0 | 0 | 0 ----------------+------------+------------+------------+------------+------------ 4 | 2 | 0 | 0 | 0 | 0 ----------------+------------+------------+------------+------------+------------ 5 | 0 | 0 | 1 | 0 | 0 ----------------+------------+------------+------------+------------+------------ 6 | 1 | 1 | 0 | 0 | 0 ----------------+------------+------------+------------+------------+------------ 7 | 0 | 0 | 0 | 1 | 0 ----------------+------------+------------+------------+------------+------------ 8 | 3 | 0 | 0 | 0 | 0 ----------------+------------+------------+------------+------------+------------ 9 | 0 | 2 | 0 | 0 | 0 ----------------+------------+------------+------------+------------+------------ 10 | 1 | 0 | 1 | 0 | 0 ----------------+------------+------------+------------+------------+------------ 11 | 0 | 0 | 0 | 0 | 1 It is well known that 6, for example, is the result of 2^13^15^0*7^0.7 == 2^03^05^0*7^18 == 2^33^05^0*7^09 == 2^03^25^0*7^0The algorithm doesn't create the table by factoring positive numbers; instead it is capable to generate the sequence of exponents in each column following a rule so that the result of multiplying all the factors represented in a row is in a strictly increasing order with respect to the one of the succeeding row.All that implies "discovering on the fly" the primes needed to get bigger results gradually.The Numbers array is just to allow a simple verification of the correctness of the algorithm; in fact, for each of its elements, the following condition must occur... Numbers[Index]==Index+1Each element of the Coordinates array corresponds, in a sense, to a column of the imagined table.Such an element is an object for which the Base property represents the prime factor while the Exponents property represents, as an array, the column of exponents to which to rise that prime.Coordinates[0] is a sort of "seed element". In fact the code dynamically produces all the data needed to show a table with as many rows as the given Limit value.The Expand function is invocated every time the "insufficient currently available data" condition is reached.The line of code...  if ( ! Value ) ... is where the "next prime needed" condition is checked.Of course every time a new prime number is involved in the data structure all the exponents, except the last one, of its "corresponding column" must be set to 0.In the trials the max value for Limit depend on the memory available for the JavaScript interpreter and its efficiency.At the moment I'm not interested about the innumerable ways to optimize the implementation of the algorithm... but it is important to keep in mind that it is implementable in a fashion that dynamically takes advantage of mass memory as its availability increase.If needed to better understand what I've exposed here the following two online reference documents can be consulted...http://www.comprendonio.info/I/UnlimitedInside/I/Spazio%20discreto%20ad%20infinite%20dimensioni.Txthttp://www.comprendonio.info/I/UnlimitedInside/I/Sequenza%20notevole%20di%20coordinate.TxtAnyway my main concern is to get confirmation about my strong suspect that the behavior described by this algorithm is not computationally reducible.
5 Replies
Sort By:
Posted 5 months ago
 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 5 months 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.HTMOf 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 11 months 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.