Quant puzzles, solved step by step

Puzzles: 100
Traced to a firm: 71
Topics: 12
Hard: 30

Showing 1–3 of 3 · filtered from 100Clear filters

049Which is larger, e to the power pi or pi to the power e? Prove it without a calculator.Mental maths and number senseCoreQuant researchQuant trading
Try it first
Which way does it go?
Show the worked solution
e^pi is larger: about 23.14 against 22.46 for pi^e. Take logs of both and divide by e x pi, which turns the question into comparing ln e / e with ln pi / pi. The function ln x / x rises up to x = e and falls after it, so its value at e beats its value at any other number, pi included. Undo the steps and the order holds.
How do you turn two awkward powers into one comparison?
When two people race on different tracks, you compare them by converting to the same distance. Here the base and the exponent both differ, so convert each number into a common form. Take logarithms and divide by e x pi: e^pi against pi^e becomes ln e / e against ln pi / pi, the same function evaluated at two points. Logs and division by a positive number both preserve order, so whichever side wins the new comparison wins the original.
The relationship
$e^{\pi} \; ? \; \pi^{e} \iff \pi \ln e \; ? \; e \ln \pi \iff \frac{\ln e}{e} \; ? \; \frac{\ln \pi}{\pi}$
? the unknown direction of the inequality, the same at every step
\ln x / x the function whose largest value settles the question
What it says in wordsTaking logs and dividing by e times pi turns the question into one function compared at e and at pi.
Why is ln x / x largest at e?
Differentiate: the derivative of ln x / x is (1 - ln x) / x squared. It is positive while ln x is below 1 and negative once ln x passes 1, so the function climbs until x = e and falls after. Its largest value, 1/e, occurs only at x = e, so ln pi / pi must be smaller, and therefore e^pi beats pi^e. Equivalently, x^(1/x) peaks at e with value 1.4447, while pi^(1/pi) is 1.4396.
The curve x to the power 1/x reaches its maximum of 1.4447 at x = e and has already fallen to 1.4396 at x = pi, so raising both values to the power e times pi gives e^pi = 23.14, larger than pi^e = 22.46.
There is a second proof that needs no calculus beyond one inequality. For any x other than zero, e^x is greater than 1 + x, because the exponential curve lies above its tangent line at zero. Put x = pi/e - 1, about 0.156: then e^(pi/e - 1) is greater than pi/e, so e^(pi/e) is greater than pi, and raising both to the power e gives e^pi greater than pi^e. Give that one if the interviewer asks for a proof without derivatives.
Notice how close the race is: the two values of x^(1/x) differ by only 0.0050, because pi sits near the flat top of the curve. That is why rough estimation is risky here and a proof is needed: 23.14 and 22.46 differ by about 3%. The same argument settles a whole family: for any two numbers a and b with e at most a, and a less than b, a^b is greater than b^a, which is why 3^4 = 81 beats 4^3 = 64.
Where candidates lose it
The common loss is answering pi^e because pi is the bigger base, or trying to estimate both numbers to a decimal and getting lost in the arithmetic. The gap is only about 3%, so mental estimates can land either way.
The second is proving it backwards: assuming the answer and manipulating until something true appears, without checking each step preserves the inequality. Say out loud that taking logs and dividing by the positive e x pi keep the order.
What the interviewer asks next
Which is larger, 2^3 or 3^2, and why does the argument not apply to 2 and 4?
Find all pairs of distinct positive integers with a^b = b^a.
Which is larger, 99^100 or 100^99?
073Use Newton's method to find the square root of 2, starting from 1.5. How many correct digits do you have after each step, and why?Mental maths and number senseCoreQuant researchDesk quant
Try it first
Starting from 1.5, about how many correct digits after three Newton steps?
Show the worked solution
About 1, 3, 6 and 12 correct digits: the count roughly doubles each step. The update is x(next) = (x + 2/x)/2: 1.5 gives 17/12 = 1.41667, then 577/408 = 1.4142157, then 665857/470832 = 1.41421356237469. Each new error is about the old error squared divided by 2x, so if the error is 10^-k, the next is about 10^-2k. That is quadratic convergence.
Where does the update rule come from?
Think of guessing a side of a square room whose area is 2. If your guess is too big, 2 divided by your guess is too small, and the truth sits between the two. Newton's method for x squared minus 2 is exactly that: replace x with the average of x and 2/x. Formally, Newton follows the tangent of f(x) = x^2 - 2 down to zero, x - f(x)/f'(x) = x - (x^2 - 2)/(2x), which simplifies to (x + 2/x)/2. The averaging form is the one to use in your head.
Starting from 1.5, Newton's iterates for the square root of 2 have 1, 3, 6 and then 12 correct digits, doubling at each step because each new error is roughly the square of the old one.
How do you get the iterates without a calculator?
Keep fractions. From 3/2, the next value is (3/2 + 4/3)/2 = 17/12, then (17/12 + 24/17)/2 = 577/408, and the pattern continues: if x = p/q, the next is (p^2 + 2q^2)/(2pq). 17/12 is 1.41667, already right to 1.41. 577/408 is 1.4142157 against 1.4142136, right to 1.41421. The third step's fraction, 665857/470832, is too big for mental division, but you can predict its accuracy without doing it, which is the point of the question.
The relationship
$x_{n+1} = \tfrac12\Big(x_n + \frac{2}{x_n}\Big) \qquad x_{n+1} - \sqrt2 = \frac{(x_n - \sqrt2)^2}{2x_n}$
x_n the current estimate of the square root of 2
x_n - sqrt 2 the error of the current estimate
2 x_n about 2.8 near the root, so the new error is about a third of the old error squared
What it says in wordsEach new error is the old error squared, divided by about 2.8, so the correct digits roughly double.
Why is it the digits that double, and when does that fail?
Subtract the root from the update and the algebra collapses to (x - root 2)^2 / 2x. Squaring an error of 10^-3 gives 10^-6, so each step doubles the number of correct digits once you are close. The errors here run about 0.09, 0.0025, 2 x 10^-6 and 1.6 x 10^-12. The doubling needs a good start and a simple root: far from the root, or where the slope is zero, Newton can creep or jump away. Bisection, by contrast, gains one binary digit per step whatever happens, which is why desk code often brackets with bisection and finishes with Newton when solving for implied volatility.
Where candidates lose it
The trap is guessing linear progress, one or two digits a step, because that is how most iterative methods feel. Newton is special near a simple root, and the interviewer wants the word quadratic and the reason for it.
The second loss is getting lost in decimals. Work in fractions, 3/2, 17/12, 577/408, and state the error-squared rule instead of computing the third step.
What the interviewer asks next
Write Newton's update for the cube root of 10, and start it from 2.
Why does Newton converge only linearly at a double root?
How would you use Newton's method to find an implied volatility, and what can go wrong?
097How many integers from 1 to 1,000 share no common factor with 1,000 other than 1?Mental maths and number senseCoreQuant researchQuant trading
Try it first
Pick the count.
Show the worked solution
400. Since 1,000 = 2^3 x 5^3, a number shares a factor with 1,000 exactly when it is divisible by 2 or by 5. There are 500 multiples of 2 and 200 of 5, but the 100 multiples of 10 sit in both lists, so 600 numbers share a factor and 400 do not. Euler's formula agrees: 1,000 x 1/2 x 4/5 = 400.
Which numbers share a factor with 1,000?
Picture a hall of 1,000 people where everyone wearing a red badge or a blue badge is asked to leave. To count who stays, you need the red-badge count, the blue-badge count, and how many wear both, because they would otherwise be counted out twice. Write 1,000 as 2^3 x 5^3: a number shares a factor with it exactly when it is divisible by 2 or by 5, so only two badges matter, and the powers 3 do not add any new conditions. Every multiple of 4 or 8 is already a multiple of 2, and every multiple of 25 or 125 is already a multiple of 5.
Of the numbers 1 to 1,000, 500 are multiples of 2 and 200 are multiples of 5, with 100 multiples of 10 in both, so 600 share a factor with 1,000 and 400 lie outside both circles; Euler's product 1,000 x 1/2 x 4/5 gives the same 400.
The relationship
$\varphi(1000) = 1000 - \left\lfloor\tfrac{1000}{2}\right\rfloor - \left\lfloor\tfrac{1000}{5}\right\rfloor + \left\lfloor\tfrac{1000}{10}\right\rfloor = 1000\left(1-\tfrac12\right)\left(1-\tfrac15\right) = 400$
phi(1000) Euler's totient: how many of 1 to 1,000 share no factor with 1,000
1000/2, 1000/5 the counts of multiples of 2 and of 5
1000/10 the multiples of both, added back once
What it says in wordsRemove the multiples of each prime, add back the multiples of both, and you get the same answer as multiplying by the share that survives each prime.
Why does the quick product formula work here?
Half of all numbers are odd, and among those, four in five are not multiples of 5. Because 1,000 is a multiple of 10, the numbers 1 to 1,000 contain exactly 100 full blocks of ten, and in each block exactly 4 numbers, 1, 3, 7 and 9, survive both tests, so 100 x 4 = 400. The strip of 1 to 20 in the figure shows the pattern repeating, 8 survivors in 20. The product is exact only when the range is a whole number of such blocks: for 1 to 1,234 it gives 493.6, while a direct count gives 494.
Where does a question like this lead in an interview?
Usually to powers and remainders. Euler's theorem says a number coprime to n, raised to the power phi(n), leaves remainder 1 when divided by n, and that is the engine behind last-digit puzzles: phi(100) = 40, so 3^40 ends in 01 and so does 3^400. It also leads to probability: the chance that two large random integers share no factor tends to 6/pi^2, about 0.608. The habit the question tests is factorising first: once you see only the primes 2 and 5 matter, a counting question becomes a two-circle Venn diagram.
Where candidates lose it
The usual slip is 1,000 - 500 - 200 = 300, subtracting both lists and forgetting that the multiples of 10 were removed twice. Add them back once and the answer is 400.
The second loss is treating each prime power as a new condition, subtracting multiples of 4, 8, 25 and 125 as well. Every multiple of 4 is already a multiple of 2; only the distinct primes matter.
What the interviewer asks next
How many integers from 1 to 1,000 share no factor with 360?
What are the last two digits of 3^400?
What is the probability that two randomly chosen integers share no common factor?

?	the unknown direction of the inequality, the same at every step
\ln x / x	the function whose largest value settles the question

x_n	the current estimate of the square root of 2
x_n - sqrt 2	the error of the current estimate
2 x_n	about 2.8 near the root, so the new error is about a third of the old error squared

phi(1000)	Euler's totient: how many of 1 to 1,000 share no factor with 1,000
1000/2, 1000/5	the counts of multiples of 2 and of 5
1000/10	the multiples of both, added back once

Try it first

How do you turn two awkward powers into one comparison?

Why is ln x / x largest at e?

Where candidates lose it

What the interviewer asks next

Try it first

Where does the update rule come from?

How do you get the iterates without a calculator?

Why is it the digits that double, and when does that fail?

Where candidates lose it

What the interviewer asks next

Try it first

Which numbers share a factor with 1,000?

Why does the quick product formula work here?

Where does a question like this lead in an interview?

Where candidates lose it

What the interviewer asks next