hw1

Documentation

Index

• func Comb(n int, k int) int
• func CombDumb(n int, k int) int
• func CrossOffMultiples(primeArray []int, p int) []int
• func Fact(n int) int
• func FactArray(n int) []int
• func FibArray(n int) []int
• func FindPerfect(n int) []int
• func GCDArray(nums []int) int
• func IsPerfect(n int) bool
• func IsPerfect1(n int) bool
• func IsPerfect2(n int) (bool, []int)
• func Perm(n int, k int) int
• func PermDumb(n int, k int) int
• func PrimeFactors(n int) []int
• func PrimeFactors2(n int) []int
• func SieveOfEratosthenes(n int) []int
• func SumOfFactors(origN int) int
• func TrivialGcd(a, b int) int

Functions

func Comb

func Comb(n int, k int) int

Comb calculates the combination statistic C(n,k) - represents the number of ways to choose k items from a list of n items, when the

   ordering does not matter
- This can also be written as C(n,k) = n!/(n-k!)*k!
- Or P(n,k)/k!
- This can be expanded to (n/1*(n-1)/2*(n-2)/3*...*(n-k+1)/k) While it may look like
  remainders can result, as long as you perform the calculations strict;y from left to
  to right, it actually works, with no remainders at any time.
- See https://www.calculatorsoup.com/calculators/discretemathematics/combinations.php
  for an online combinations calculator to check results
- for hints on how to efficiently implement C(n,k) see:
	- https://www.mathbootcamps.com/counting-with-combinations/
  - https://en.wikipedia.org/wiki/Combination

func CombDumb

func CombDumb(n int, k int) int

CombDumb is a naive implementation to calculate the Permutation statistic. It will fail when n is greater than about 20, as fact(n) will overflow a 64 bit int

func CrossOffMultiples

func CrossOffMultiples(primeArray []int, p int) []int

CrossOffMultiples takes a boolean slice and an integer p. It crosses off multiples of p, meaning turning these multiples to false in the slice. It returns the slice obtained as a result.

func Fact

func Fact(n int) int

Fact calculates the factorial of an int There are 2 big issues:

• the result grows quickly, and will soon overflow a 64 bit int at about n=20. One can solve this by using bignums in the package math/big
• Go does not implement tail recursion, so each recursive call uses a stack frame. If the recursion is very deep, we can run out of stack space. The solution is to use a for loop to replace the recursion

func FactArray

func FactArray(n int) []int

FactArray makes an array of a sequence of n factorials

func FibArray

func FibArray(n int) []int

FibArray makes an array of a sequence of n Fibonacci numbers

func FindPerfect

func FindPerfect(n int) []int

FindPerfect finds all perfect numbers up to some bound n. It returns a slice of the perfect numbers found Note that ISPerfect creates an array of length sqrt(n), so space as well as time will be a problem when n grows FindPerfect assumes perfect numbers are always even.

func GCDArray

func GCDArray(nums []int) int

GCDArray finds the GCD of slice of ints.

func IsPerfect

func IsPerfect(n int) bool

IsPerfect based on John Cox's geometric progression algorithm

func IsPerfect1

func IsPerfect1(n int) bool

IsPerfect1 JiPi's Version from discussion board (JiPi and Henk Westerink)

func IsPerfect2

func IsPerfect2(n int) (bool, []int)

IsPerfect2 takes an integer n, and returns true if it is a perfect number. It also returns []int slice with all the factors of n Is Perfect uses a modified trial division algorithm to factorize the input, which is the most inefficient way of factoring. Some optimizations:

• We only test to sqrt(n), and then when we find a factor we also add n/factor as a second factor
• If a number does not divide n, we also know that all multiples of that number won't divide it either. so we keep a slice of "notDivisibleby" values, and check against them before we do the trial division

func Perm

func Perm(n int, k int) int

Perm calculates the Permutation statistic P(n,k) - represents the number of ways to choose k items from a list of n items, when the

   ordering matters
- It is equal to the product: n*(n-1)*(n-2)*...*(n-k+1)
- This can also be written as P(n,k) = n!/(n-k!)
- See https://www.calculatorsoup.com/calculators/discretemathematics/permutations.php
  for an online perutations calculator to check results

This implementation calculates n*(n-1)*(n-2)*...*(n-k+1) to minimise issues with integer overflow

func PermDumb

func PermDumb(n int, k int) int

PermDumb is a naive implementation to calculate the Permutation statistic. It will fail when n is greatr than about 20, as fact(n) will overflow a 64 bit int

func PrimeFactors

func PrimeFactors(n int) []int

PrimeFactors returns all the prime factors of n

func PrimeFactors2

func PrimeFactors2(n int) []int

PrimeFactors2 uses simple trial division

func SieveOfEratosthenes

func SieveOfEratosthenes(n int) []int

SieveOfEratosthenes takes an integer n and returns a slice of n+1 ints primeArray where primeArray[p] is 0 if p is prime and holds the lowest primer divisor of p if it is not It implements the Sieve of Eratosthenes approach.

func SumOfFactors

func SumOfFactors(origN int) int

SumOfFactors John D Cox's algorithm to compute the sum o factors computes sum by using geometric progression. The final sum will also include the number N as a factor so that needs to be subtracted before returning

func TrivialGcd

func TrivialGcd(a, b int) int

TrivialGcd find the GCD of two ints in a very inefficient way