|fibonacci||nth fibonacci number|
|make_cyclic||create a cyclic number from 1/prime in given base|
|cyclic_length||length of cyclic number from 1/prime in given base, 0 if acyclic|
|is_pow||checks if guess is a power of base|
|is_square||checks if number is a perfect square|
|gcd||greatest common denominator (binary)|
|gcd_euclidean||Euclidean algorithm for gcd|
|gcd_alt||Another way for expressing the Euclidean algorithm|
|totient||number of integers less than n that is relatively prime with n|
|mul||matrix chain multiplication ordering|
|factorize||prime factorization of smooth numbers|
|factorize_rough||prime factorization of numbers with large prime factors|
|num_factors||total number of factors (including composites)|
|sum_factors||sum of all factors (including composites)|
The general approach is to exponentiate by squaring the base and
reducing the exponent to at most half each time. This gurantees completion
Some more examples here.
|n||nth fibonacci number, sequence starting: (n=0)0, 1, 1..|
Since exponentiation can be done in
expanding out clever matrices also shares that time complexity.
Because the fibonacci sequence can be defined recursively as a linear
combination of previous terms, such a matrix exists (the companion matrix), and is:
Cyclic numbers ¶
|prime||prime that does not divide base|
Cyclic numbers are related to repeating decimals, from which they can be generated in a given base b with prime p using the relation
They can be constructed by computing the digits of
1/p in base b
by long division and collecting the digits.
Integer power ¶
Through divisions, checks whether guess is an integer power of base.
Perfect square ¶
Used in tight loops of many number theory problems. Algorithm is written by maartinus from stackoverflow.
Greatest Common Denominator ¶
|a||integer (can be negative)|
|b||integer (can be negative)|
Often used to solve combination problems. The binary optimization is used because gcd's common usage in time critical operations. The alternative versions are much simpler and easier to memorize.
Euler's Totient ¶
|n||number to find the totient of|
Number of positive integers less than n that is relatively prime to n.
1 < k < n such that gcd(k,n) == 1
It is multiplicative, so
phi(a*b) == phi(a) * phi(b)
One application is in Euler's theorem: that a and n are relatively prime iff
With applications here.
Matrix Chain Multiplication ¶
Θ(n^3) work is done optimally parenthesize the multiplications using dynamic programming.
This order affects the number of operations required; using Wikipedia's example:
suppose A is a 10 × 30 matrix, B is a 30 × 5 matrix, and C is a 5 × 60 matrix. Then,
(AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations
A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.
Integer Factorization ¶
Factorizing in polynomial time is still an open problem.
Smooth numbers are ones that have small prime factors, while rough numbers factor into large primes. Trial division is used to factorize both, with the difference being the divisor sequence for smooth numbers being that of odd numbers (2, 3, 5, 7, 9,...), while rough numbers is that of generated primes (2, 3, 5, 7, 11,...). Trial division is very fast for practical encounters.