6 Jul
2003
6 Jul
'03
12:13 p.m.
On Saturday, July 5, 2003, at 08:27 PM, Edwin Clark wrote:
Is it not the case that a number appears in the N x N multiplication table precisely when none of its prime factors exceed N, and the number itself does not exceed N^2?
If N = 8 then 54 = 9*6 is not in the NxN multiplication table, yet 54 < N^2 and its prime factors are 2 and 3, both < N.
Isn't the problem to determine when an n-digit number appears in a multiplication table of side length roughly its square-root presumably NP-complete? This is a variation of the knapsack problem, trying to distribute a bunch of packages into two bags each of which has total weight less than N. Bill