% Copyright The Numerical Algorithms Group Limited 1991, 1992, 1993
% Certain derivative-work portions Copyright (C) 1988 by Leslie Lamport.
% All rights reserved

% Number page

%-------------------------------------------------------------------------
\begin{page}{NumberPage}{\Language{} Number Types}
%-------------------------------------------------------------------------
\beginscroll
The following types of numbers are among those available in \Language{}.
\beginmenu

\menulink{Integers}{IntegerPage}\tab{16}
Arithmetic with arbitrarily large integers.

\menulink{Fractions}{FractionPage} \tab{16}
Rational numbers and general fractions.

\menulink{Machine Floats}{DoubleFloatXmpPage} \tab{16}
Fixed precision machine floating-point.

\menulink{Real Numbers}{FloatXmpPage} \tab{16}
Arbitrary precision decimal arithmetic.

\menulink{Complex Numbers}{ComplexXmpPage} \tab{16}
Complex numbers in general.

\menulink{Finite Fields}{ugProblemFinitePage} \tab{16}
Arithmetic in characteristic \spad{p}.
\endmenu
\horizontalline\newline
Additional Topics
\beginmenu

\menulink{Numeric Functions}{ugProblemNumericPage}
\menulink{Cardinal Numbers}{CardinalNumberXmpPage}
\menulink{Machine-sized Integers}{SingleIntegerXmpPage}
\menulink{Roman Numerals}{RomanNumeralXmpPage}
\menulink{Continued Fractions}{ContinuedFractionXmpPage}
\menulink{Partial Fractions}{PartialFractionXmpPage}
\menulink{Quaternions}{QuaternionXmpPage}
\menulink{Octonions}{OctonionXmpPage}
\menulink{Repeating Decimals}{DecimalExpansionXmpPage}
\menulink{Repeating Binary Expansions}{BinaryExpansionXmpPage}
\menulink{Repeating Hexadecimal Expansions}{HexadecimalExpansionXmpPage}
\menulink{Expansions in other Bases}{RadixExpansionXmpPage}

%\menulink{p-adic Numbers}{PAdicPage}
%\menulink{Algebraic Numbers}{AlgebraicNumberPage}
\endmenu

\endscroll
\autobuttons
\end{page}

% Fraction Page

%-------------------------------------------------------------------------
\begin{page}{FractionPage}{Fractions}
%-------------------------------------------------------------------------

\beginscroll
\Language{} handles fractions in many different contexts
and will automatically simplify fractions whenever possible.
Here are some examples:
\spadpaste{1/4 - 1/5}
\spadpaste{f := (x**2 + 1)/(x - 1) \bound{f}}
\spadpaste{g := (x**2 - 3*x + 2)/(x + 2) \bound{g}}
\spadpaste{f * g \free{f g}}
\endscroll
Additional Topics:
\beginmenu

\menulink{Rational Numbers}{RationalNumberPage} \tab{18}
Quotients of integers

\menulink{Quotient Fields}{FractionXmpPage}  \tab{18}
Quotients over an arbitrary integral domain

%\menulink{Localizations}{LocalizationPage}  \tab{18}
%Fractions in the most general setting
\endmenu
\autobuttons
\end{page}

%-------------------------------------------------------------------------
\begin{page}{RationalNumberPage}{Rational Numbers}
%-------------------------------------------------------------------------
\beginscroll
Like integers, rational numbers can be arbitrarily large.
For example:
\spadpaste{61657 ** 10 / 999983 ** 12}
Rational numbers will not be converted to decimals unless you explicitly
ask \Language{} to do so.
To convert a rational number to a decimal, use the function
\spadfun{numeric}.
Here's an example:
\spadpaste{x := 104348/33215 \bound{x}}
\spadpaste{numeric x \free{x}}
You can find the numerator and denominator of rational numbers using
the functions \spadfun{numer} and \spadfun{denom}, respectively.
\spadpaste{numer(x) \free{x}}
\spadpaste{denom(x) \free{x}}
To factor the numerator and denominator of a fraction, use the following
command:
\spadpaste{factor(numer x) / factor(denom x) \free{x}}
\endscroll
\autobuttons
\end{page}

%\begin{page}{LocalizationPage}{Localizations}
%\beginscroll
%\endscroll
%\autobuttons

% Algebraic Number Page

%\begin{page}{AlgebraicNumberPage}{Algebraic Numbers}
%\beginscroll
%\endscroll
%\autobuttons

% p-adic Number Page

%\begin{page}{PAdicPage}{p-adic Numbers}
%\beginscroll
%\endscroll
%\autobuttons

% Integer Page

%-------------------------------------------------------------------------
\begin{page}{IntegerPage}{Integers}
%-------------------------------------------------------------------------

\beginscroll
In \Language{}, integers can be as large as you like.
Try the following examples:
\spadpaste{x := factorial(200) \bound{x}}
\spadpaste{y := 2**90 - 1 \bound{y}}
Of course, you can now do arithmetic as usual on these (very)
large integers:
\spadpaste{x + y \free{x y}}
\spadpaste{x - y \free{x y}}
\spadpaste{x * y \free{x y}}
\Language{} can factor integers, but numbers with small prime factors
\spadpaste{factor(x) \free{x}}
will factor more rapidly than numbers with large prime factors.
\spadpaste{factor(y) \free{y}}
\horizontalline
Additional Topics
\beginmenu

\menulink{General Info}{IntegerXmpPage} \tab{16}
General information and examples of integers.

\menulink{Factorization}{ugxIntegerPrimesPage} \tab{16}
Primes and factorization.

\menulink{Functions}{IntegerNumberTheoryFunctionsXmpPage} \tab{16}
Number theoretic functions.

\menulink{Examples}{IntegerExamplePage} \tab{16}
Examples from number theory.

\menulink{Problems}{IntegerProblemPage} \tab{16}
Problems from number theory.

\endmenu
\endscroll
\autobuttons
\end{page}

%\begin{page}{IntegerFactorizationPage}{Factorization of Integers}
%\beginscroll
%\endscroll
%\autobuttons

%-------------------------------------------------------------------------
\begin{page}{IntegerExamplePage}{Examples}
%-------------------------------------------------------------------------
\beginscroll
One can show that if an integer of the form 2**k + 1 is prime, then
k must be a power of 2.
\downlink{Proof}{IntegerExampleProofPage}
\par
Pierre Fermat conjectured that every integer of the forn 2**(2**n) + 1
is prime.
Let's look for a counterexample.
First define a function:
\spadpaste{f: NNI -> INT \bound{f1}}
\spadpaste{f(n) == 2**(2**n) + 1 \bound{f} \free{f1}}
Now try commands like:
\spadpaste{factor f(1) \free{f}}
\spadpaste{factor f(2) \free{f}}
until you find an integer of this form which is composite.
You can also try the following command:
\spadpaste{for n in 1..6 repeat output factor f(n) \free{f}}
Obviously, Fermat didn't have access to \Language{}!
\endscroll
\autobuttons
\end{page}

%-------------------------------------------------------------------------
\begin{page}{IntegerExampleProofPage}{Proof}
%-------------------------------------------------------------------------

\beginscroll
Proposition.  If 2**k + 1 is prime, then k is a power of 2.
\newline
Proof.  Suppose that k = m * n with m > 1 odd.  Then
%
\centerline{2**n = -1 (mod (2**n + 1))}
\centerline{2**(n * m) = (-1)**m = -1 (mod (2**n + 1))}
\centerline{2**k + 1 = 0 (mod (2**n + 1))}
%
Therefore, 2**k + 1 is divisible by 2**n + 1.
Now 1 < 2**n + 1 and since m > 1, 2**n + 1 < 2**k + 1.
Hence, 2**k + 1 has a non-trivial factor.
\newline
QED
\endscroll
\autobuttons
\end{page}

%-------------------------------------------------------------------------
\begin{page}{IntegerProblemPage}{Problems}
%-------------------------------------------------------------------------

\beginscroll
One can show that if an integer of the form 2**k - 1 is prime, then
k must be prime.
\downlink{Proof}{IntegerProblemProofPage}
\newline
Problem \#1:  Find the smallest prime p such that \spad{2**p - 1} is not prime.
\downlink{Answer}{IntegerProblemAnswerPage1}
\newline
Problem \#2:  Find the smallest positive integer \spad{n} such that
\spad{n**2 - n + 41} isn't prime.
\downlink{Answer}{IntegerProblemAnswerPage2}
\endscroll
\autobuttons
\end{page}


%-------------------------------------------------------------------------
\begin{page}{IntegerProblemProofPage}{Proof}
%-------------------------------------------------------------------------
\beginscroll
Proposition.  If \spad{2**k - 1} is prime, then \spad{k} is prime.
\newline
Proof.  Suppose that k = m * n is a non-trivial factorization.
Then
%
\centerline{2**m = 1 (mod (2**m - 1))}
\centerline{2**(m * n) = 1 (mod (2**m - 1))}
\newline
and 2**m - 1 is a non-trivial factor of 2**k - 1.
\newline
QED
\endscroll
\autobuttons
\end{page}

%-------------------------------------------------------------------------
\begin{page}{IntegerProblemAnswerPage1}{Solution to Problem \#1}
%-------------------------------------------------------------------------
\beginscroll
Problem \#1:  Find the smallest prime p such that \spad{2**p - 1}
is not prime.
\newline
First, define a function:
\spadpaste{f: NNI -> INT \bound{f1}}
\spadpaste{f(n) == 2**n - 1 \bound{f} \free{f1}}
You can try factoring f(p) as p ranges through the set of primes.
For example,
\spadpaste{factor f(7) \free{f}}
This gets tedious after a while, so let's use \Language{}'s stream
facility.  (A stream is essentially an infinite sequence.)
\newline
First, we create a stream consisting of the positive integers:
\spadpaste{ints := [n for n in 1..] \bound{ints}}
Now, we create a stream consisting of the primes:
\spadpaste{primes := [x for x in ints | prime? x] \bound{primes} \free{ints}}
Here's the 25th prime:
\spadpaste{primes.25 \free{primes}}
Next, create the stream of numbers of the form 2**p - 1 with p prime:
\spadpaste{numbers := [f(n) for n in primes] \bound{numbers} \free{primes f}}
Finally, form
the stream of factorizations of the elements of \spad{numbers}:
\spadpaste{factors := [factor n for n in numbers] \bound{factors} \free{numbers}}
You can see that the fifth number in the stream (2047 = 23*89)
is the first one that has a non-trivial factorization.
Since 2**11 = 2048, the solution to the problem is 11.
\newline
Here's another way to see that 2047 is the first number in the stream that
is composite:
\spadpaste{nums := [x for x in numbers | not prime? x] \bound{nums} \free{numbers}}
\endscroll
\autobuttons
\end{page}

%-------------------------------------------------------------------------
\begin{page}{IntegerProblemAnswerPage2}{Solution to Problem \#2}
%-------------------------------------------------------------------------
\beginscroll
Problem \#2:  Find the smallest positive integer n such that
\spad{n**2 - n + 41} is not prime.
\newline
When n = 41, n**2 - n + 41 = 41**2, which certainly isn't prime.
Let's see if any smaller integer works.
Here are the first 40 values:
\spadpaste{numbers := [n**2 - n + 41 for n in 0..40] \bound{numbers}}
Now have \Language{} factor the numbers on this list:
\spadpaste{[factor n for n in numbers] \free{numbers}}
You can see that 41 is the smallest positive integer n such that
n**n - n + 41 is not prime.
\endscroll
\autobuttons
\end{page}