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

Posted 7 months ago
963 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 7 months 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.HTMObserving 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 7 months ago
 What is called the "reverse factoring counter" appears to be a description, more or less, of the Sieve of Eratosthenes 1, 2.
Posted 7 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.