Python number theory

Enter your answers to these questions in the accompanying Python script file kit103_assign3.py. As in the previous assignment, your answers will be function definitions and the script file already contains function ‘stubs’ that you will complete. Include your name and student ID in the places indicated in the header comment. ∨ Question 1: Divisibility of really, really big integers (2 marks, *) In many programming languages the native integer data types have an upper limit on their maximum value. To test the divisibility of numbers larger than can be represented natively it can be convenient to instead work with strings of digits, as character strings can grow indefinitely. Task: There are incomplete functions in the assignment script file that are intended to test large numbers (defined by strings of the characters ‘0’ through ‘9’) for divisibility by various values. Complete the implementations of these functions by applying the common divisibility rules for 4, 5, 9 and 11 (the functions are named divisible_by_n ∈ {4, 5, 9, 11}). KMA155 students must implement the rules for divisibility by 4, 5 and 9. Hints:  Your functions will be tested with strings, like ‘1234’, not integers such as 1234. These are not equivalent: the first occupies more than 64 bits in memory (4 × 2-byte characters), while the small integer value is likely only 32 bits.  Practical 6 (week 7) contains some similar examples and describes how to access individual characters in a string by index (which may count backwards from the end of the string). String slicing may also be useful in up to two of the above functions.  You might not need to convert any part of the string to a number (but if you’ve applied the common divisibility rules and have reached the point where that makes sense then it’s fine for you to do so). ∨ Question 2: LCM from a prime factorisation (2 marks) Both the math and programming lecture streams have described how to calculate lcm(a, b) using the prime factorisations of a and b. Your task is to q2_factor_lcm(a, b) to implement this behaviour. Counter class to represent a multiset/bag, and make use of the included helper function factor_list to complete the stub function In your solution you should use the Python generate a list of prime factors for each input. ∨ Question 3: Are aa and bb coprime (i.e., relatively prime)? (1 mark, *) q3_coprime(a, b) that is intended to return True if a and b are relatively prime,False otherwise (coprime In the assignment script file there is a stub function is another term for relatively prime, and provides a shorter function name). One indicator that two numbers are coprime is that they do not have any prime factors in common. Complete the implementation ofq3_coprime to perform this test. You will find at least one of the included functions in the script file of use. ∨ Information on string slicing The following information on string slicing (essentially, taking a substring from a string) may be helpful in some parts of Question 1. For a string s: s[start:end] s[start:] s[:end] s[:] # # # # characters start through end-1 characters start through the rest of the string characters from the beginning through end-1 a copy of the whole string And you may optionally include a step value: s[start:end:step] # start through not past end, by step So, for example, s[2::3] copies every third character in s starting with the third character (i.e., position 2) up to the end (because the end position was omitted). ...