MATH40006 Practice Paper 4 Solutions

Notes — cell 1

# MATH40006 Revised Historical-Coverage Mock 4 - Course-Method Audited Solutions

**Time allowed:** 60 minutes 
**Total marks:** 50 
**Role:** 2021-23 early historical ability: Legendre quadrature, integer square roots and LCM complexity

The main solutions use methods evidenced in the supplied official papers and mark schemes. No lecture notes or problem sheets were available in this window, so “course-method audited” here means audited against the official answer methods that are actually accessible.

Code — cell 2

import numpy as np
import sympy as sp
import matplotlib.pyplot as plt
import pandas as pd
from time import perf_counter
from copy import copy
import pickle
import ast
import math
sp.init_printing()

def legendre_poly(n,x):
    if n==0:return sp.Integer(1)
    if n==1:return x
    pa,pb=sp.Integer(1),x
    for r in range(2,n+1): pa,pb=pb,sp.together(sp.expand(((2*r-1)*x*pb-(r-1)*pa)/r))
    return pb

def lcm_add(a,b):
    a0,b0=a,b
    while a!=b:
        if a<b:a+=a0
        else:b+=b0
    return a
def lcm_euclid(a,b):
    a0,b0=a,b
    while b>0:a,b=b,a%b
    return a0*b0//a

Notes — cell 3

## Question 1 (20 marks)

**Recognition signal.** A three-term polynomial recurrence, exact symbolic roots and a quadrature formula based on those roots.

**First key step.** Keep the pair `(P_{n-1},P_n)` together; this is also the key to an efficient one-call recursive version.

**Course-method chain.** exact recurrence -> lambdify/plot -> pair-return recursion -> roots/derivative/weights -> affine interval transform and weighted sum.

**Marking points.** 2+3+5+5+5.

**Common errors.** Two recursive calls per level; converting to float too early; using P5 derivative with P4 roots; omitting the interval scaling factor.

**Final self-check.** The quadrature value should agree with `1-exp(-1)` to many digits.

### Historical-basis and difficulty audit

- **Historical formal-question basis:** 2022-23 Assessment 3 Q1(a-f)
- **Accessible course-material basis:** 2022-23 official marking scheme 
- Historical ability gap filled: Legendre recurrence, symbolic-to-numerical conversion, roots and weights, and Gauss quadrature
- **Equivalent 2026 difficulty unit:** 2026 Q1(20 mark highly abstract synthesis difficulty unit )
- Why equivalent: the original 35-mark question is compressed to 20 marks, retaining recurrence, lambdify, roots/weights and one integral; approximately 20 minutes.

Code — cell 4

x=sp.symbols('x')
print([legendre_poly(n,x) for n in range(5)])
p6=legendre_poly(6,x); f6=sp.lambdify(x,p6,'numpy'); xx=np.linspace(-1,1,200)
plt.figure(); plt.plot(xx,f6(xx)); plt.show()
def legendre_recursive(n,x,pair=False):
    if pair:
        if n==1:return sp.Integer(1),x
        pa,pb=legendre_recursive(n-1,x,True)
        return pb,sp.together(sp.expand(((2*n-1)*x*pb-(n-1)*pa)/n))
    if n==0:return sp.Integer(1)
    return legendre_recursive(n,x,True)[1]
print(all(sp.simplify(legendre_poly(n,x)-legendre_recursive(n,x))==0 for n in range(9)))
p4=legendre_poly(4,x); dp4=sp.diff(p4,x); roots=sp.solve(sp.Eq(p4,0),x)
weights=[float(2/((1-r**2)*dp4.subs(x,r)**2)) for r in roots]
vals=[math.exp(-float((r+1)/2)) for r in roots]
approx=0.5*np.dot(weights,vals); exact=1-math.exp(-1)
print(roots); print(weights); print(approx,exact,abs(approx-exact))

[1, x, (3*x**2 - 1)/2, x*(5*x**2 - 3)/2, (35*x**4 - 30*x**2 + 3)/8]

<Figure size 640x480 with 1 Axes>

True

[-sqrt(3/7 - 2*sqrt(30)/35), sqrt(3/7 - 2*sqrt(30)/35), -sqrt(2*sqrt(30)/35 + 3/7), sqrt(2*sqrt(30)/35 + 3/7)]
[0.6521451548625461, 0.6521451548625461, 0.34785484513745385, 0.34785484513745385]
0.6321205584853381 0.6321205588285577 3.4321956388083663e-10

Notes — cell 5

## Question 2 (20 marks)

**Recognition signal.** The integer square root is defined by inequalities, and the question supplies bit-level construction plus discrete Newton iteration.

**First key step.** Derive `smax` from `bit_length`; keep every operation integer-valued.

**Course-method chain.** bit-length identity -> descending even shifts -> invariant tests -> logarithmic iteration argument -> Newton with safe upper start -> cross-check.

**Marking points.** 2+7+3+2+5+1.

**Common errors.** Using floating sqrt; wrong parity for smax; stopping Newton after equality rather than when the update no longer decreases; missing n=0,1.

**Final self-check.** For every n, verify `r*r<=n<(r+1)*(r+1)`.

### Historical-basis and difficulty audit

- **Historical formal-question basis:** 2022-23 Assessment 3 Q3-Q5
- **Accessible course-material basis:** 2022-23 official marking scheme 
- Historical ability gap filled: the two historical method sequences for bitwise integer square roots and discrete Newton iteration
- **Equivalent 2026 difficulty unit:** 2026 Q2(20 mark long-algorithm difficulty unit )
- Why equivalent: both algorithms include tests and counts; slightly more abstract, but the prescribed n=120 hand calculation and complete closed-form proof are omitted; approximately 25 minutes.

Code — cell 6

def isqrt_bitwise(n):
    if n<0: raise ValueError
    if n<2:return n
    r=0; smax=2*((n.bit_length()-1)//2)
    for s in range(smax,-1,-2):
        r<<=1
        if (r+1)**2 <= (n>>s): r+=1
    return r
def isqrt_newton(n):
    if n<0: raise ValueError
    if n<2:return n
    old=1<<(((n.bit_length()-1)//2)+1)
    new=(old+n//old)//2
    while new<old: old,new=new,(new+n//new)//2
    return old
tests=[2,17,10**100+12345,12345**2,12345**2-1,12345**2+1]
for n in tests:
    a=isqrt_bitwise(n); b=isqrt_newton(n)
    print(n if n<100000 else str(n)[:15]+'...',a==b,a*a<=n<(a+1)**2)

2 True True
17 True True
100000000000000... True True
152399025... True True
152399024... True True
152399026... True True

Notes — cell 7

## Question 3 (10 marks)

**Recognition signal.** Two given loops solve the same problem but have very different comparison-count behaviour.

**First key step.** Initialize the count to one so the final failed while test is included.

**Course-method chain.** instrument loops -> edge tests -> enumerate b values -> identify worst inputs -> connect repeated additions to linear growth and Euclid to Fibonacci/logarithmic depth.

**Marking points.** 4+2+2+2.

**Common errors.** Off-by-one counts; changing original a,b before computing the LCM; claiming timing alone proves complexity.

**Final self-check.** Both algorithms must return the same LCM on all tests.

### Historical-basis and difficulty audit

- **Historical formal-question basis:** 2021-22 Assessment 3 Q1(a-h)
- **Accessible course-material basis:** 2021-22 official marking scheme 
- Historical ability gap filled: exact LCM operation counting, worst-input experiments and asymptotic complexity
- **Equivalent 2026 difficulty unit:** 2026 Q3(10 mark short-algorithm difficulty unit )
- Why equivalent: selects the counter, scanning and complexity core of the original 25-mark sequence; four marking stages, approximately 10 minutes.

Code — cell 8

def lcm_add_count(a,b):
    a0,b0=a,b; count=1
    while a!=b:
        if a<b:a+=a0
        else:b+=b0
        count+=1
    return a,count
def lcm_euclid_count(a,b):
    a0,b0=a,b; count=1
    while b>0:a,b,count=b,a%b,count+1
    return a0*b0//a,count
for a,b in [(5,3),(35,21),(35,35),(35,1)]: print(a,b,lcm_add_count(a,b),lcm_euclid_count(a,b))
for fn in [lcm_add_count,lcm_euclid_count]:
    counts=[fn(144,b)[1] for b in range(1,144)]; print(fn.__name__,1+int(np.argmax(counts)),max(counts))

5 3 (15, 7) (15, 4)
35 21 (105, 7) (105, 4)
35 35 (35, 1) (35, 2)
35 1 (35, 35) (35, 2)
lcm_add_count 143 286
lcm_euclid_count 89 11