Transcript 12. Mathsx

Contest Algorithms
January 2016
12. Maths
Types, BigInteger, combinatorics
(the maths of counting), primes,
GCD, modulo,
assorted maths and stats functions
Contest Algorithms: 12. Maths
1
Overview
 1. Primitive Types and Number Representation
 2. BigInteger
 factorials, powers, contest examples
 BIFun, BigRational
 3. Sums and Series
 4. Combinatorics
 Fibonacci, Binomial, Catalan
 5. Log and Exponent Rules
Contest Algorithms:12. Maths
2
 6. Prime Numbers
 prime testing, generation (sieve), factorization,
divisors (number, sum)
 7. GCD, LCM
 8. Divisibility
 9. Modulo Arithmetic
 mod, %, floorMod, fast calculation tricks,
congruences, Fermat, Totient function, Euler
Contest Algorithms:12. Maths
3
 10. Complex Numbers
 11. Assorted Math Functions
 linear regression, root finding, integration, etc.
 12. Assorted Statistical Functions
 mean, variance, standard deviation, covariance, etc.
Contest Algorithms:12. Maths
4
More info:
https://docs.oracle.com/javase/tutorial/java/
nutsandbolts/datatypes.html
1. Primitive Types
2 x 109
9 x 1018
Contest Algorithms:12. Maths
5
Numerical Constants
see PrintNumberConstants.java
 Integer.MAX_VALUE, Integer.MIN_VALUE
 Long.MAX_VALUE, Long.MIN_VALUE
 Double.MAX_VALUE, Double.MIN_VALUE, Double.NaN
 Math.E, Math.PI
Contest Algorithms:12. Maths
6
Double details
 A double represents real numbers using 64 bits.
 1 bit of sign, 52 bits of "data" and 11 bits of exponent
data
Contest Algorithms:12. Maths
7
What's the Maximum double?
 A decimal number is represented according to:
 The maximum value has sign == 0, all 1's in the data part, and e =
211-2 = 2046 (normalization doesn't allow all 1's)
 max is 1· (2 – 2-52)· 21023 ≈ 21024 ≈ 10102*3 x 24 =
10306 x 16 = 1.6 x 10307 (actually 1.8 x 10308)
Contest Algorithms:12. Maths
8
Doubles are Inaccurate
 Between 252 ≈ 4.5 x1015 and 253-1 ≈ 9 x 1015 all the integers can
be represented exactly in the data part.
 From 253 to 254, the the data numbers are multiplied by 2, so
only even integers can be represented exactly.
 From 251 to 252, the spacing between numbers is 0.5.
 In other words, depending on the size of the number, its
representation inside double may only be close to its real
value.
 working with doubles (floats) has inaccuracy built-in;
 avoid using doubles (floats)
Contest Algorithms:12. Maths
9
More Info on Number Representation
 Java Quick Guide: double type
 http://www.mobilefish.com/tutorials/java/
java_quickguide_double.html
 Floating Point in Java
 http://introcs.cs.princeton.edu/java/91float/
 A Tutorial on Data Representation
 http://www3.ntu.edu.sg/home/ehchua/programming/java/
datarepresentation.html
Contest Algorithms:12. Maths
10
2. BigInteger
 Arbitrarily large integer type
 Immutable which means must reassign changes to the variable
 If you're asked to work with very large numbers (larger than
long, 263), use BigInteger
 Basic operations: +, -, /, *, %, pow, bit-manipulation
 Advanced operations: gcd, modulo arithmetic (modPow),
base conversion, probabilistic prime testing (Miller-Rabin)
11
 There is BigDecimal for manipulating very large floating
point numbers
 it has the same accuracy problems as double since all values will
be approximate; try to use BigInteger
 Get to know BigInteger's API
 https://docs.oracle.com/javase/8/
docs/api/java/math/BigInteger.html
 A good, brief BigInteger tutorial:
 http://wiki.compsci.ca/index.php?title=Java_Big_Integers
Contest Algorithms:12. Maths
12
Max size of a BigInteger?
 There is no theoretical limit, but one limit is the amount of
heap space allocated to Java
 in most contests this is set to be -Xmx1024m on the command line
 BigInteger stores a number in an int[] array
 an array can store a max of 232 elements
 so a BigInteger can be made up of at most 232 ints
 this means the biggest BigInteger can have 232*32 bits = 21024 bits
 21024 = 21020 * 24 ≈ 103*102 * 16 = 1.6 x 10307 (actually 1.8 x 10308)
Contest Algorithms:12. Maths
13
BigInteger vs long Factorial
import java.math.BigInteger;
public class Factorial {
public static void main(String[] args) {
BigInteger n = BigInteger.ONE;
for (int i=1; i<=25; i++) {
n = n.multiply(BigInteger.valueOf(i));
System.out.println(i + "! = " + n);
}
//-- long solution (ONLY WORKS TO 20)
long fact = 1;
for (long i=1; i<=25; i++) {
fact = fact * i;
System.out.println(i + "! = " + fact);
}
}
}
see BigFactorial.java
14
Results
1! = 1
2! = 2
3! = 6
4! = 24
:
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000
21! = 51090942171709440000
22! = 1124000727777607680000
23! = 25852016738884976640000
24! = 620448401733239439360000
25! = 15511210043330985984000000
BigInteger
1! = 1
2! = 2
3! = 6
4! = 24
:
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000
21! = -4249290049419214848
22! = -1250660718674968576
23! = 8128291617894825984
24! = -7835185981329244160
25! = 7034535277573963776
long
15
Return to Binary Exponentiation
see Power.java
from "Divide &
Conquer" slides
public static BigInteger powBI(BigInteger x, long n)
// binary exponentiation with BigInteger x
{
if (n <= 0)
return BigInteger.ONE;
else if (n % 2 == 1) {
// n is odd
BigInteger p = powBI(x, (n-1)/2);
return x.multiply(p).multiply(p);
}
else { // n is even
BigInteger p = powBI(x, n/2);
return p.multiply(p);
}
} // end of powBI()
Contest Algorithms:12. Maths
16
Using powBI()
BigInteger two = new BigInteger("2");
for (int i=10; i <= 200; i=i+10)
System.out.println("2^" + i + " = " + powBI(two,i));
long startTime = System.currentTimeMillis();
BigInteger res = powBI(two, 300000000L);
// System.out.println("pow BI = " + res);
// printing the result takes about 30 secs!
System.out.println("Evaluation time (secs): " +
(System.currentTimeMillis() - startTime)/1000);
Contest Algorithms:12. Maths
17
Contest Algorithms:12. Maths
18
'Super' powBI() – all BigInteger args
public static BigInteger superPow(BigInteger x, BigInteger n)
// binary exponentiation with BigInteger x and n
{
BigInteger result = BigInteger.ONE;
while (n.signum() > 0) {
// while n > 0
// looping with BigIntegers is slow
if (n.testBit(0)) // is n even?
result = result.multiply(x);
x = x.multiply(x);
// square x
n = n.shiftRight(1); // n = n/2
}
return result;
} // end of superPow()
Contest Algorithms:12. Maths
19
Using superPow()
BigInteger nbi = new BigInteger("300000000");
startTime = System.currentTimeMillis();
try {
// sometimes runs out of heap space
res = superPow(two,nbi);
}
catch(Exception e)
{ System.out.println(e); }
// System.out.println("Super (slow) pow = " + res);
// same answer as before
System.out.println("Evaluation time (secs): " +
(System.currentTimeMillis() - startTime)/1000);
Contest Algorithms:12. Maths
// 34 secs
20
Pow Summary
 BigInteger can deal with very, very large numbers
 that's good!
 Using BigInteger for every number (instead of long or int)
will slow your code down
 that's bad!
Contest Algorithms:12. Maths
21
Generate Pythagorean Triples
see PythTrip.java
 Three positive integers (a,b,c) where a < b < c,
and a2 + b2 = c2
 Use BigInteger mainly to use
BigInteger.gcd(), and as a longer
example.
Contest Algorithms:12. Maths
22
Example: N bills, F friends
see BillFriends.java
sum N large bills and divide the
large sum between F friends
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int numBills = sc.nextInt();
int numFriends = sc.nextInt();
BigInteger sum = BigInteger.ZERO;
for (int i = 0; i < numBills; i++) { // sum the large bills
BigInteger V = sc.nextBigInteger();
sum = sum.add(V);
}
System.out.println("Total of bills: " + sum +
"; each friend pays: " +
sum.divide(BigInteger.valueOf(numFriends)));
}
23
Contest Algorithms:12. Maths
24
Example: Basic Remains
see BasicRemains.java
 Given a base b and two non-negative integers p and
m – both in base b, compute p%m and print the result
as a base b integer.
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int b = sc.nextInt();
BigInteger p = new BigInteger(sc.next(), b); // 2nd arg is radix/base
BigInteger m = new BigInteger(sc.next(), b);
System.out.println((p.mod(m)).toString(b));
}
25
see SimplifyFractions.java
Example: Simplifying Fractions
 Reduce a large fraction to its simplest form by dividing
both numerator and denominator with their GCD.
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
BigInteger p = sc.nextBigInteger();
sc.next(); // we ignore the division sign in the input
BigInteger q = sc.nextBigInteger();
BigInteger gcd = p.gcd(q);
System.out.println(p.divide(gcd) + " / " + q.divide(gcd));
}
26
Example: Compute xy mod n
see ModPowTest.java
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
BigInteger x = BigInteger.valueOf(sc.nextInt()); // int -> BigInteger
BigInteger y = BigInteger.valueOf(sc.nextInt());
BigInteger n = BigInteger.valueOf(sc.nextInt());
System.out.println("x^y mod n == " + x.modPow(y,n));
}
27
More Examples
 BIFun.java
 http://www.java2s.com/
Tutorial/Java/
0040__Data-Type/
0680__BigInteger.htm
Contest Algorithms:12. Maths
BigInteger toBinary(String s)
BigInteger random(int numBits)
BigInteger random(BigInteger min, BigInteger max)
boolean isEven(BigInteger n)
boolean isMultiple(BigInteger y, BigInteger x)
BigInteger power(int m, int n)
BigInteger power(BigInteger m, BigInteger n)
BigInteger sqrt(BigInteger n)
BigInteger factorial(int n)
ArrayList<BigInteger> fibs(int n)
BigInteger fib(int n)
ArrayList<BigInteger> threeN(int n)
BigInteger[] egcd(BigInteger a, BigInteger b)
BigInteger nextPrime(BigInteger start)
boolean isPrime(long n)
boolean isPrime(BigInteger n)
ArrayList<BigInteger> tdFactors(BigInteger n)
ArrayList<BigInteger> rhoFactors(BigInteger n)
28
see BigRational.java
Big Rationals
 My BigRational.java contains a
BigRational class which implements
rationals (e.g. 4/5) using two
BigIntegers
 one for the numerator, one for the
denominator
 This approach allows very large
rationals to be manipulated, and
avoids many accuracy problems.
Contest Algorithms:12. Maths
BigRational(int numerator,
int denominator)
BigRational(int numerator)
BigRational(String s)
BigRational(BigInteger numerator,
BigInteger denominator)
String toString()
int compareTo(BigRational b)
boolean isZero()
boolean isPositive()
boolean isNegative()
boolean equals(Object y)
int hashCode()
BigRational times(BigRational b)
BigRational plus(BigRational b)
BigRational negate()
BigRational minus(BigRational b)
BigRational reciprocal()
BigRational divides(BigRational b)
double doubleValue()
29
Usage
public static void main(String[] args)
{ // 1/2 + 1/3 = 5/6
BigRational x = new BigRational(1, 2);
BigRational y = new BigRational(1, 3);
BigRational z = x.plus(y);
System.out.println(z);
// 8/9 + 1/9 = 1
x = new BigRational(8, 9);
y = new BigRational(1, 9);
z = x.plus(y);
System.out.println(z);
// 1/200000000 + 1/300000000 = 1/120000000
x = new BigRational(1, 200000000);
y = new BigRational(1, 300000000);
z = x.plus(y);
System.out.println(z);
Contest Algorithms:12. Maths
// 1073741789/20 + 1073741789/30 = 1073741789/12
x = new BigRational(1073741789, 20);
y = new BigRational(1073741789, 30);
z = x.plus(y);
System.out.println(z);
:
30
// 4/17 * 17/4 = 1
x = new BigRational(4, 17);
y = new BigRational(17, 4);
z = x.times(y);
System.out.println(z);
// 3037141/3247033 * 3037547/3246599 = 841/961
x = new BigRational(3037141, 3247033);
y = new BigRational(3037547, 3246599);
z = x.times(y);
System.out.println(z);
// 1/6 - -4/-8 = -1/3
x = new BigRational(1, 6);
y = new BigRational(-4, -8);
z = x.minus(y);
System.out.println(z);
// 0
x = new BigRational(0, 5);
System.out.println(x);
System.out.println(x.plus(x).compareTo(x) == 0);
:
Contest Algorithms:12. Maths
// true
31
// -1/200000000 + 1/300000000 = -1/60000000
x = new BigRational(-1, 200000000);
y = new BigRational(1, 300000000);
z = x.plus(y);
System.out.println(z);
} // end of main()
Contest Algorithms:12. Maths
32
Bernoulli Numbers
see Bernoulli.java
 Use BigRational to implement the generation of Bernoulli
numbers, a sequence involving very large fractional
numerators and denominators:
 See https://en.wikipedia.org/wiki/
Bernoulli_number
Contest Algorithms:12. Maths
33
3. Sum of Powers
 Useful in many situations:
Contest Algorithms:12. Maths
34
Geometric Series
 For r ≠ 1, the sum of the first n terms of a geometric series:
 As n goes to infinity, the sum becomes:
Contest Algorithms:12. Maths
35
4. Combinatorics
 The study of countable discrete structures
 How many [objects]?
 Count [objects]…
 Contest problems frequently involve Fibonacci numbers,
Binomial coefficients, or Catalan numbers
36
Fibonacci numbers
 Fibonacci numbers:
see FibMemo.java
from "Divide &
Conquer" slides
 fib(0) = 0, fib(1) = 1
 fib(n) = fib(n-1) + fib(n-2)
 Example: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,
377, 610, 987, 1597, 2584, 4181, 6765, …
 grows quickly
 Some problems involving Fibonacci number require
BigInteger (see later)
37
Fibonacci numbers
Zeckendorf’s Theorem: every positive integer can
be written in a unique way as a sum of Fibonacci
numbers. The sum does not include two
consecutive Fibonacci numbers.
 Given a positive integer n, such a sum can be found
using a Greedy technique:
 Take the largest Fibonacci number f lower than n
 Repeat with n-f instead of n until n-f = 0
38
Fibonacci Numbers
O(1) approximation of the nth Fibonacci number
= -0.61803…
 Binet’s formula
1 5 n 1 5 n
Fn  ((
) (
) )/ 5
2
2
 Golden ratio:
see fibBinets() in
FibMemo.java
1 5

 1.61803
2
Not accurate for large values of n
39
Binomial Coefficient
nC
k
see Binomial.java
from "Divide &
Conquer" slides
 How many ways are there to choose k things out
of n possibilities?
 n
n!
 
 k  ( n  k )! k !
say "n choose k"
 Coefficients of (a+b)n
 n  n  n  n1
(a  b)    a    a b 
0
1
n
 n  nk k
  a b 
k
 n n
  b
 n
40
Binomial Coef and Pascal's Triangle
nC
k
0
1
2
5C
3
n rows
== 10
3
4
5
0
1
2
3
k columns
4
5
41
Example:
 The binomial coefficients of (x + y)3 are 1, 3, 3, 1
 1x3 + 3x2y + 3xy2 + 1y3
 Use the formula nCk = n!/((n-k)!  k!)
 arithmetic overflow occurs for n > 12
 Tricks
 During computation, first divide, then multiply
 Use Pascal's triangle (see Dynamic Prog slides)
 Use BigInteger (see later)
42
Pascal's Triangle & Fibonacci
Contest Algorithms:12. Maths
43
Pascal's Triangle and Primes
 Move the triangle’s rows so that row n starts at column 2n:
Contest Algorithms:12. Maths
44
Test for Primality
 A column number is prime when all the numbers in
that column are divisible by their row number
 e.g. column 13 is prime: it has two entries: 10 which is
divisible by 5, and 6 which is divisible by 6
 e.g. column 12 is not prime: the two 1's are not evenly
divisible by their row numbers
Contest Algorithms:12. Maths
45
Problems involving Binomial Coefs
 Counting the number of ways of:
 making subsets
 “n choose k” means the number of ways of choosing a subset of k
elements from a set with n elements
 forming distinct partitions
 perhaps the most common use of binomial coefficients in
combinatorics, but it's often hard to spot
 rephrase the problem into choosing things from a set
 searching a grid
Contest Algorithms:12. Maths
46
Partitions Example
 How many ways can we write an expression involving nonnegative integers that uses p '+' signs and == n ?
 e.g. Let n be 2, p = 2.
The expressions can be “1+1+0”, “1+0+1”, “0+1+1”,
“2+0+0”, “0+2+0”, and “0+0+2”
 6 different ways using 2 plus signs
 note that the number of integers in the expression, m, is p+1
Contest Algorithms:12. Maths
47
Rewrite problem as a set choosing
 To make n, we need n '1's. There are p '+'s. Put these '1's
and '+'s into a set:
{ 1, 1, 1, …, 1, +, +, …, +}
set size == n + p
n 1's
p 1's
 Any selection represents an expression.
 e.g. "+1111++11+1+1” corresponds to "0+4+0+2+1+1"
 "111++11+11+1+" is "3+0+2+2+1+0"
Contest Algorithms:12. Maths
48
 Total number of selections: (n+p)!
 But the 1's are not unique, so we divide by n!
 But the +'s are not unique, so we divide by p!
 The total number of selections where the ordering of the
1's and +'s do not matter:
=
𝑛+𝑝 !
𝑛!𝑝!
= n+pCp =
Contest Algorithms:12. Maths
n+pC
n
49
City Grid Problem
 A person wants to return to their house that is 3 blocks
south and 5 blocks east. How many ways can he get
home?
The connection to the binomial is
easiest to see via Pascal's triangle.
Write the number of ways onto
the corners of the squares.
Contest Algorithms:12. Maths
50
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
3
2
1
1
1
1
1
1
1
1
1
2
3
4
3
6
10
Contest Algorithms:12. Maths
4
1
1
10
1
5
1
1
1
1
1
1
1
1
2
1
3
1
1
1
2
3
3
6
1
1
1
1
1
1
1
1
4
4
1
1
1
1
1
2
3
4
3
6
10
4
10
20
5
6
15
15
51
Compare to Pascal's Triangle
1
1
1
1
1
1
1
2
3
4
3
6
10
4
10
20
1
1
5
6
15 21
15
52
35
56
If there are r rows and c columns
in the grid, then the no. of ways =
( c+r )
Cr
Contest Algorithms:12. Maths
8C
3
= 56
52
 A person wants to return to their house that is 3 blocks
south and 5 blocks east. How many ways can he get
home?
 The number of ways == (5+3)C3 = (5+3)C5
Contest Algorithms:12. Maths
53
Catalan numbers
The Catalan number sequence appears in many
combinatorial problems.
 The first Catalan numbers for n = 0, 1, 2, 3, …, 25 are
 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012,
742900, 2674440, 9694845, 35357670, 129644790, 477638700,
1767263190, 6564120420, 24466267020, 91482563640,
343059613650, 1289904147324, 4861946401452, …
 The numbers grow quickly, which mean they should be
coded with BigInteger
54
 Recursive definitions (easy and efficient for coding):
the Cn notation is easy to confuse with
the binomial coefficient notation nCk
2(2𝑛 − 1)
𝐶𝑛 =
𝐶𝑛−1
𝑛+1
Contest Algorithms:12. Maths
55
Code
see CalcCatalan.java
public static BigInteger catalan(int n)
{
BigInteger[] cats = new BigInteger[n + 1];
2(2𝑛 − 1)
𝐶𝑛 =
𝐶𝑛−1
cats[0] = new BigInteger("1");
𝑛+1
for (int i = 1; i <= n; i++)
cats[i] = cats[i - 1].multiply(BigInteger.valueOf(4*i - 2)).
divide(BigInteger.valueOf(i+1));
return cats[n];
} // end of catalan()
Contest Algorithms:12. Maths
56
Problems using Catalan numbers
 How many ways are there to build a balanced formula
from n pairs of parentheses?
 Divide the formula into two parts: (……)(……)
 The first part contains k pairs, the second part has n-1-k pairs.
 So the first part has Ck possibilities, while the second part has Cn-1k possibilities.
 e.g. using 3 pairs of parens == C3 == Cat(3) == 5
 ()()(), ()(()), (())(), ((())) and (()())
Contest Algorithms:12. Maths
57
 Cn is the number of Dyck words of length 2n.
 A Dyck word is a string consisting of n X's and n Y's where
the start of the string does not have more Y's than X's
 e.g the following are the Dyck words of length 6:
 XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.
 length == 6, so n == 3, C3 == cat(3) == 5
Contest Algorithms:12. Maths
58
 A rooted binary tree is full if every vertex has either two
children or no children.
 Cn is the number of full binary trees with n + 1 leaves
 no. leaves == 4, so n == 3, C3 == cat(3) == 5
Contest Algorithms:12. Maths
59
 Cat(n) is the number of ways a convex polygon of n+2
sides can be triangulated
 polygon sides == 5, so n == 3, C3 == cat(3) == 5
Contest Algorithms:12. Maths
60
 Cat(n) == the number of paths with 2n steps on a rectangular
grid from (0,0) to (n,n) that do not cross the main diagonal.
Contest Algorithms:12. Maths
61
 A good list of Catalan problems:
 http://mathforum.org/mathimages/index.php/Catalan_Numbers
 Also see the Wiki page:
 https://en.wikipedia.org/wiki/Catalan_number
Contest Algorithms:12. Maths
62
5. Computing logarithms, base b
 In Java, Math.log() uses base e
 How to compute loga(x)?
 Math.log(x) / Math.log(a)
 More generally:
see MathFun.java
public double log(double base, double x)
{ return Math.log(x) / Math.log(base); }
63
Other Log
Laws
Contest Algorithms:12. Maths
64
Some Exponent Laws
Contest Algorithms:12. Maths
65
Convert bases?
 Integer.toString(int i, int radix) takes an integer and a
radix (the base) and returns that integer's string
representation in that base.
 String hexRepr = Integer.toString(255, 16) // returns "FF"
 To go the other way around, i.e. from a string
representing a number in a different base there is
Integer.parseInt(String s, int radix)
 int myNum = Integer.parseInt("FF", 16) // returns 255 in decimal
Contest Algorithms:12. Maths
66
 In toString(int i, int radix) if the radix is smaller than
Character.MIN_RADIX or larger than
Character.MAX_RADIX, then the radix 10 is used instead
 min == 2; max == 36
 nasty design
 For bigger radixs use BigInteger
Contest Algorithms:12. Maths
67
Base Conversion to List of Ints
 Integer.toString converts a number and base into a string.
 Another approach is to generate a list of integers. This is
best when the base is less than 10 (e.g. 2, 8)
 Example: repInBase(2578, 2) ==>
[1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0]
Contest Algorithms:12. Maths
68
Code
see BaseReps.java
public static int[] repInBase(long number, int base)
{
long basePower = base; // increase until > number
int exponent = 1;
while (number >= basePower) {
basePower *= base;
exponent++;
}
int[] rep = new int[exponent];
for (int i = 0; i < exponent; i++) {
basePower /= base;
rep[i] = (int) (number / basePower);
number %= basePower;
}
return rep;
} // end of repInBase()
Contest Algorithms:12. Maths
69
6. Prime Numbers
 A prime number is an integer  2 and can only be divided
by 1 and itself
 It cannot be written as a product of other numbers
 E.g. 2,3,5,7 are prime; 4,6,8,9,10 are not
 A number n  2 which isn’t prime is called composite.
 Prime numbers less than 200:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67
71 73 79 83 89 97 101 103 107 109 113 127 131 137
139 149 151 157 163 167 173 179 181 191 193 197 199
70
 Prime counts:
N
Primes <= N
10
4
100
25
1,000
168
10,000
1,229
100,000
9,592
1,000,000
78,498
10,000,000
664,579
100,000,000
5,761,455
1,000,000,000 50,847,534
 Useful for factoring due to the Fundamental Theorem of
Arithmetic
Contest Algorithms:12. Maths
71
Fundamental Theorem of Arithmetic
 Any number n  2 is expressible as a unique product of 1
or more prime numbers.
 e.g. 22, 100, 12, 17
22 = 2·11, 100 = 2·2·5·5,
12 = 2·2·3, 17 = 17
 In other words, every number can be factorized into
primes.
72
Testing if a number is prime, isPrime(n)
 Check if n is divisible by 2, …, n-1
 O(n)
 Check if n is divisible by 2, 3, …, sqrt(n)
 O(sqrt(n))
 Check if n is divisible by 3, 5, 7, …, sqrt(n)
 O(sqrt(n)/2) = O(sqrt(n)) + check of 2
 Check if n is divisible by primes ≤ sqrt(n)
 fastest: O(sqrt(n) / log(sqrt(n)))
Contest Algorithms:12. Maths
73
Prime Testing (third approach)
see Primes.java
public static boolean isPrime(long num)
{
if (num <= 1)
return false;
if (num == 2)
return true;
if (num % 2 == 0)
return false;
for (long i = 3; i*i <= num; i += 2)
if (num % i == 0)
// no need to check even numbers
return false;
return true;
} // end of isPrime()
74
Generating primes from 1 to N
 Simple algorithm:
for (int i = 2; i <= N; i++)
if (isPrime(i))
System.out.println(i);
 Better algorithm:
 Sieve of Eratosthenes
Contest Algorithms:12. Maths
75
Sieve of Eratosthenes
Sieve multiples of 2:
Contest Algorithms:12. Maths
76
Sieve multiples of 3:
Sieve multiples of 5:
continue until 77…
Contest Algorithms:12. Maths
77
Sieve of Eratosthenes (in words)
Generate a list of prime numbers in [2..N]:
1. Fill the list with all the numbers 0..N, as potential primes
2. Exclude 0 and 1
3. 2 is prime so exclude all multiples of 2
 4, 6, 8, 10…
4. The next non-excluded number in the list (3) is a prime. So
exclude all multiples of 3 (9, 15…)
5. Continue …
6. Once N is reached, the list contains only the primes in
[2..N]
78
Code
see Primes.java
// globals in Primes class
public static final int PRIME_BOUND = 10000000;
public static boolean[] bitsSieve;
// indicates whether a number in the range [0..N] is prime or not
public static List<Integer> primes = new ArrayList<Integer>();
// a list of primes in the range [0..N]
// these data structures are created by sieve();
// all the other prime functions use them
// in main()
sieve(PRIME_BOUND);
Contest Algorithms:12. Maths
79
public static void sieve(int N)
{ bitsSieve = new boolean[N+1];
Arrays.fill(bitsSieve, true); // set all bits to 1
bitsSieve[0] = bitsSieve[1] = false; // except for index 0 and 1
// mark non-primes <= N
for (int i = 2; i*i <= N; i++) {
// if i is prime, then mark multiples of i as nonprime
// suffices to consider multiples i, i+1, ..., N/i
if (bitsSieve[i]) {
for (int j = i; i*j <= N; j++)
bitsSieve[i*j] = false;
}
}
// add primes to list
for (int i = 2; i <= N; i++)
if (bitsSieve[i])
primes.add(i);
System.out.println("No. of primes <= " + N + ": " + primes.size());
} // end of sieve
Contest Algorithms:12. Maths
80
Revised Prime Testing
We can use the primes list
to implement the fourth
version of isPrime():
public static boolean iePrime4(long num)
{
if ((primes.get(primes.size()-1) < Math.sqrt(num))) {
System.out.println("Not enough primes in table to test " + num);
return false;
}
if (num < bitsSieve.length)
return bitsSieve[(int) num]; // O(1) for small primes
for (int i = 0; i < primes.size(); i++) {
if (primes.get(i) > Math.sqrt(num))
return true;
if (num % primes.get(i) == 0)
return false;
}
return true;
} // end of iePrime4()
Contest Algorithms:12. Maths
81
Probablistic Prime Testing
 Implement isPrime() by repeating doing a prime test with
a low likelihood of mistakenly saying a number is prime.
 it the test says that n "is prime" many times then it is very likely that
n really is prime
 A probable prime (PRP) is an integer that satisfies a test
that is passed by all prime numbers, and not passed by
most composite numbers.
 https://en.wikipedia.org/wiki/Probable_prime
Contest Algorithms:12. Maths
82
 One well known probable prime test is to use Fermat's
Little theorem (see later)
 BigInteger has another probable prime test built-in
 the Miller-Rabin test (https://en.wikipedia.org/wiki/
Miller%E2%80%93Rabin_primality_test)
 BigInteger.isProbablePrime()
Contest Algorithms:12. Maths
83
Code
import java.math.BigInteger;
public class MillerRabin
{
public static void main(String[] args)
{
BigInteger n = new BigInteger(args[0]);
int certainty = Integer.parseInt(args[1]);
see MillerRabin.java
System.out.println(n.toString() + " is " +
(n.isProbablePrime(certainty) ?
"probably prime" : "composite"));
}
}
// end of MillerRabin class
Contest Algorithms:12. Maths
84
Prime Factorization
 Factoring a number n writes it as a product of other
numbers: n = a × b × c
 Prime factorization of a number n writes it as a product of
primes
 e.g. 91 = 7×13 ; 3600 = 24 × 32 × 52
85
Find Prime Factors of N
see Primes.java
public static List<Integer> getPFs(long num)
{
List<Integer> factors = new ArrayList<Integer>();
int i = 0;
long p = primes.get(i);
// using p = 2, 3, 4, ..., is also ok
while ((num != 1) && (p*p <= num)) {
while (num % p == 0) {
num /= p;
factors.add((int) p);
}
p = primes.get(++i); // only consider primes!
}
if (num != 1)
factors.add((int) num); // special case if num is actually a prime
return factors;
} // end of getPFs()
Contest Algorithms:12. Maths
86
Count the number of Prime factors of N
public static long countPFs(long num)
{
int i = 0;
long p = primes.get(i);
long count = 0;
while ((num != 1) && (p*p <= num)) {
while (num % p == 0) {
num /= p;
count++;
}
p = primes.get(++i);
}
if (num != 1)
count++;
return count;
} // end of countPFs()
Contest Algorithms:12. Maths
87
Count the number of Different Prime factors of N
public static long numDifferentPFs(long num)
{
int i = 0;
long p = primes.get(i);
long count = 0;
while ((num != 1) && (p*p <= num)) {
if (num % p == 0)
count++; // count this prime factor only once
while (num % p == 0)
num /= p;
p = primes.get(++i);
}
if (num != 1)
count++;
return count;
} // end of numDifferentPFs()
Contest Algorithms:12. Maths
88
Number of divisors
 If the prime factorisation of a number n is
 Then the number of positive divisors of n is
• e.g. the prime factors of 60 = 22 x 3 x 5
• the number of divisors is 3 x 2 x 2 == 12
{1,2,3,4,5,6,10,12,15,20,30,60}
89
Code
public static long numDivisors(long num)
{
int i = 0;
long p = primes.get(i);
long ans = 1;
while ((num != 1) && (p*p <= num)) {
long power = 0;
while (num % p == 0) {
num /= p;
power++;
}
ans *= (power + 1);
p = primes.get(++i);
}
if (num != 1)
ans *= 2;
// last factor has pow = 1, we add 1 to it
return ans;
} // end of numDivisors()
Contest Algorithms:12. Maths
90
Sum the Divisors
 e.g. N=60 has 12 divisors whose sum is 168
 60 = 22 x 3 x 5
 Divisors: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60
 If N = ai x bj x … x ck then the sum of the divisors of N is:
(ai+1-1)/(a-1) x (bj+1-1)/(b-1) x … x (ck+1-1)/(c-1)
 For 60, sum == (23-1)/1 x (32-1)/2 x (52-1)/4
== 7 x 4 x 6 == 168
Contest Algorithms:12. Maths
91
Code
public static long sumOfDivisors(long num)
{
int i = 0;
long p = primes.get(i);
long ans = 1;
while ((num != 1) && (p*p <= num)) {
long power = 0;
while (num % p == 0) {
num /= p;
power++;
}
ans *= ((long) Math.pow((double) p, power+1.0) - 1) / (p-1);
p = primes.get(++i);
}
if (num != 1)
ans *= ((long) Math.pow((double) num,2.0) - 1) / (num-1); // last one
return ans;
} // end of sumOfDivisors()
Contest Algorithms:12. Maths
92
Examples of Use
see Primes.java
public static void main(String[] args)
{
sieve(PRIME_BOUND);
// this boolean[] can be used for checking primes in 0-PRIME_BOUND
System.out.println("Is 199 prime: " + isPrime(199));
System.out.println("Is 200 prime: " + isPrime(200));
// true
// false
long bigPNum = 2147483647L; // prime
System.out.println("Is 2147483647 prime: " + isPrime(bigPNum)); // true
System.out.println("Is 2147483647 prime: " + isPrime4(bigPNum)); // true
System.out.println("Is 100000000000001L prime: " + isPrime(100000000000001L));
System.out.println("Is 100000000000001L prime: " + isPrime4(100000000000001L));
// too big
long bCNum1 = 136117223861L;
// composite: 104729*1299709
System.out.println("Is 136117223861L prime: " + isPrime(bCNum1)); // false
:
Contest Algorithms:12. Maths
93
List<Integer> factors = getPFs(bigPNum);
printList(bigPNum, factors);
factors = getPFs(bCNum1);
// 2 large prime factors 104729 * 1299709
printList(bCNum1, factors);
long bigCNum2 = 142391208960L;
// composite with many factors
// 2^10 * 3^4 * 5*7^4 * 11*13
factors = getPFs(bigCNum2);
printList(bigCNum2, factors);
System.out.println("Info about the number 50");
System.out.println(" Number of prime factors: " + countPFs(50));
// 2^1 * 5^2 => 3
}
System.out.println("
Number of different prime factors: " + numDifferentPFs(50));
// 2^1 * 5^2 => 2
System.out.println("
Sum of its prime factors: " + sumPFs(50));
// 2^1 * 5^2 => 2 + 5 + 5 = 12
System.out.println("
Number of divisors: " + numDivisors(50));
// 1, 2, 5, 10, 25, 50; 6 divisors
System.out.println("
Sum of its divisors: " + sumOfDivisors(50));
// 1 + 2 + 5 + 10 + 25 + 50 = 93
System.out.println("
totient(): " + totient(50));
// 20 integers < 50 are relatively prime with 50
// end of main()
Contest Algorithms:12. Maths
94
Execution
Contest Algorithms:12. Maths
95
7. Greatest Common Divisor
The Greatest Common Divisor (GCD) of two integers,
a, b is the largest integer d that divides into a and b
without any remainder.
 Example: gcd(4,8) = 4, gcd(6,9) = 3
 One usage of GCD is to simplify fractions
 e.g., 6/9 = (6/gcd(6,9)) / (9/gcd(6,9)) = (6/3) / (9/3) = 2/3
96
Euclid’s algorithm for GCD
see GCDTests.java
public static long gcd(long a, long b)
{ return (b == 0) ? a : gcd(b, a % b);
}
 Repeated replaces the bigger integer by its
remainder modulo the smaller integer.
 E.g.: a = 34398, b = 2132
gcd(34398, 2132)  (34398 % 2132 == 286) = gcd(2132, 286)
(2132 % 286 == 130) = gcd(286, 130)
 (286 % 130 == 26) = gcd(130, 26)
 (130 % 26 == 0) = gcd(26, 0)
= 26
97
Examples
 gcd(77, 11) = 11
 gcd(77, 33) = 11
 gcd(36, 24) = 12
 gcd(25, 24) = 1
 Therefore 24 and 25 are relatively prime
98
Least Common Multiple
see GCDTests.java
 The Least Common Multiple (LCM) is the smallest
positive integer c which is divisible by both a and b
 e.g., lcm(9, 6) == 18
public static long lcm(long a, long b)
{ return a * (b / gcd(a, b)); }
The parentheses force division before
multiplication to avoid overflow
99
Examples
 lcm(100, 10) = 100
 lcm(7, 5) = 35
 lcm(21, 9) = 63
100
Extended Euclid’s Algorithm
 The gcd(a,b) result can be expressed as ax+by, where
x and y are integers
 e.g. gcd(44, 25) == 1, and x = 4, y = -7
 1 = (44 * 4) + (25 * -7) = 176 - 175
 The extended version of gcd() returns the gcd value
and x and y
101
Code
see GCDTests.java
public static int[] egcd(int a, int b)
// returns three values in an array: {gcd, x, y} such that gcd = x*a + y*b
{
int[] vals = new int[3];
if (b == 0) {
vals[0] = a;
vals[1] = 1;
vals[2] = 0;
}
else {
// Otherwise, recurse
int q = a/b;
vals = egcd(b, a % b);
int temp = vals[1] - vals[2]*q;
vals[1] = vals[2];
vals[2] = temp;
}
return vals;
} // end of egcd()
Contest Algorithms:12. Maths
102
Relatively Prime Numbers and GCD
 Two numbers a, b are relatively prime (coprime) if they
have no common divisors apart from 1
 In other words, a and b are relatively prime if gcd(a,b) = 1
 E.g. 8 & 15 are relatively prime since:




factors of 8 are 1,2,4,8
factorsof 15 are 1,3,5,15
1 is the only common factor
also gcd(15,8) == 1
103
Other GCD-related functions
 linearDiophantine(a, b, c)
 // compute (x, y) such that ax + by = c
Contest Algorithms:12. Maths
104
GCD Examples
see GCDTests.java
public static void main(String[] args)
{ if (args.length != 2) {
System.out.println("Usage: java GCDTests <int> <int>");
return;
}
int a = parseInt(args[0]);
int b = parseInt(args[1]);
if ((a <= 0) || (b <= 0)) {
System.out.println("Both the integers must be > 0");
return;
}
if (a < b) {
System.out.println("Swapping ints, so first is bigger");
int temp = a; a = b; b = temp;
}
System.out.println("Vals: " + a + ", " + b);
System.out.println("gcd(): " + gcd(a, b));
System.out.println("lcm(): " + lcm(a, b));
Contest Algorithms:12. Maths
int[] vals = egcd(a, b);
// vals == {gcd, j, k}
System.out.println("egcd() == " + vals[0]);
System.out.println(" " + vals[0] + " = (a * " + vals[1] +
") + (b * " + vals[2] + ")");
:
105
System.out.println("modInv == " + modInv(2, 7));
// Compute b such that ab mod n = 1.
// 4
ArrayList<Long> xs = modSolve(5, 9, 7);
// a, b, n
System.out.println("modSolve == " + Arrays.toString(xs.toArray()));
// all x solutions to ax mod n = b;
gcd(a,n) | b
System.out.println("1. crt == " + crt(6, 3, 11, 7));
// Chinese remainder theorem
// find such that z mod 6 = 3 and z mod 11 = 7
// 51
System.out.println("2. crt == " + crt(36, 12, 51, 5));
// find such that z mod 36 = 12 and z mod 51 = 5
// no soln since 36 and 51 are not relatively prime
// -1
I'll explain these at
the end of section 9
on the mod
function.
long[] res = linearDiophantine(3, 5, 19);
// xa + yb = c; res == {x, y} or null
if (res != null)
System.out.println("linearDiophantine == " + res[0] + ", " + res[1]);
// 38, -19
}
// end of main()
Contest Algorithms:12. Maths
106
public static int parseInt(String s)
{
if (s == null)
return 0;
try {
return Integer.parseInt(s);
}
catch (NumberFormatException ex) {
System.out.println(s + " could not be parsed as an int; using 0");
return 0;
}
} // end of parseInt()
Contest Algorithms:12. Maths
107
Execution
Contest Algorithms:12. Maths
108
8. Divisibility
 d | n means there is an integer k such that n = d· k.
 d | n can be said in several ways:




d divides n
d is a divisor of n
d is a factor of n
n is a multiple of d
109
Divisors Examples
1. 77 | 7: false bigger number can’t divide smaller positive
number
2. 7 | 77: true because 77 = 7 · 11
3. 24 | 24: true because 24 = 24 · 1
4. 0 | 24: false, only 0 is divisible by 0
5. 24 | 0: true, 0 is divisible by every number (0 = 24 · 0)
110
9. Modulo Arithmetic
There are two types of “mod” (confusing):
 the mod function
 r = a mod n
 Read this as r is the remainder after a is divided by n
 Similar to Java’s % operator (but not quite the same)
 the (mod) congruence
 a  r (mod n)
 Read this as a is equivalent to r when using modulo n
arithmetic
 I'm not going to discuss this one
111
Modulo Function (mod)
 a mod b = r
 If a and b are integers and b > 0, then there exist unique
integers q and r satisfying the two conditions:
 a = bq + r, and
0 ≤ r<b
 r is called the remainder
112
Examples
 13 mod 12 == 1
 29 mod 5 == 4
 10000 mod 997 == 30
 -1 mod 3 == 2
Contest Algorithms:12. Maths
113
Mod as Clock Arithmetic
 Modulo arithmetic is
arithmetic on a circle
 In modulo N , we use
only 0 through N-1
The 12-hour clock : modulo 12
If the time is 9:00 now, then 4
hours later it will be 1:00
13 mod 12 == 1
mod and Negative Numbers
 Why does -1 mod 3 = 2?
 One way to understand it is in terms of the movement
around a clock face:
0
 -1mod 3 is a counter-clockwise move
of 1 step from 0, which goes to 2
 In the same way, -5 mod 3 = 1
2
Contest Algorithms:12. Maths
1
115
mod and Java 's %
 mod and Java’s “%” operator give the same result when
the arguments are positive:
 e.g. 29 mod 5 == 29 % 5 == 4
 But mod and % are different when the number is negative:
 e.g. -1 mod 3 == 2
≠
-1 % 3 == -1
 Fix: Change the negative mod function into an equivalent
positive version, then use %:
 -1 mod 3 == 2 mod 3 == 2 % 3 == 2
L9
116
Implementing mod with Java's %
 -a mod n
≠
-a % n
 Make mod's negative argument positive by adding n as
many times as needed:
 e.g. -1 mod 3 == (3 mod 3) + (-1 mod 3)
= (3 -1) mod 3 = (2 mod 3) = 2
 2 mod 3 = 2 % 3 = 2
 e.g. -22 mod 5 == (25 mod 5) + (-22 mod 5)

= (25 – 22) mod 5 = (3 mod 5) = 3
 3 mod 5 = 3 % 5 = 3
Contest Algorithms:12. Maths
117
Simplifying Calculations with mod
 Addition / Subtraction:
 (a + c) mod n = ((a mod n) + (c mod n)) mod n
 (a - c) mod n = ((a mod n) - (c mod n)) mod n
 Multiplication:
 (a * c) mod n = ((a mod n) * (c mod n)) mod n
 Exponentiation
 (am) mod n = (ak mod n) * (a(m-k) mod n)) mod n,
for some 0 ≤ k ≤ m
Contest Algorithms:12. Maths
118
Simplifying multiplications
 10000 mod 997
= (1000*10) mod 997
= ((1000 mod 997) * (10 mod 997)) mod 997
= (3 * 10) mod 997 = 30
 (9835*1177) mod 12
= ((9835 mod 12) * (1177 mod 12)) mod 12
=(7 * 1) mod 12 = 7
Contest Algorithms:12. Maths
119
Simplifying Exponentiation
 2345 mod 31
= (25)69 mod 31
= 3269 mod 31
= (32 mod 31)69 mod 31
= 169 mod 31
= 1 mod 31
=1
Contest Algorithms:12. Maths
see slide 25
120
What are the tens and units digits of 71942?
 It's enough to find the remainder when the number is
divided by 100. In other words, we need 7^1942 mod 100.
 Write down the first few values of 7n mod 100, for n == 1, 2,
3, 4, 5,… looking for a small result, hopefully 1:
 7, 49, 43, 1, 7, …
 so 74 == 2401, and 2401 mod 100 = 1
Contest Algorithms:12. Maths
121
 We know (74 mod 100) == 1
 Also (74k mod 100) == ((74)k mod 100)
= ((74 mod 100)k mod 100) ==(1k mod 100) == 1
 We can write: 71940 = 7(4 X 485) = (74)485
 We know ((74)485 mod 100) == 1
 Note that 71942 = 71940 x 72
 (71942 mod 100)
= ((71940 mod 100) x (72 mod 100)) mod 100)
= ((1 x 49) mod 100) = 49
 The remainder is 49 and so the tens and units digits 4 and 9.
Contest Algorithms:12. Maths
122
Java's % and floorMod()
public static void main(String[] args)
{
System.out.println("% tests:");
System.out.println( 13%2 );
System.out.println( 29%5 );
System.out.println( 10000%997 );
System.out.println( -1%3 );
see ModTests.java
//
//
//
//
1
4
30
-1
System.out.println("\nfloorMod tests:");
System.out.println( Math.floorMod(13,2) ); // 1
System.out.println( Math.floorMod(29,5) ); // 4
System.out.println( Math.floorMod(10000,997) );
// 30
System.out.println( Math.floorMod(-1,3) ); // 2 (same as mod)
} // end of main()
Contest Algorithms:12. Maths
123
Congruences ≡
 a ≡ b (mod m)
 A congruence means that a is equivalent to b
modulo m.
 1:00 and and 13:00 hours are the same
 13  1 (mod 12)
 1:00 and and 25:00 hours are the same
 25  1 (mod 12)
124
Congruence Class Example
15  8  1 (mod 7)
 Congruence Classes of the integers modulo 7
Modular Arithmetic Summary
Modulus function
Congruence relation
r = a mod n
a  r (mod n)
Output of a mod n is the remainder of
an (a value between 0 and b –1)
Relates two numbers a, r to each other
relative some base n
= means that integer r is the remainder
of the division of integer a by integer n
 indicates that the integers a and r fall
into the same congruence class modulo
n (same remainder when divided by n)
2 = 14 mod 3
14  2 (mod 3)
Fermat's Little Theorem
 If p is prime, then for any integer a, ap mod p = a
A corollary is:
 If p is prime and integer a is not divisible by p,
then ap−1 mod p = 1
which can be written using gcd():
 If p is prime and gcd(a, p) = 1, then ap-1 mod p = 1
127
Example Using the Theorem
gcd(6, 31) == 1
 636 mod 31
= (630 * 66) mod 31
= ((630 mod 31) * (66 mod 31)) mod 31
= (1 * (66 mod 31)) mod 31
= (62 * 62 * 62) mod 31
= ((62 mod 31) * (62 mod 31) * (62 mod 31)) mod 31
= (5 * 5 * 5) mod 31
= 125 mod 31
=1
Contest Algorithms:12. Maths
128
Example: calculate 12347865435 mod 11
 Look for powers of 1234k mod 11, which give a small
result, hopefully 1
 1234 mod 11 = 2
 so 12347865435 mod 11 == (1234 mod 11)7865435 mod 11
 = 2 7865435 mod 11
 Look for powers of 2k mod 11, which give a small
result, hopefully 1
 210 mod 11 = 1 (according to Fermat's theorem)
Contest Algorithms:12. Maths
a ==2, p == 11, which are prime
and gcd(2, 11) == 1
129
 210 mod 11 = 1 (according to theorem)
 2 7865435 mod 11 = 2(786543x10)+5 mod 11
= (210)786543 x 25 mod 11
= (210 mod 11)786543 x 25 mod 11
= 1786543 x 25 mod 11
= 25 mod 11 = 32 mod 11 = 10
 So 12347865435 mod 11 = 10
Contest Algorithms:12. Maths
130
More Probable Prime Testing
 Fermat's little theorem can be used as the basis for
another probable prime test
 see FermatPrimeTest.java
 But the Miller-Rabin test is built into BigInteger, and
mathematically better as well
Contest Algorithms:12. Maths
131
Euler's Totient Function
 (N) = how many numbers between 1 and N - 1 which are
relatively prime to N
 Examples:
 (4) = 2
 (5) = 4
 (6) = 2
 (7) = 6
 (8) = 4
 (9) = 6
(1 and 3 are relatively prime to 4)
(1, 2, 3, and 4 are relatively prime to 5)
(1 and 5 are relatively prime to 6)
(1, 2, 3, 4, 5, and 6 are relatively prime to 7)
(1, 3, 5, and 7 are relatively prime to 8)
(1, 2, 4, 5, 7, and 8 are relatively prime to 9)
Note that (N) = N-1
when N is prime
 This function has been examined in great detail for
centuries!
 https://en.wikipedia.org/wiki/Euler%27s_totient_function
 There are many, many ways to generate it. One easy way
for programming is by using gcd(a,b) == 1 to test for
relative primeness:
Contest Algorithms:12. Maths
133
Code
see Totient.java
public static BigInteger totient(BigInteger n)
// also known as Euler's phi function
// see alternative primes-based soln in Primes.java
{
BigInteger phi = new BigInteger("1");
// phi = 1
BigInteger i = new BigInteger("2");
while (i.compareTo(n) < 0) {
// while (i <= n-1)
if ((i.gcd(n)).equals(BigInteger.ONE))
//if gcd(i,n)==1
phi = phi.add(BigInteger.ONE);
// phi++
i = i.add(BigInteger.ONE);
// i++
}
return phi;
} // end of totient()
Contest Algorithms:12. Maths
134
Execution
public static void main(String[] args)
{
BigInteger n = new BigInteger("20");
BigInteger i = new BigInteger("1");
while (i.compareTo(n) <= 0) {
System.out.println("totient(" + i + ") = " +
totient(i));
i = i.add(BigInteger.ONE);
}
}
Contest Algorithms:12. Maths
135
http://primefan.tripod.com/Phi500.html
Totient Values 1-20
n
(n)
Divisors
n
(n)
Divisors
1
1
1
11
10
1, 11
2
1
1, 2
12
4
1, 2, 3, 4, 6, 12
3
2
1, 3
13
12
1, 13
4
2
1, 2, 4
14
6
1, 2, 7, 14
5
4
1, 5
15
8
1, 3, 5, 15
6
2
1, 2, 3, 6
16
8
1, 2, 4, 8, 16
7
6
1, 7
17
16
1, 17
8
4
1, 2, 4, 8
18
6
1, 2, 3, 6, 9, 18
9
6
1, 3, 9
19
18
1, 19
10
4
1, 2, 5, 10
20
8
1, 2, 4, 5, 10, 20
Contest Algorithms:12. Maths
136
Totient and Primes
 Note that (N) = N-1 when N is prime
 (N) is also easy to calculate when N is a multiple of two different
prime factors, p and q:
(p*q) = (p-1)*(q-1)
e.g.
(37) = 36
(21) = (3*7) = (3 - 1)×(7 - 1) = 2×6 = 12
Euler's Theorem
One of the important parts
of the RSA algorithm
 a(n) mod n = 1 if gcd(n, a)=1 and n > a
 a generalisation of Fermat's Theorem
 useful for finding ways of reducing powers+mod to 1
 E.g.
 34 mod 10 = 1
since a=3; n=10; (10)=4; gcd(10,3) = 1
 210 mod 11 = 1
since a=2; n=11; (11)=10; gcd(11,2) = 1
138
GCD-related Mod functions
see GCDTests.java
 modInv(a, n)
 return b such that ab mod n == 1
 modSolve(a, b, n)
 return all x solutions to ax mod n == b
 Chinese remainder theorem: crt(m, a, n, b)
 return z such that z mod m == a and z mod n == b
Contest Algorithms:12. Maths
139
10. Complex Numbers
see Complex.java
 Create Complex objects, add, subtract, multiply, division,
reciprocal, exp(), sin(), cos(), tan(), etc.
 Not a collection of
static methods.
Contest Algorithms:12. Maths
140
11. Assorted Math Functions
 Collection of static functions,
including linear regression, root
finding, integration.
see MathFun.java
boolean isPerfect(long num)
boolean isArmstrong(long num)
double log(double base, double x)
double sigmod(double x)
double invSigmod(double sig)
double horner(double x, double[] p)
void linearRegression(double[] xs,
double[] ys)
double bisection(Function f,
double a, double b)
double simpson(Function f,
double a, double b)
double gamma(double x)
Contest Algorithms:12. Maths
141
public static void main(String[] args)
{
System.out.println("isPerfect(6): " + isPerfect(6));
// true
System.out.println("isArmstrong(371): " + isArmstrong(371));
// true
System.out.println("\nlog3(81): " + log(3, 81));
// 4
double sig = sigmod(5);
System.out.println("\nsigmod(5): " + sig);
System.out.println("invSigmod(): " + invSigmod(sig));
// 5
double[] poly = {1, 1, 1, 1};
// 1 + x + x^2 + x^3
System.out.println("\nHorner of 2 on geom series: " + horner(2, poly));
// 15
// almost straight line y = 2*x + 3
double[] xs = { 1, 2, 3, 4, 5};
double[] ys = { 4.8, 7.2, 9.1, 10.9, 13.2};
linearRegression(xs, ys);
:
Contest Algorithms:12. Maths
142
Function f1 = new Function() {
public double eval(double x)
{ return x*x - 4; }
};
System.out.println("bisection on f1: " + bisection(f1, -1000, 1000));
// roots are -2, 2
System.out.println("\nsimpson on f1, interval 1-3: " + simpson(f1, 1, 3));
// integration == [ x^3/3 - 4x] from 1 to 3 == 2/3
System.out.println("\ngamma(5): " + gamma(5));
} // end of main()
Contest Algorithms:12. Maths
// about 4! = 24
143
Execution
Contest Algorithms:12. Maths
144
see StatsFun.java
12. Assorted Statistical Functions
 A collection of static functions,
including mean, variance,
standard deviation, covariance.
double mean(double[] a)
double var(double[] a)
double varp(double[] a)
double stddev(double[] a)
double stddevp(double[] a)
double stderr(double[] v)
double covar(double[] v1, double[] v2)
double correlation(double[] v1,
double[] v2)
double max(double[] a)
double min(double[] a)
double sum(double[] a)
Contest Algorithms:12. Maths
145
public static void main(String[] args)
{
double[] a = new double[] { 3.0, 1.0, 2.0, 5.0, 4.0 };
double[] b = new double[] { 3.0, 1.0, 2.4, 4.7, 4.0 };
System.out.printf("mean: %.3f\n", mean(a));
System.out.printf("stddev: %.3f\n", stddev(a));
System.out.printf("var: %.3f\n", var(a));
System.out.printf("stderr: %.3f\n", stderr(a));
System.out.printf("stddevp: %.3f\n", stddevp(a));
System.out.printf("varp: %.3f\n", varp(a));
System.out.println();
System.out.printf("min: %f\n", min(a));
System.out.printf("max: %f\n", max(a));
System.out.printf("sum: %f\n", sum(a));
System.out.println();
System.out.printf("covar of a and b: %.3f\n", covar(a,b));
System.out.printf("correlation: %.3f\n", correlation(a,b));
} // end of main()
Contest Algorithms:12. Maths
146