Message Boards Message Boards

GROUPS:

Is the "reverse factoring" counter behavior computationally irreducible?

Posted 7 months ago
954 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^1

8 == 2^33^05^0*7^0

9 == 2^03^25^0*7^0

The 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+1

Each 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.Txt

http://www.comprendonio.info/I/UnlimitedInside/I/Sequenza%20notevole%20di%20coordinate.Txt

Anyway my main concern is to get confirmation about my strong suspect that the behavior described by this algorithm is not computationally reducible.

5 Replies
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.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.

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.

Posted 1 month 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!)

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.

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