32. Number Theory

32.1 Definitions for Number Theory

Function: bern (n)

Returns the n'th Bernoulli number for integer n. Bernoulli numbers equal to zero are suppressed if zerobern is false.

See also burn.

(%i1) zerobern: true$ (%i2) map (bern, [0, 1, 2, 3, 4, 5, 6, 7, 8]); 1 1 1 1 1 (%o2) [1, - -, -, 0, - --, 0, --, 0, - --] 2 6 30 42 30 (%i3) zerobern: false$ (%i4) map (bern, [0, 1, 2, 3, 4, 5, 6, 7, 8]); 1 1 1 5 691 7 3617 43867 (%o4) [1, - -, -, - --, --, - ----, -, - ----, -----] 2 6 30 66 2730 6 510 798

Function: bernpoly (x, n)

Returns the n'th Bernoulli polynomial in the variable x.

Function: bfzeta (s, n)

Returns the Riemann zeta function for the argument s. The return value is a big float (bfloat); n is the number of digits in the return value.

load ("bffac") loads this function.

Function: bfhzeta (s, h, n)

Returns the Hurwitz zeta function for the arguments s and h. The return value is a big float (bfloat); n is the number of digits in the return value.

The Hurwitz zeta function is defined as

sum ((k+h)^-s, k, 0, inf)

load ("bffac") loads this function.

Function: binomial (x, y)

The binomial coefficient x!/(y! (x - y)!). If x and y are integers, then the numerical value of the binomial coefficient is computed. If y, or x - y, is an integer, the binomial coefficient is expressed as a polynomial.

Examples:

(%i1) binomial (11, 7); (%o1) 330 (%i2) 11! / 7! / (11 - 7)!; (%o2) 330 (%i3) binomial (x, 7); (x - 6) (x - 5) (x - 4) (x - 3) (x - 2) (x - 1) x (%o3) ------------------------------------------------- 5040 (%i4) binomial (x + 7, x); (x + 1) (x + 2) (x + 3) (x + 4) (x + 5) (x + 6) (x + 7) (%o4) ------------------------------------------------------- 5040 (%i5) binomial (11, y); (%o5) binomial(11, y)

Function: burn (n)

Returns the n'th Bernoulli number for integer n. burn may be more efficient than bern for large, isolated n (perhaps n greater than 105 or so), as bern computes all the Bernoulli numbers up to index n before returning.

burn exploits the observation that (rational) Bernoulli numbers can be approximated by (transcendental) zetas with tolerable efficiency.

load ("bffac") loads this function.

Function: cf (expr)

Converts expr into a continued fraction. expr is an expression comprising continued fractions and square roots of integers. Operands in the expression may be combined with arithmetic operators. Aside from continued fractions and square roots, factors in the expression must be integer or rational numbers. Maxima does not know about operations on continued fractions outside of cf.

cf evaluates its arguments after binding listarith to false. cf returns a continued fraction, represented as a list.

A continued fraction a + 1/(b + 1/(c + ...)) is represented by the list [a, b, c, ...]. The list elements a, b, c, ... must evaluate to integers. expr may also contain sqrt (n) where n is an integer. In this case cf will give as many terms of the continued fraction as the value of the variable cflength times the period.

A continued fraction can be evaluated to a number by evaluating the arithmetic representation returned by cfdisrep. See also cfexpand for another way to evaluate a continued fraction.

See also cfdisrep, cfexpand, and cflength.

Examples:

• expr is an expression comprising continued fractions and square roots of integers.

  (%i1) cf ([5, 3, 1]*[11, 9, 7] + [3, 7]/[4, 3, 2]); (%o1) [59, 17, 2, 1, 1, 1, 27] (%i2) cf ((3/17)*[1, -2, 5]/sqrt(11) + (8/13)); (%o2) [0, 1, 1, 1, 3, 2, 1, 4, 1, 9, 1, 9, 2]

• cflength controls how many periods of the continued fraction are computed for algebraic, irrational numbers.

  (%i1) cflength: 1$ (%i2) cf ((1 + sqrt(5))/2); (%o2) [1, 1, 1, 1, 2] (%i3) cflength: 2$ (%i4) cf ((1 + sqrt(5))/2); (%o4) [1, 1, 1, 1, 1, 1, 1, 2] (%i5) cflength: 3$ (%i6) cf ((1 + sqrt(5))/2); (%o6) [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]

• A continued fraction can be evaluated by evaluating the arithmetic representation returned by cfdisrep.

  (%i1) cflength: 3$ (%i2) cfdisrep (cf (sqrt (3)))$ (%i3) ev (%, numer); (%o3) 1.731707317073171

• Maxima does not know about operations on continued fractions outside of cf.

  (%i1) cf ([1,1,1,1,1,2] * 3); (%o1) [4, 1, 5, 2] (%i2) cf ([1,1,1,1,1,2]) * 3; (%o2) [3, 3, 3, 3, 3, 6]

Function: cfdisrep (list)

Constructs and returns an ordinary arithmetic expression of the form a + 1/(b + 1/(c + ...)) from the list representation of a continued fraction [a, b, c, ...].

(%i1) cf ([1, 2, -3] + [1, -2, 1]); (%o1) [1, 1, 1, 2] (%i2) cfdisrep (%); 1 (%o2) 1 + --------- 1 1 + ----- 1 1 + - 2

Function: cfexpand (x)

Returns a matrix of the numerators and denominators of the last (column 1) and next-to-last (column 2) convergents of the continued fraction x.

(%i1) cf (rat (ev (%pi, numer))); `rat' replaced 3.141592653589793 by 103993//33102 = 3.141592653011902 (%o1) [3, 7, 15, 1, 292] (%i2) cfexpand (%); [ 103993 355 ] (%o2) [ ] [ 33102 113 ] (%i3) %[1,1]/%[2,1], numer; (%o3) 3.141592653011902

Option variable: cflength

Default value: 1

cflength controls the number of terms of the continued fraction the function cf will give, as the value cflength times the period. Thus the default is to give one period.

(%i1) cflength: 1$ (%i2) cf ((1 + sqrt(5))/2); (%o2) [1, 1, 1, 1, 2] (%i3) cflength: 2$ (%i4) cf ((1 + sqrt(5))/2); (%o4) [1, 1, 1, 1, 1, 1, 1, 2] (%i5) cflength: 3$ (%i6) cf ((1 + sqrt(5))/2); (%o6) [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]

Function: divsum (n, k)

Function: divsum (n)

divsum (n, k) returns the sum of the divisors of n raised to the k'th power.

divsum (n) returns the sum of the divisors of n.

(%i1) divsum (12); (%o1) 28 (%i2) 1 + 2 + 3 + 4 + 6 + 12; (%o2) 28 (%i3) divsum (12, 2); (%o3) 210 (%i4) 1^2 + 2^2 + 3^2 + 4^2 + 6^2 + 12^2; (%o4) 210

Function: euler (n)

Returns the n'th Euler number for nonnegative integer n.

For the Euler-Mascheroni constant, see %gamma.

(%i1) map (euler, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]); (%o1) [1, 0, - 1, 0, 5, 0, - 61, 0, 1385, 0, - 50521]

Constant: %gamma

The Euler-Mascheroni constant, 0.5772156649015329 ....

Function: factorial (x)

Represents the factorial function. Maxima treats factorial (x) the same as x!. See !.

Function: fib (n)

Returns the n'th Fibonacci number. fib(0) equal to 0 and fib(1) equal to 1, and fib (-n) equal to (-1)^(n + 1) * fib(n).

After calling fib, prevfib is equal to fib (x - 1), the Fibonacci number preceding the last one computed.

(%i1) map (fib, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]); (%o1) [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Function: fibtophi (expr)

Expresses Fibonacci numbers in terms of the constant %phi, which is (1 + sqrt(5))/2, approximately 1.61803399.

By default, Maxima does not know about %phi. After executing tellrat (%phi^2 - %phi - 1) and algebraic: true, ratsimp can simplify some expressions containing %phi.

(%i1) fibtophi (fib (n)); n n %phi - (1 - %phi) (%o1) ------------------- 2 %phi - 1 (%i2) fib (n-1) + fib (n) - fib (n+1); (%o2) - fib(n + 1) + fib(n) + fib(n - 1) (%i3) ratsimp (fibtophi (%)); (%o3) 0

Function: inrt (x, n)

Returns the integer n'th root of the absolute value of x.

(%i1) l: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]$ (%i2) map (lambda ([a], inrt (10^a, 3)), l); (%o2) [2, 4, 10, 21, 46, 100, 215, 464, 1000, 2154, 4641, 10000]

Function: jacobi (p, q)

Returns the Jacobi symbol of p and q.

(%i1) l: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]$ (%i2) map (lambda ([a], jacobi (a, 9)), l); (%o2) [1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0]

Function: lcm (expr_1, ..., expr_n)

Returns the least common multiple of its arguments. The arguments may be general expressions as well as integers.

load ("functs") loads this function.

Function: minfactorial (expr)

Examines expr for occurrences of two factorials which differ by an integer. minfactorial then turns one into a polynomial times the other.

(%i1) n!/(n+2)!; n! (%o1) -------- (n + 2)! (%i2) minfactorial (%); 1 (%o2) --------------- (n + 1) (n + 2)

Function: partfrac (expr, var)

Expands the expression expr in partial fractions with respect to the main variable var. partfrac does a complete partial fraction decomposition. The algorithm employed is based on the fact that the denominators of the partial fraction expansion (the factors of the original denominator) are relatively prime. The numerators can be written as linear combinations of denominators, and the expansion falls out.

(%i1) 1/(1+x)^2 - 2/(1+x) + 2/(2+x); 2 2 1 (%o1) ----- - ----- + -------- x + 2 x + 1 2 (x + 1) (%i2) ratsimp (%); x (%o2) - ------------------- 3 2 x + 4 x + 5 x + 2 (%i3) partfrac (%, x); 2 2 1 (%o3) ----- - ----- + -------- x + 2 x + 1 2 (x + 1)

Function: primep (n)

Returns true if n is a prime, false if not.

Function: qunit (n)

Returns the principal unit of the real quadratic number field sqrt (n) where n is an integer, i.e., the element whose norm is unity. This amounts to solving Pell's equation a^2 - n b^2 = 1.

(%i1) qunit (17); (%o1) sqrt(17) + 4 (%i2) expand (% * (sqrt(17) - 4)); (%o2) 1

Function: totient (n)

Returns the number of integers less than or equal to n which are relatively prime to n.

Option variable: zerobern

Default value: true

When zerobern is false, bern excludes the Bernoulli numbers which are equal to zero. See bern.

Function: zeta (n)

Returns the Riemann zeta function if x is a negative integer, 0, 1, or a positive even number, and returns a noun form zeta (n) for all other arguments, including rational noninteger, floating point, and complex arguments.

See also bfzeta and zeta%pi.

(%i1) map (zeta, [-4, -3, -2, -1, 0, 1, 2, 3, 4, 5]); 2 4 1 1 1 %pi %pi (%o1) [0, ---, 0, - --, - -, inf, ----, zeta(3), ----, zeta(5)] 120 12 2 6 90

Option variable: zeta%pi

Default value: true

When zeta%pi is true, zeta returns an expression proportional to %pi^n for even integer n. Otherwise, zeta returns a noun form zeta (n) for even integer n.

(%i1) zeta%pi: true$ (%i2) zeta (4); 4 %pi (%o2) ---- 90 (%i3) zeta%pi: false$ (%i4) zeta (4); (%o4) zeta(4)

This document was generated on March, 19 2006 using texi2html 1.76.