Ex Bibliotheca

The life and times of Zack Weinberg.

Monday, 2 August 2004

# 3:35 PM

math problem, solved

Let'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

K = SN + N + P

Let's make explicit which constants are powers of two.

2^k = 2^sN + N + 2^p

where

k = log₂ K
s = log₂ S
p = log₂ P

Factoring out N,

2^k = N(2^s + 1) + 2^p
2^k-p = N(2^s + 1)/2^p + 1

Written this way, it is obvious that 2^p must divide N evenly (since it cannot divide 2^s + 1, and the right-hand side must be an integer). Let N = 2^p ⋅ r. Then

2^k-p = r (2^s + 1) + 1

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 = 2^s - 1.

2^k-p = (2^s - 1)(2^s + 1) + 1
2^k-p = 2^2s - 2^s + 2^s - 1 + 1

The second and subsequent terms on the right-hand side cancel, leaving us with

2^k-p = 2^2s
k - p = 2s
k = 2s + p

corresponding to N = 2^p(2^s - 1) = P (S - 1). This is the basis of a family of solutions of the form

N = (2^s - 1) ∏_i (2^{s ⋅ 2i} + 1)
k = 2ⁱ⁺¹s + p

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.