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? Not that I'm claiming this helps to calculate A027424(N). -A
--- "Allan C. Wechsler" <acw@alum.mit.edu> 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?
Not that I'm claiming this helps to calculate A027424(N).
-A
No. 8 does not appear in the 3x3 multiplication table. __________________________________ Do you Yahoo!? SBC Yahoo! DSL - Now only $29.95 per month! http://sbc.yahoo.com
At 05:11 PM 7/5/03 -0700, Eugene Salamin wrote:
--- "Allan C. Wechsler" <acw@alum.mit.edu> 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? No. 8 does not appear in the 3x3 multiplication table.
Oh. Darn. Well, so much for that idea. -A
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.
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
On Sun, Jul 06, 2003 at 02:09:27PM -0400, William Thurston wrote:
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.
Oh, nice. Yes, that should be right. Explicitly, if d_1, ... d_k are the prime factors of N (with multiplicity), you're trying to divide log d_1, ..., log d_k into two sets, each with sum less than log L (where L is the side length of the table). By picking the d_i appropriately, you can get this to be close to any givn instance of the knapsack problem, which is NP complete; the remaining issue is whether you can do this without making the d_i too large (thus ruining the NP-completeness). The right measure of complexity here is log N or the sum of log d_i. Peace, Dylan
On Friday, July 11, 2003, at 03:44 PM, Dylan Thurston wrote:
On Sun, Jul 06, 2003 at 02:09:27PM -0400, William Thurston wrote:
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.
Oh, nice. Yes, that should be right. Explicitly, if d_1, ... d_k are the prime factors of N (with multiplicity), you're trying to divide log d_1, ..., log d_k into two sets, each with sum less than log L (where L is the side length of the table). By picking the d_i appropriately, you can get this to be close to any givn instance of the knapsack problem, which is NP complete; the remaining issue is whether you can do this without making the d_i too large (thus ruining the NP-completeness). The right measure of complexity here is log N or the sum of log d_i.
Sure, but that doesn't mean that the original problem has to be hard. First of all, the values of N that were bothering David Wilson in the first place were something like a million -- log N is just not that big; we can do a relevant knapsack problem by exhaustion, we just can't do it O(N) times. Second, we just want to know the total number of entries in the NxN mult table, not even test whether any particular number appears or not. And even if answering this led to a knapsack-like solution for some specific number near N, that's fine, by the first point. --Michael Kleber kleber@brandeis.edu
participants (6)
-
Allan C. Wechsler -
Dylan Thurston -
Edwin Clark -
Eugene Salamin -
Michael Kleber -
William Thurston