Re: CVS commit: src/games/factor

[Joerg Sonnenberger <joerg%britannica.bec.de@localhost>]

On Mon, May 17, 2010 at 02:53:40AM +0400, Aleksej Saushev wrote:
> Consider natural numbers as finite cardinals, the way set theorists do.
> Factorization of a number a is non-empty set {<f_i, n_i>} (f_i are distinct)
> such that product f_i^n_i = a.

That's a product decomposition. The term "factorisation" is after all
refering to a specific decomposition with additional requirements on the
f_i.

> It is easy to see that there exist numbers
> which occur in any their factorization. These are called "prime" numbers.

That's not the definition of prime elements algebra uses, which is the
relevant field here. The algebraic definition of prime explicitly
excludes units.

> And zero and unit are among them. Note that you have to introduce
> "non-empty" to treat unit rather than zero. That makes zero no less
> prime than anything else and even a bit more prime than unit.

The definition of prime also excludes 0 for the simple reason that 0
doesn't have any divisor in an integral domain like we are using here.
As I said originally, 0 as prime doesn't make sense at all as the
criterion for primality, both the high school version (only dividable by
1 and itself) and algebraic version (not 0, not a unit, f it divides a
product it divides it least one of the factors) fail, if only due to the
lack of zero divisors.. 

> When you construct integer numbers, you see that the same applies to "-1".
> That you prefer to choose "2" as prime rather than "-2" happens due to the
> wish to preserve (where applicable) theorems when reducing back to natural
> numbers.

2 and -2 are both primes and for that reason the factorization in Z is
only unique up to units. factor(6) never implemented the behavior
descripted in the man page for possible negative numbers as the smallest
prime factor of a number is of course the additive inverse of the
largest (positive) prime factor and that is the last one computed. That
is of course ignoring completely the question of why a specific
factorization should be choosen.

So this all leaves two questions:

(1) Should the diagnostic messages be fatal or not.  The implemented
behavior matches the specification in the documentation in this regard,
but for interactive use it is certainly more useful to continue reading
numbers.

(2) Is printing the more convient "1: 1" more useful behavior or not. It
is not a prime factorisation, just a product decomposition. As long as
it is not complaimed to be something else, there is little harm in doing
that. This is consistent with non-buggy behavior of e.g. Wolfram Alpha
and if all you want to know are smallest factors, it is certainly a
reasonable answer.

Joerg