Teaser 2183: The punishment fits the crime
From The Sunday Times, 18th July 2004 [link]
Recently I was teaching the class about Pascal’s triangle, which starts:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1Subsequent rows have a 1 at each end of each row, with any other number in the row obtained by adding the two numbers diagonally above it. Then a row gives, for example:
(1 + x)⁴ = 1 + 4x + 6x² + 4x³ + x⁴
Six pupils disrupted the lesson, and so I kept them in after school. I gave each of them a different prime number and told them to work out its 10th power without a calculator.
“That’s too easy”, said Blaise, whose prime was 3. “I’ll work out the product of everyone else’s answers instead”. Then she read out the 41-digit answer and left!
What was her 41-digit answer?
[teaser2183]
GeoffR and 
Frits, and 
Hugo are discussing. 
S2T2 
Jim Randell 10:34 am on 25 May 2023 Permalink |
In order for the 10th power to be a 41 digit number the product of the 5 primes must be in the range:
Excluding 3, the five smallest primes are (2, 5, 7, 11, 13) which have a product of 10010, which is in the range we require.
And:
We can calculate this number using Pascal’s Triangle as follows:
And row 10 (numbering from 0) of Pascal’s triangle is:
So we can calculate (1000 + 1)^10, using the polynomial derived from this row with x = 1000).
The terms are separated by 1000, and each value in the row is 3 digits or less, so we can just write the result out by padding the values in the row to 3 digits:
Multiplying this by 10^10 just involves adding 10 zeros to the end, to give the 41 digit number:
Or using Python.
The following Python program runs in 57ms. (Internal runtime is 228µs).
Run: [ @replit ]
from enigma import (intc, intf, fdiv, primes, inf, subsets, diff, multiply, ndigits, printf) def solve(n, k): # min and max products for an n digit number m = intc(pow(10, fdiv(n - 1, k))) M = intf(pow(10, fdiv(n, k))) printf("[n={n} -> [{m}, {M}]]") # consider the largest prime for p in primes.irange(2, inf): if p == 3: continue # choose 4 smaller primes (excluding 3) f = 0 for ps in subsets(diff(primes.between(2, p - 1), [3]), size=4, fn=list): ps.append(p) x = multiply(ps) if x > M: if f == 0: return break if not (x < m or x > M): x10 = pow(x, 10) printf("{ps} -> {x} -> {x10} [{d} digits]", d=ndigits(x10)) f = 1 # solve for 41 digit numbers solve(41, 10)LikeLike
GeoffR 4:45 pm on 26 May 2023 Permalink |
primes = (2, 5, 7, 11, 13, 17, 19) # prime 3 excluded from description # The highest product of primes to power of 10 in the tuple below # .. i.e. (7,11,13,17,19) gives a 56 digit number # .. so a more than an adequate range to find a 41 digit product. from itertools import combinations for P1 in combinations(primes, 5): # choose 5 primes from a tuple of 7 primes p1, p2, p3, p4, p5 = P1 num = p1**10 * p2**10 * p3**10 * p4**10 * p5**10 if len(str(num)) == 41: print(f"41 digit number is {num}") exit() # only one answer needed # 41 digit number is 10100451202102522101200450100010000000000LikeLike