For those who haven't guessed, A027424(N) is the number of distinct integers in an NxN multiplication table. According to the accompanying text, (info from Pomerance) Erdos showed it's o(N^2), and Linnik & Vinogradov got O(N^2/(logN)^c) for some c>0; and there's a finer result in a 1988 book by Hall & Tenenbaum. An easy lower bound is to consider primes P > N/2, times anything < N. This gives N * (N/2logN) - ((N/2logN)^2)/2, after subtracting double counting of P*P'; or roughly N^2/2logN. I'd expect the large corner of the table, near N, to have mostly unique numbers (except for reflection); this might also give a lower bound. For computing the exact number, you might be able to work out the count of new numbers in row N, from the factorization of N. The work for the factors of each N is small, maybe logN or loglogN. Rich -----Original Message----- From: Allan C. Wechsler [mailto:acw@alum.mit.edu] Sent: Saturday, July 05, 2003 5:09 PM To: math-fun Subject: [math-fun] A027424 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 _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun