Ex BibliothecaThe life and times of Zack Weinberg.
Monday, 2 August 2004# 3:35 PMmath problem, solvedLet's restate the problem; the form I showed last time doesn't bear an obvious relation to the problem I actually wanted to solve. Given constants P and S (both of which are powers of two) we want to find all positive integers K (also a power of two) and N (not necessarily a power of two) which satisfy the equation
Let's make explicit which constants are powers of two.
where
Factoring out N,
Written this way, it is obvious that 2p must divide N evenly (since it cannot divide 2s + 1, and the right-hand side must be an integer). Let N = 2p ⋅ r. Then
All powers of two are even, so all values of r must cancel the 1 on the right-hand side. The simplest expression for r that does so is r = 2s - 1.
The second and subsequent terms on the right-hand side cancel, leaving us with
corresponding to N = 2p(2s - 1) = P (S - 1). This is the basis of a family of solutions of the form
where i = 0, 1, 2, 3, … Demonstrating that these solutions all work is a straightforward exercise in algebra. Obviously the i = 0 case (N = P (S - 1)) is the smallest. I have not been able to prove that this is the smallest possible solution, or that there are no solutions outside the above family. However, for the two cases I am specifically interested in - P = 4, S = 16; P = 8, S = 32 - I've enumerated values of the right-hand side of the original equation, for all values of N up to the predicted smallest solution, and found that it is indeed the smallest. Thanks in chronological order to Nathaniel Smith, Dan Berlin,
Tkil, and V.
A practical application of this is hoped to be coming soon
to a GCC near you. |