Changeset 39576 in project


Ignore:
Timestamp:
02/03/21 06:39:21 (4 weeks ago)
Author:
dieggsy
Message:

Convert racket docs for chicken impl of racket/math

File:
1 edited

Legend:

Unmodified
Added
Removed
  • wiki/eggref/5/math

    r37911 r39576  
     1[[toc:]]
     2
    13== math
    24
    3 [[toc:]]
    4 
    55=== Introduction
    6 math is a chicken port of racket's {{racket/math}}.
    7 
    8 '''Disclaimer''': This is still largely under development, with the exception
    9 of the {{math.number-theory}} module, which is finished and ready for use.
    10 
    11 === API
    12 See source documentation at: [[https://docs.racket-lang.org/math/index.html]]
     6
     7math is a chicken port of racket's math library.
     8
     9The following documentation is largely taken directly from the racket
     10documentation, but tweaked for the CHICKEN implementation.
     11
     12==== math.number-theory
     13
     14===== Congruences and modular arithmetic
     15<procedure>(divides? m n) -> boolean</procedure>
     16
     17; m : integer
     18; n : integer
     19
     20Returns {{#t}} if {{m}} divides {{n}}, {{#f}} otherwise.
     21
     22Examples:
     23<enscript highlight="scheme">
     24> (divides? 2 9)
     25#f
     26> (divides? 2 8)
     27#t
     28</enscript>
     29
     30Note that 0 cannot divide anything:
     31
     32<enscript highlight="scheme">
     33> (divides? 0 5)
     34#f
     35> (divides? 0 0)
     36#f
     37</enscript>
     38
     39Practically, if {{(divides? m n)}} is {{#t}}, then {{(/ n m)}} will return an integer.
     40
     41Wikipedia: [[https://en.wikipedia.org/wiki/Divisor|Divisor]]
     42
     43<procedure>(bezout a b c ...) -> (list-of integer)</procedure>
     44
     45; a : integer
     46; b : integer
     47; c : integer
     48
     49Given integers {{a b c ...}} returns a list of integers {{(list u v w ...)}}
     50such that {{(gcd a b c ...)}} = {{(+ (* a u) (* b v) (* c w) ...)}}.
     51
     52Examples:
     53<enscript highlight="scheme">
     54> (bezout 6 15)
     55(-2 1)
     56> (+ (* -2 6) (* 1 15))
     573
     58> (gcd 6 15)
     593
     60</enscript>
     61
     62Wikipedia: [[https://en.wikipedia.org/wiki/B%C3%A9zout's_identity|Bézout's Identity]]
     63
     64<procedure>(coprime? a b ...) -> boolean</procedure>
     65
     66; a : integer
     67; b : integer
     68
     69Returns {{#t}} if the integers {{a b ...}} are coprime. Formally, a set of
     70integers is considered coprime (also called relatively prime) if their greatest
     71common divisor is 1.
     72
     73Example:
     74<enscript highlight="scheme">
     75> (coprime? 2 6 15)
     76#t
     77</enscript>
     78
     79Wikipedia: [[https://en.wikipedia.org/wiki/Coprime|Coprime]]
     80
     81<procedure>(pairwise-coprime? a b ...) -> boolean</procedure>
     82
     83; a : integer
     84; b : integer
     85
     86Returns {{#t}} if the integers {{a b ...}} are ''pairwise'' coprime, meaning that each
     87pair of integers is coprime.
     88
     89The numbers 2, 6 and 15 are coprime, but not ''pairwise'' coprime, because 6 and 15
     90share the factor 3:
     91<enscript highlight="scheme">
     92> (pairwise-coprime? 2 6 15)
     93#f
     94</enscript>
     95
     96Wikipedia:[[https://en.wikipedia.org/wiki/Pairwise_coprime|Pairwise Coprime]]
     97
     98<procedure>(solve-chinese as ns) -> integer</procedure>
     99
     100; as : (list-of integer)
     101; ns : (list-of integer)
     102
     103Given a length-k list of integers as and a length-k list of coprime moduli ns,
     104(solve-chinese as ns) returns the least natural number x that is a solution to
     105the equations
     106
     107 x = a₁ (mod n₁)
     108  ...
     109 x = aₖ (mod nₖ)
     110
     111The solution {{x}} is less than {{(* n1 ... nk)}}.
     112
     113The moduli {{ns}} must all be positive.
     114
     115What is the least number {{x}} that when divided by 3 leaves a remainder of 2, when
     116divided by 5 leaves a remainder of 3, and when divided by 7 leaves a remainder
     117of 2?
     118<enscript highlight="scheme">
     119> (solve-chinese '(2 3 2) '(3 5 7))
     12023
     121</enscript>
     122
     123Wikipedia: [[https://en.wikipedia.org/wiki/Chinese_remainder_theorem|Chinese Remainder Theorem]]
     124
     125<procedure>(quadratic-residue? a n) -> boolean</procedure>
     126
     127; a : integer
     128; n : integer
     129
     130Returns {{#t}} if {{a}} is a quadratic residue modulo {{n}}, otherwise {{#f}}. The modulus
     131{{n}} must be positive, and a must be nonnegative.
     132
     133Formally, {{a}} is a quadratic residue modulo {{n}} if there exists a number
     134{{x}} such that {{(* x x)}} = {{a}} (mod {{n}}). In other words,
     135{{(quadratic-residue? a n)}} is {{#t}} when {{a}} is a perfect square modulo
     136{{n}}.
     137
     138Examples:
     139<enscript highlight="scheme">
     140> (quadratic-residue? 0 4)
     141#f
     142> (quadratic-residue? 1 4)
     143#t
     144> (quadratic-residue? 2 4)
     145#f
     146> (quadratic-residue? 3 4)
     147#f
     148</enscript>
     149
     150Wikipedia: [[https://en.wikipedia.org/wiki/Quadratic_residue|Quadratic Residue]]
     151
     152<procedure>(quadratic-character a p) -> integer</procedure>
     153
     154; a : integer
     155; b : integer
     156
     157Returns the value of the quadratic character modulo the prime {{p}}. That is,
     158for a non-zero {{a}} the number 1 is returned when {{a}} is a quadratic
     159residue, and -1 is returned when {{a}} is a non-residue. If {{a}} is zero, then
     1600 is returned.
     161
     162If {{a}} is negative or {{p}} is not positive, quadratic-character raises an
     163error. If {{p}} is not prime, (quadratic-character a p) is indeterminate.
     164
     165This function is also known as the ''Legendre symbol''.
     166
     167<enscript highlight="scheme">
     168> (quadratic-character 0 5)
     1690
     170> (quadratic-character 1 5)
     1711
     172> (quadratic-character 2 5)
     173-1
     174> (quadratic-character 3 5)
     175-1
     176</enscript>
     177
     178Wikipedia: [[https://en.wikipedia.org/wiki/Legendre_symbol|Legendre Symbol]]
     179
     180<procedure>(jacobi-symbol a n) -> integer</procedure>
     181
     182; a : integer
     183; n : integer
     184
     185Computes the Jacobi symbol for any nonnegative integer {{a}} and any positive
     186odd integer {{n}}.
     187
     188If {{n}} is not an odd positive integer, {{(jacobi-symbol a n)}} throws an exception.
     189
     190<enscript highlight="scheme">
     191> (jacobi-symbol 1 1)
     1921
     193> (jacobi-symbol 8 11)
     194-1
     195> (jacobi-symbol 39 27)
     1960
     197> (jacobi-symbol 22 59)
     1981
     199> (jacobi-symbol 32 8)
     200Error: (jacobi-symbol) bad argument type - not an odd integer: 8
     201</enscript>
     202
     203Wikipedia: [[https://en.wikipedia.org/wiki/Jacobi_symbol|Jacobi Symbol]]
     204
     205<procedure>(modular-inverse a n) -> integer</procedure>
     206
     207; a : integer
     208; b : integer
     209
     210Returns the inverse of a modulo {{n}} if {{a}} and {{n}} are coprime, otherwise raises an
     211error. The modulus {{n}} must be positive, and {{a}} must be nonzero.
     212
     213Formally, if {{a}} and {{n}} are coprime, {{b}} = {{(modular-inverse a n)}} is the unique
     214natural number less than {{n}} such that {{(* a b)}} = {{1}} (mod {{n}}).
     215
     216<enscript highlight="scheme">
     217> (modular-inverse 2 5)
     2183
     219> (modulo (* 2 3) 5)
     2201
     221</enscript>
     222
     223Wikipedia: [[https://en.wikipedia.org/wiki/Modular_multiplicative_inverse|Multiplicative Inverse]]
     224
     225<procedure>(modular-expt a b n) -> integer</procedure>
     226
     227; a : integer
     228; b : integer
     229; n : integer
     230
     231Computes {{(modulo (expt a b) n)}}, but much more efficiently. The modulus {{n}} must
     232be positive, and the exponent {{b}} must be nonnegative.
     233
     234<enscript highlight="scheme">
     235> (modulo (expt -6 523) 19)
     23613
     237> (modular-expt -6 523 19)
     23813
     239> (modular-expt 9 158235208 19)
     2404
     241> ; don't try this at home!
     242  (modulo (expt 9 158235208) 19)
     2434
     244</enscript>
     245
     246===== Parameterized Modular Arithmetic
     247
     248The {{math.number-theory}} library supports modular arithmetic parameterized on
     249a current modulus. For example, the code
     250
     251<enscript highlight="scheme">
     252(with-modulus n
     253  (mod= (modexpt a b) c))
     254</enscript>
     255
     256corresponds with the mathematical statement ''a^b'' = ''c'' (mod ''n'').
     257
     258The current modulus is stored in a parameter that, for performance reasons, can
     259only be set using with-modulus. (The basic modular operators cache parameter
     260reads, and this restriction guarantees that the cached values are current.
     261'''NOTE:''' I'm not entirely sure this is true for the chicken port, as a
     262slightly more complicated racket syntax-case has been turned into a simple
     263syntax-rule for {{(parameterize ...)}})
     264
     265Wikipedia: [[https://en.wikipedia.org/wiki/Modular_arithmetic|Modular Arithmetic]]
     266
     267<syntax>(with-modulus n body ...)</syntax>
     268
     269; n : integer
     270
     271Alters the current modulus within the dynamic extent of {{body}}. The
     272expression {{n}} must evaluate to a positive integer.
     273
     274By default, the current modulus is 1, meaning that every modular arithmetic
     275expression that does not raise an error returns 0.
     276
     277<procedure>(current-modulus) -> integer</procedure>
     278
     279Returns the current modulus.
     280
     281Examples:
     282
     283<enscript highlight="scheme">
     284> (current-modulus)
     2851
     286> (with-modulus 5 (current-modulus))
     2875
     288</enscript>
     289
     290<procedure>(mod x) -> integer</procedure>
     291
     292; x : exact rational
     293
     294Converts a rational number {{x}} to a natural number less than the current
     295modulus.
     296
     297If {{x}} is an integer, this is equivalent to {{(modulo x n)}}. If {{x}} is a
     298fraction, an integer input is generated by multiplying its numerator by its
     299denominator’s modular inverse.
     300
     301Examples:
     302
     303<enscript highlight="scheme">
     304> (with-modulus 7 (mod (* 218 7)))
     3050
     306> (with-modulus 7 (mod 3/2))
     3075
     308> (with-modulus 7 (mod/ 3 2))
     3095
     310> (with-modulus 7 (mod 3/7))
     311Error: (modular-inverse) bad argument type - not coprime to modulus 7: 7
     312</enscript>
     313
     314<procedure>(mod+ a ...) -> integer</procedure>
     315<procedure>(mod* a ...) -> integer</procedure>
     316
     317; a : integer
     318
     319Equivalent to {{(modulo (+ a ...) (current-modulus))}} and {{(modulo (* a ...) (current-modulus))}},
     320respectively, but generate smaller intermediate values.
     321
     322<procedure>(modsqr a) -> integer</procedure>
     323<procedure>(modexpt a b) -> integer</procedure>
     324
     325; a : integer
     326; b : integer
     327
     328Equivalent to {{(mod* a a)}} and {{(modular-expt a b (current-modulus))}}, respectively.
     329
     330<procedure>(mod- a b ...) -> integer</procedure>
     331
     332; a : integer
     333; b : integer
     334
     335Equivalent to {{(modulo (- a b ...) (current-modulus))}}, but generates smaller
     336intermediate values. Note that {{(mod- a)}} = {{(mod (- a))}}.
     337
     338<procedure>(mod/ a b ...) -> integer</procedure>
     339
     340; a : integer
     341; b : integer
     342
     343Divides a by {{(* b ...)}}, by multiplying {{a}} by the multiplicative inverse of
     344{{(* b ...)}}. The one-argument variant returns the modular inverse of {{a}}.
     345
     346Note that {{(mod/ a b ...)}} is '''not''' equivalent to
     347{{(modulo (/ a b ...) (current-modulus))}}; see {{mod=}} for a demonstration.
     348
     349<procedure>(mod= a b ...) -> boolean</procedure>
     350<procedure>(mod< a b ...) -> boolean</procedure>
     351<procedure>(mod<= a b ...) -> boolean</procedure>
     352<procedure>(mod> a b ...) -> boolean</procedure>
     353<procedure>(mod>= a b ...) -> boolean</procedure>
     354
     355; a : integer
     356; b : integer
     357
     358Each of these is equivalent to {{(op (mod a) (mod b) ...)}}, where op is the
     359corresponding numeric comparison function. Additionally, when given one
     360argument, the inequality tests always return {{#t}}.
     361
     362Suppose we wanted to know why 17/4 = 8 (mod 15), but 51/12 (mod 15) is
     363undefined, even though normally 51/12 = 17/4. In code,
     364
     365<enscript highlight="scheme">
     366> (with-modulus 15 (mod/ 17 4))
     3678
     368> (/ 51 12)
     36917/4
     370> (with-modulus 15 (mod/ 51 12))
     371Error: (modular-inverse) bad argument type - not coprime to modulus 15: 12
     372</enscript>
     373
     374We could try to divide by brute force: find, modulo 15, all the numbers {{a}} for
     375which {{(mod* a 4)}} is 17, then find all the numbers {{b}} for which {{(mod* a 12)}} is
     37651.
     377<enscript highlight="scheme">
     378(import srfi-42)
     379> (with-modulus 15
     380    (list-ec (:range a 15)
     381             (if (mod= (mod* a 4) 17))
     382      a))
     383(8)
     384> (with-modulus 15
     385    (list-ec (:range a 15)
     386             (if (mod= (mod* a 12) 51))
     387      a))
     388(3 8 13)
     389</enscript>
     390
     391So the problem isn't that {{b}} doesn't exist, it's that {{b}} isn't
     392''unique''.
     393
     394===== Primes
     395<procedure>(prime? z) -> boolean</procedure>
     396
     397; z : integer
     398
     399Returns {{#t}} if {{z}} is a prime, {{#f}} otherwise.
     400
     401Formally, an integer {{z}} is prime when the only positive divisors of {{z}}
     402are 1 and {{(abs z)}}.
     403
     404The positive primes below 20 are:
     405<enscript highlight="scheme">
     406> (filter prime? (iota 20 1))
     407(2 3 5 7 11 13 17 19)
     408</enscript>
     409
     410The corresponding negative primes are:
     411<enscript highlight="scheme">
     412> (filter prime? (iota 20 0 -1))
     413(-2 -3 -5 -7 -11 -13 -17 -19)
     414</enscript>
     415
     416Wikipedia: [[https://en.wikipedia.org/wiki/Prime_number|Prime Number]]
     417
     418<procedure>(odd-prime? z) -> boolean</procedure>
     419
     420; z : integer
     421
     422Returns {{#t}} if {{z}} is a odd prime, {{#f}} otherwise.
     423
     424<enscript highlight="scheme">
     425> (odd-prime? 2)
     426#f
     427> (odd-prime? 3)
     428#t
     429</enscript>
     430
     431<procedure>(nth-prime n) -> integer</procedure>
     432
     433; n : integer
     434
     435Returns the {{n}}th positive prime; {{n}} must be nonnegative.
     436
     437<enscript highlight="scheme">
     438> (nth-prime 0)
     4392
     440> (nth-prime 1)
     4413
     442> (nth-prime 2)
     4435
     444</enscript>
     445
     446<procedure>(random-prime n) -> integer</procedure>
     447
     448; n : integer
     449
     450Returns a random prime smaller than {{n}}, which must be greater than 2.
     451
     452The function {{random-prime}} picks random numbers below {{n}} until a prime is
     453found.
     454
     455<enscript highlight="scheme">
     456> (random-prime 10)
     4573
     458> (random-prime 10)
     4592
     460> (random-prime 10)
     4615
     462</enscript>
     463
     464<procedure>(next-prime z) -> integer</procedure>
     465
     466; z : integer
     467
     468Returns the first prime larger than {{z}}.
     469
     470<enscript highlight="scheme">
     471> (next-prime 4)
     4725
     473> (next-prime 5)
     4747
     475</enscript>
     476
     477<procedure>(prev-prime z) -> integer</procedure>
     478
     479Returns the first prime smaller than {{z}}.
     480
     481<enscript highlight="scheme">
     482> (prev-prime 4)
     4833
     484> (prev-prime 5)
     4853
     486</enscript>
     487
     488<procedure>(next-primes z n) -> (list-of integer)</procedure>
     489
     490; z : integer
     491; n : integer
     492
     493Returns list of the next {{n}} primes larger than {{z}}; {{n}} must be
     494nonnegative.
     495
     496<enscript highlight="scheme">
     497> (next-primes 2 4)
     498(3 5 7 11)
     499</enscript>
     500
     501<procedure>(prev-primes z n) -> (list-of integer)</procedure>
     502
     503; z : integer
     504; n : integer
     505
     506Returns list of the next {{n}} primes smaller than {{z}}; {{n}} must be
     507nonnegative.
     508
     509<enscript highlight="scheme">
     510> (prev-primes 13 4)
     511(11 7 5 3)
     512</enscript>
     513
     514<procedure>(factorize n) -> (list-of (list integer integer))</procedure>
     515
     516; n : integer
     517
     518Returns the factorization of a natural number {{n}}. The factorization consists of
     519a list of corresponding primes and exponents. The primes will be in ascending
     520order.
     521
     522The prime factorization of 600 = 2^3 * 3^1 * 5^2:
     523
     524<enscript highlight="scheme">
     525> (factorize 600)
     526((2 3) (3 1) (5 2))
     527</enscript>
     528
     529<procedure>(defactorize f) -> integer</procedure>
     530
     531; f : (list-of (list integer integer))
     532
     533Returns the natural number, whose factorization is given by {{f}}. The
     534factorization {{f}} is represented as described in {{factorize}}.
     535
     536<enscript highlight="scheme">
     537> (defactorize '((2 3) (3 1) (5 2)))
     538600
     539</enscript>
     540
     541Wikipedia: [[https://en.wikipedia.org/wiki/Integer_factorization|Integer Factorization]]
     542
     543<procedure>(divisors z) -> (list-of integer)</procedure>
     544
     545; z : integer
     546
     547Returns a list of all positive divisors of the integer {{z}}. The divisors appear
     548in ascending order.
     549
     550<enscript highlight="scheme">
     551> (divisors 120)
     552(1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120)
     553> (divisors -120)
     554(1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120)
     555</enscript>
     556
     557<procedure>(prime-divisors z) -> (list-of integer)</procedure>
     558
     559; z : integer
     560
     561Returns a list of all positive prime divisors of the integer {{z}}. The divisors
     562appear in ascending order.
     563
     564<enscript highlight="scheme">
     565> (prime-divisors 120)
     566'(2 3 5)
     567</enscript>
     568
     569<procedure>(prime-exponents z) -> (list-of integer)</procedure>
     570
     571; z : integer
     572
     573Returns a list of the exponents of in a factorization of the integer {{z}}.
     574
     575<enscript highlight="scheme">
     576> (define z (* 2 2 2 3 5 5))
     577> (prime-divisors z)
     578(2 3 5)
     579> (prime-exponents z)
     580(3 1 2)
     581</enscript>
     582
     583===== Roots
     584
     585<procedure>(integer-root n m) -> integer</procedure>
     586
     587; n : integer
     588; m : integer
     589
     590Returns the mth integer root of {{n}}. This is the largest integer {{r}} such that
     591{{(expt r m)}} <= {{n}}.
     592
     593<enscript highlight="scheme">
     594> (integer-root (expt 3 4) 4)
     5953
     596> (integer-root (+ (expt 3 4) 1) 4)
     5973
     598</enscript>
     599
     600<procedure>(integer-root/remainder n m) -> integer integer</procedure>
     601
     602; n : integer
     603; m : integer
     604
     605Returns two values. The first, {{r}}, is the {{m}}th integer root of {{n}}. The
     606second is {{n}}-{{r}}^{{m}}.
     607
     608<enscript highlight="scheme">
     609> (integer-root/remainder (expt 3 4) 4)
     6103
     6110
     612> (integer-root/remainder (+ (expt 3 4) 1) 4)
     6133
     6141
     615</enscript>
     616
     617===== Powers
     618
     619<procedure>(max-dividing-power a b) -> integer</procedure>
     620
     621; a : integer
     622; b : integre
     623
     624Returns the largest exponent, {{n}}, of a power with base {{a}} that divides
     625{{b}}.
     626
     627That is, {{(expt a n)}} divides {{b}} but {{(expt a (+ n 1))}} does not divide {{b}}.
     628
     629<enscript highlight="scheme">
     630> (max-dividing-power 3 (expt 3 4))
     6314
     632> (max-dividing-power 3 5)
     6330
     634</enscript>
     635
     636<procedure>(perfect-power m) -> (or (list integer integer) #f)</procedure>
     637
     638; m : integer
     639
     640If {{m}} is a perfect power, a list with two elements {{b}} and {{n}} such that
     641{{(expt b n)}} = {{m}} is returned, otherwise {{#f}} is returned.
     642
     643<enscript highlight="scheme">
     644> (perfect-power (expt 3 4))
     645(3 4)
     646> (perfect-power (+ (expt 3 4) 1))
     647#f
     648</enscript>
     649
     650<procedure>(perfect-power? m) -> boolean</procedure>
     651
     652; m : integer
     653
     654Returns {{#t}} if {{m}} is a perfect power, otherwise {{#f}}.
     655
     656<enscript highlight="scheme">
     657> (perfect-power? (expt 3 4))
     658#t
     659> (perfect-power? (+ (expt 3 4) 1))
     660#f
     661</enscript>
     662
     663Wikipedia: [[https://en.wikipedia.org/wiki/Perfect_power|Perfect Power]]
     664
     665<procedure>(prime-power m) -> (or (list integer integer) #f)</procedure>
     666
     667; m : integer
     668
     669If {{M}} is a power of the form {{(expt p n)}} where p is prime, then a list with the
     670prime and the exponent is returned, otherwise {{#f}} is returned.
     671
     672<enscript highlight="scheme">
     673> (prime-power (expt 3 4))
     674(3 4)
     675> (prime-power (expt 6 4))
     676#f
     677</enscript>
     678
     679<procedure>(prime-power? m) -> boolean</procedure>
     680
     681; m : integer
     682
     683Returns {{#t}} if {{m}} is a prime power, otherwise {{#f}}.
     684
     685<enscript highlight="scheme">
     686> (prime-power? (expt 3 4))
     687#t
     688> (prime-power? (expt 6 4))
     689#f
     690> (prime-power? 1)
     691#f
     692> (prime-power? 0)
     693#f
     694</enscript>
     695
     696<procedure>(odd-prime-power? m) -> boolean</procedure>
     697
     698; m : integer
     699
     700Returns {{#t}} if {{m}} is a power of an odd prime, otherwise {{#f}}.
     701
     702<enscript highlight="scheme">
     703> (odd-prime-power? (expt 2 4))
     704#f
     705> (odd-prime-power? (expt 3 4))
     706#t
     707> (odd-prime-power? (expt 15 4))
     708#f
     709</enscript>
     710
     711<procedure>(as-power m) -> integer integer</procedure>
     712
     713; m : integer
     714
     715Returns two values {{b}} and {{n}} such that {{m}} = {{(expt b n)}} and {{n}}
     716is maximal.
     717
     718<enscript highlight="scheme">
     719> (as-power (* (expt 2 4) (expt 3 4)))
     7206
     7214
     722> (expt 6 4)
     7231296
     724> (* (expt 2 4) (expt 3 4))
     7251296
     726> (as-power (* (expt 2 4) (expt 3 5)))
     7273888
     7281
     729</enscript>
     730
     731<procedure>(prefect-square m) -> (or integer #f)</procedure>
     732
     733Returns {{(sqrt m)}} if {{m}} is perfect square, otherwise {{#f}}.
     734
     735<enscript highlight="scheme">
     736> (perfect-square 9)
     7373
     738> (perfect-square 10)
     739#f
     740</enscript>
     741
     742===== Multiplicative and Arithmetic Functions
     743
     744The functions in this section are ''multiplicative'' (with exception of the Von
     745Mangoldt function). In number theory, a multiplicative function is a function
     746{{f}} such that {{(f (* a b))}} = {{(* (f a) (f b))}} for all coprime natural
     747numbers {{a}} and {{b}}.
     748
     749<procedure>(totient n) -> integer</procedure>
     750
     751; n : integer
     752
     753Returns the number of integers from 1 to {{n}} that are coprime with {{n}}.
     754
     755This function is known as Euler's totient or phi function.
     756
     757<enscript highlight="scheme">
     758> (totient 9)
     7596
     760> (length (filter (curry coprime? 9) (range 10)))
     7616
     762</enscript>
     763
     764Wikipedia: [[https://en.wikipedia.org/wiki/Euler%27s_totient_function|Euler's Totient]]
     765
     766<procedure>(moebius-mu n) -> integer</procedure>
     767
     768; n : integer
     769
     770Returns:
     771
     772* 1 if {{n}} is a square-free product of an even number of primes
     773* -1 if {{n}} is a square-free product of an odd number of primes
     774* 0 if {{n}} has a multiple prime factor
     775
     776<enscript highlight="scheme">
     777> (moebius-mu (* 2 3 5))
     778-1
     779> (moebius-mu (* 2 3 5 7))
     7801
     781> (moebius-mu (* 2 2 3 5 7))
     7820
     783</enscript>
     784
     785Wikipedia: [[https://en.wikipedia.org/wiki/M%C3%B6bius_function|Moebius Function]]
     786
     787<procedure>(divisor-sum n k) -> integer</procedure>
     788
     789; n : integer
     790; k : integer
     791
     792Returns sum of the {{k}}th powers of all divisors of {{n}}.
     793
     794<enscript highlight="scheme">
     795> (divisor-sum 12 2)
     796210
     797> (apply + (map sqr (divisors 12)))
     798210
     799</enscript>
     800
     801Wikipedia: [[https://en.wikipedia.org/wiki/Divisor_function|Divisor Function]]
     802
     803<procedure>(prime-omega n) -> integer</procedure>
     804
     805; n : integer
     806
     807Counting multiplicities the number of prime factors of {{n}} is returned.
     808
     809<enscript highlight="scheme">
     810> (prime-omega (* 2 2 2 3 3 5))
     8116
     812</enscript>
     813
     814OEIS: [[https://oeis.org/A001222|Big Omega]], [[https://oeis.org/wiki/Omega(n),_number_of_prime_factors_of_n_(with_multiplicity)|Big Omega]]
     815
     816<procedure>(mangoldt-lambda n) -> number</procedure>
     817
     818; n : integer
     819
     820The von Mangoldt function. If n=p^k for a prime {{p}} and an integer {{k>=1}}
     821then {{(log n)}} is returned. Otherwise {{0}} is returned.
     822
     823Note: The Von Mangoldt function is not multiplicative.
     824
     825<enscript highlight="scheme">
     826> (mangoldt-lambda (* 3 3))
     8271.0986122886681098
     828> (log 3)
     8291.0986122886681098
     830</enscript>
     831
     832Wikipedia: [[https://en.wikipedia.org/wiki/Von_Mangoldt_function|Von Mangoldt Function]]
     833
     834===== Number Sequences
     835
     836<procedure>(bernoulli-number n) -> ratnum</procedure>
     837
     838; n : integer
     839
     840Returns the {{n}}th Bernoulli number; {{n}} must be nonnegative.
     841
     842<enscript highlight="scheme">
     843> (map bernoulli-number (iota 9))
     844(1 -1/2 1/6 0 -1/30 0 1/42 0 -1/30)
     845</enscript>
     846
     847Note that these are the ''first'' Bernoulli numbers, since
     848{{(bernoulli-number 1)}} = {{-1/2}}.
     849
     850Wikipedia: [[https://en.wikipedia.org/wiki/Bernoulli_number|Bernoulli Number]]
     851
     852<procedure>(eulerian-number n k) -> integer</procedure>
     853
     854; n : integer
     855; k : integer
     856
     857Returns the Eulerian number {{<n,k>}}; both arguments must be nonnegative.
     858
     859<enscript highlight="scheme">
     860> (eulerian-number 5 2)
     86166
     862</enscript>
     863
     864Wikipedia: [[http://mathworld.wolfram.com/EulerianNumber.html|Eulerian Number]]
     865
     866<procedure>(fibonacci n) -> integer</procedure>
     867
     868; n : integer
     869
     870Returns the {{n}}th Fibonacci number; {{n}} must be nonnegative.
     871
     872The ten first Fibonacci numbers:
     873<enscript highlight="scheme">
     874> (map fibonacci (iota 10))
     875'(0 1 1 2 3 5 8 13 21 34)
     876</enscript>
     877
     878Wikipedia: [[https://en.wikipedia.org/wiki/Fibonacci_number|Fibonacci Number]]
     879
     880<procedure>(make-fibonaci a b) -> (integer -> integer)</procedure>
     881
     882; a : integer
     883; b : integer
     884
     885Returns a function representing a Fibonacci sequence with the first two numbers
     886{{a}} and {{b}}. The {{fibonacci}} function is defined as {{(make-fibonacci 0 1)}}.
     887
     888The Lucas numbers are defined as a Fibonacci sequence starting with 2 and 1:
     889
     890<enscript highlight="scheme">
     891> (map (make-fibonacci 2 1) (iota 10))
     892(2 1 3 4 7 11 18 29 47 76)
     893</enscript>
     894
     895Wikipedia: [[https://wikipedia.org/wiki/Lucas_number|Lucas Number]]
     896
     897<procedure>(modular-fibonacci n m) -> integer</procedure>
     898
     899; n : integer
     900; m : integer
     901
     902Returns the {{n}}th Fibonacci number modulo {{m}}; {{n}} must be nonnegative
     903and {{m}} must be positive.
     904
     905The ten first Fibonacci numbers modulo 5:
     906<enscript highlight="scheme">
     907> (map (lambda (n) (modular-fibonacci n 5)) (range 10))
     908(0 1 1 2 3 0 3 3 1 4)
     909</enscript>
     910
     911<procedure>(make-modular-fibonacci a b) -> (integer integer -> integer)</procedure>
     912
     913; a : integer
     914; b : integer
     915
     916Like {{make-fibonacci}}, but makes a modular fibonacci sequence.
     917
     918<procedure>(farey-sequence n) -> (list-of ratnum)</procedure>
     919
     920; n : integer
     921
     922Returns a list of the numbers in the {{n}}th Farey sequence; {{n}} must be positive.
     923
     924The {{n}}th Farey sequence is the sequence of all completely reduced rational
     925numbers from 0 to 1 which denominators are less than or equal to {{n}}.
     926
     927<enscript highlight="scheme">
     928> (farey-sequence 1)
     929(0 1)
     930> (farey-sequence 2)
     931(0 1/2 1)
     932> (farey-sequence 3)
     933(0 1/3 1/2 2/3 1)
     934</enscript>
     935
     936Wikipedia: [[https://en.wikipedia.org/wiki/Farey_sequence|Farey Sequence]]
     937
     938<procedure>(tangent-number n) -> integer</procedure>
     939
     940; n : integer
     941
     942Returns the {{n}}th tangent number; {{n}} must be nonnegative.
     943
     944<enscript highlight="scheme">
     945> (tangent-number 1)
     9461
     947> (tangent-number 2)
     9480
     949> (tangent-number 3)
     9502
     951</enscript>
     952
     953MathWorld: [[http://mathworld.wolfram.com/TangentNumber.html|Tangent Number]]
     954
     955===== Combinatorics
     956
     957<procedure>(factorial n) -> integer</procedure>
     958
     959; n : integer
     960
     961Returns the factorial of {{n}}, which must be nonnegative. The factorial of
     962{{n}} is the number {{(* n (- n 1) (- n 2) ... 1)}}.
     963
     964<enscript highlight="scheme">
     965> (factorial 3)
     9666
     967> (factorial 0)
     9681
     969</enscript>
     970
     971Wikipedia: [[https://en.wikipedia.org/wiki/Factorial|Factorial]]
     972
     973<procedure>(binomial n k) -> integer</procedure>
     974
     975; n : integer
     976; k : integer
     977
     978Returns the number of ways to choose a set of k items from a set of n items;
     979i.e. the order of the k items is not significant. Both arguments must be
     980nonnegative.
     981
     982When {{k > n}}, {{(binomial n k) = 0}}. Otherwise, {{(binomial n k)}} is
     983equivalent to {{(/ (factorial n) (factorial k) (factorial (- n k)))}},
     984but computed more quickly.
     985
     986<enscript highlight="scheme">
     987> (binomial 5 3)
     98810
     989</enscript>
     990
     991Wikipedia: [[https://en.wikipedia.org/wiki/Binomial_coefficient|Binomial Coefficient]]
     992
     993<procedure>(permutations n k) -> integer</procedure>
     994
     995; n : integer
     996; k : integer
     997
     998Returns the number of ways to choose a sequence of {{k}} items from a set of n
     999items; i.e. the order of the {{k}} items is significant. Both arguments must be
     1000nonnegative.
     1001
     1002When {{k > n}}, {{(permutations n k) = 0}}. Otherwise, {{(permutations n k)}}
     1003is equivalent to {{(/ (factorial n) (factorial (- n k)))}}.
     1004
     1005<enscript highlight="scheme">
     1006> (permutations 5 3)
     100760
     1008</enscript>
     1009
     1010Wikipedia: [[https://en.wikipedia.org/wiki/Permutation#Permutations_in_combinatorics|Permutations]]
     1011
     1012<procedure>(multinomial n ks) -> integer</procedure>
     1013
     1014; n : integer
     1015; ks : (list-of integer)
     1016
     1017A generalization of binomial to multiple sets of choices; e.g.
     1018{{(multinomial n (list k0 k1 k2))}} is the number of ways to choose a set of
     1019{{k0}} items, a set of {{k1}} items, and a set of {{k2}} items from a set of {{n}}
     1020items. All arguments must be nonnegative.
     1021
     1022When {{(apply + ks) = n}}, this is equivalent to
     1023{{(apply / (factorial n) (map factorial ks))}}. Otherwise, multinomial returns 0.
     1024
     1025<enscript highlight="scheme">
     1026> (multinomial 5 '(3 2))
     102710
     1028> (= (multinomial 8 '(5 3))
     1029     (binomial 8 5)
     1030     (binomial 8 3))
     1031#t
     1032> (multinomial 10 '(5 3 2))
     10332520
     1034> (multinomial 0 '())
     10351
     1036> (multinomial 4 '(1 1))
     10370
     1038</enscript>
     1039
     1040Wikipedia: [[https://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients|Multinomial Coefficient]]
     1041
     1042<procedure>(partitions n) -> integer</procedure>
     1043
     1044; n : integer
     1045
     1046Returns the number of partitions of {{n}}, which must be nonnegative. A partition
     1047of a positive integer {{n}} is a way of writing {{n}} as a sum of positive integers.
     1048The number 3 has the partitions {{(+ 1 1 1)}}, {{(+ 1 2)}} and {{(+ 3)}}.
     1049
     1050<enscript highlight="scheme">
     1051> (partitions 3)
     10523
     1053> (partitions 4)
     10545
     1055</enscript>
     1056
     1057Wikipedia: [[https://en.wikipedia.org/wiki/Partition_(number_theory)|Partition]]
     1058
     1059===== Polygonal numbers
     1060
     1061<procedure>(triangle-number? n) -> boolean</procedure>
     1062<procedure>(square-number? n) -> boolean</procedure>
     1063<procedure>(pentagonal-number? n) -> boolean</procedure>
     1064<procedure>(hexagonal-number? n) -> boolean</procedure>
     1065<procedure>(heptagonal-number? n) -> boolean</procedure>
     1066<procedure>(octagonal-number? n) -> boolean</procedure>
     1067
     1068; n : integer
     1069
     1070These functions check whether the input is a polygonal number of the types
     1071triangle, square, pentagonal, hexagonal, heptagonal and octogonal respectively.
     1072
     1073Wikipedia: [[https://en.wikipedia.org/wiki/Polygonal_number|Polygonal Number]]
     1074
     1075
     1076<procedure>(triangle-number n) -> boolean</procedure>
     1077<procedure>(sqr n) -> boolean</procedure>
     1078<procedure>(pentagonal-number n) -> boolean</procedure>
     1079<procedure>(hexagonal-number n) -> boolean</procedure>
     1080<procedure>(heptagonal-number n) -> boolean</procedure>
     1081<procedure>(octagonal-number n) -> boolean</procedure>
     1082
     1083; n : integer
     1084
     1085These functions return the {{n}}th polygonal number of the corresponding type
     1086of polygonal number.
     1087
     1088===== Fractions
     1089
     1090<procedure>(mediant x y) -> ratnum</procedure>
     1091
     1092; x : ratnum
     1093; y : ratnum
     1094
     1095Computes the mediant of the numbers {{x}} and {{y}}. The mediant of two
     1096fractions {{p/q}} and {{r/s}} in their lowest term is the number
     1097{{(p+r)/(q+s)}}.
     1098
     1099<enscript highlight="scheme">
     1100> (mediant 1/2 5/6)
     11013/4
     1102</enscript>
     1103
     1104Wikipedia: [[https://en.wikipedia.org/wiki/Mediant_(mathematics)|Mediant]]
     1105
     1106===== The Quadratic Equation
     1107
     1108<procedure>(quadratic-solutions a b c) -> (list-of number)</procedure>
     1109  a : number
     1110  b : number
     1111  c : number
     1112
     1113Returns a list of all real solutions to the equation a {{x^2 + bx + c = 0}}
     1114with real coefficients.
     1115
     1116<enscript highlight="scheme">
     1117> (quadratic-solutions 1 0 -1)
     1118'(-1 1)
     1119> (quadratic-solutions 1 2 1)
     1120'(-1)
     1121> (quadratic-solutions 1 0 1)
     1122'()
     1123</enscript>
     1124
     1125<procedure>(quadratic-integer-solutions a b c) -> (list-of integer)</procedure>
     1126
     1127; a : number
     1128; b : number
     1129; c : number
     1130
     1131Returns a list of all integer solutions to the equation a {{x^2 + bx + c = 0}}
     1132with real coefficients.
     1133
     1134<enscript highlight="scheme">
     1135> (quadratic-integer-solutions 1 0 -1)
     1136'(-1 1)
     1137> (quadratic-integer-solutions 1 0 -2)
     1138'()
     1139</enscript>
     1140
     1141<procedure>(quadratic-natural-solutions a b c) -> (list-of integer)</procedure>
     1142
     1143; a : number
     1144; b : number
     1145; c : number
     1146
     1147Returns a list of all natural solutions to the equation a {{x^2 + bx + c = 0}}
     1148with real coefficients.
     1149
     1150<enscript highlight="scheme">
     1151> (quadratic-natural-solutions 1 0 -1)
     1152'(1)
     1153> (quadratic-natural-solutions 1 0 -2)
     1154'()
     1155</enscript>
     1156
     1157<procedure>(complex-quadratic-solutions a b c) -> (list-of number)</procedure>
     1158
     1159; a : number
     1160; b : number
     1161; c : number
     1162
     1163Returns a list of all complex solutions to the equation a {{x^2 + bx + c = 0}}.
     1164This function allows complex coeffecients.
     1165
     1166<enscript highlight="scheme">
     1167> (complex-quadratic-solutions 1 0 1)
     1168(0-1i 0+1i)
     1169> (complex-quadratic-solutions 1 0 (sqrt -1))
     1170(-0.7071067811865476+0.7071067811865475i 0.7071067811865476-0.7071067811865475i)
     1171> (complex-quadratic-solutions 1 0 1)
     1172(0-1i 0+1i)
     1173</enscript>
     1174
     1175===== The group Zn and Primitive Roots
     1176
     1177The numbers 0, 1, ..., n-1 with addition and multiplication modulo {{n}} is a ring
     1178called {{Zn}}.
     1179
     1180The group of units in {{Zn}} with respect to multiplication modulo {{n}} is
     1181called {{Un}}.
     1182
     1183The order of an element {{x}} in {{Un}} is the least {{k>0}} such that {{x^k=1 mod n}}.
     1184
     1185A generator the group {{Un}} is called a primitive root modulo {{n}}. Note that {{g}} is a
     1186primitive root if and only if {{order(g)=totient(n)}}. A group with a generator is
     1187called cyclic.
     1188
     1189Wikipedia: [[https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n|The Group Zn]]
     1190
     1191<procedure>(unit-group n) -> (list-of integer)</procedure>
     1192
     1193; n : integer
     1194
     1195Returns a list of all elements of {{Un}}, the unit group modulo {{n}}. The
     1196modulus {{n}} must be positive.
     1197
     1198<enscript highlight="scheme">
     1199> (unit-group 5)
     1200(1 2 3 4)
     1201> (unit-group 6)
     1202(1 5)
     1203</enscript>
     1204
     1205<procedure>(unit-group-order x n) -> integer</procedure>
     1206
     1207; x : integer
     1208; n : integer
     1209
     1210Returns the order of {{x}} in the group {{Un}}; both arguments must be
     1211positive. If {{x}} and n are not coprime, {{(unit-group-order x n)}} raises an
     1212error.
     1213
     1214<enscript highlight="scheme">
     1215> (unit-group-order 2 5)
     12164
     1217> (unit-group-order 2 6)
     1218Error: (unit-group-order) expected coprime arguments; given 2 and 6
     1219</enscript>
     1220
     1221<procedure>(unit-group-orders n) -> (list-of positive-integer)</procedure>
     1222
     1223; n : integer
     1224
     1225Returns a list {{(list (unit-group-order x0 n) (unit-group-order x1 n) ...)}}
     1226where {{x0}}, {{x1}}, {{...}} are the elements of {{Un}}. The modulus {{n}}
     1227must be positive.
     1228
     1229<enscript highlight="scheme">
     1230> (unit-group-orders 5)
     1231(1 4 4 2)
     1232> (map (cut unit-group-order <> 5) (unit-group 5))
     1233(1 4 4 2)
     1234</enscript>
     1235
     1236<procedure>(primitive-root? x n) -> boolean</procedure>
     1237
     1238; x : integer
     1239; n : integer
     1240
     1241Returns {{#t}} if the element {{x}} in {{Un}} is a primitive root modulo {{n}},
     1242otherwise {{#f}} is returned. An error is signaled if {{x}} is not a member of
     1243{{Un}}. Both arguments must be positive.
     1244
     1245<enscript highlight="scheme">
     1246> (primitive-root? 1 5)
     1247#f
     1248> (primitive-root? 2 5)
     1249#t
     1250> (primitive-root? 5 5)
     1251Error: (primitive-root?) expected coprime arguments; given 5 and 5
     1252</enscript>
     1253
     1254<procedure>(exists-primitive-root? n) -> boolean</procedure>
     1255
     1256; n : integer
     1257
     1258Returns {{#t}} if the group {{Un}} has a primitive root (i.e. it is cyclic),
     1259otherwise {{#f}} is returned. In other words, {{#t}} is returned if {{n}} is
     1260one of {{1}}, {{2}}, {{4}}, {{p^e}}, {{2*p^e}} where {{p}} is an odd prime, and
     1261{{#f}} otherwise. The modulus {{n}} must be positive.
     1262
     1263<enscript highlight="scheme">
     1264> (exists-primitive-root? 5)
     1265#t
     1266> (exists-primitive-root? 6)
     1267#t
     1268> (exists-primitive-root? 12)
     1269#f
     1270</enscript>
     1271
     1272<procedure>(primitive-root n) -> (or integer false)</procedure>
     1273
     1274Returns a primitive root of {{Un}} if one exists, otherwise {{#f}} is returned.
     1275The modulus {{n}} must be positive.
     1276
     1277<enscript highlight="scheme">
     1278> (primitive-root 5)
     12792
     1280> (primitive-root 6)
     12815
     1282</enscript>
     1283
     1284<procedure>(primitive-roots n) -> (list-of integer)</procedure>
     1285
     1286; n : integer
     1287
     1288Returns a list of all primitive roots of {Un}. The modulus {{n}} must be positive.
     1289
     1290<enscript highlight="scheme">
     1291> (primitive-roots 3)
     1292(2)
     1293> (primitive-roots 5)
     1294(2 3)
     1295> (primitive-roots 6)
     1296(5)
     1297</enscript>
     1298
     1299=== Original documentation
     1300
     1301[[https://docs.racket-lang.org/math/]]
     1302
     1303=== Development status
     1304
     1305This egg is still largely under active development, with the exception of the
     1306{{math.number-theory}} module, which is finished and ready for use.
     1307
     1308
     1309=== Implementation caveats
     1310
     1311* It's possible some undefined behavior may occur with arguments of the wrong
     1312  type, since a good amount of the original functions were originally defined
     1313  in typed racket, which AFAIK would catch those and throw an exception.
     1314
     1315* In some places the original implementation references {{unsafe-}} {{fx}} and
     1316  {{fl}} operators, but these are actually just aliased to safe operators. This
     1317  implementation just uses chicken's {{chicken.fixnum}} module, which is
     1318  unsafe. This may also lead to undefined behavior in some cases.
     1319
     1320=== Author
     1321
     1322Neil Toronto and Jens Axel SÞgaard for Racket
     1323
     1324=== Maintainer
     1325
     1326[[/users/diego-mundo|Diego A. Mundo]]
     1327
     1328=== Repository
     1329
     1330[[https://github.com/dieggsy/chicken-math]]
     1331
     1332=== License
     1333
     1334GPL-3.0
     1335
     1336=== Version History
Note: See TracChangeset for help on using the changeset viewer.