|
| |
|
|
A027424
|
|
Number of distinct products ij with 1 <= i, j <= n (number of distinct terms in n X n multiplication table).
|
|
24
|
|
|
|
1, 3, 6, 9, 14, 18, 25, 30, 36, 42, 53, 59, 72, 80, 89, 97, 114, 123, 142, 152, 164, 176, 199, 209, 225, 239, 254, 267, 296, 308, 339, 354, 372, 390, 410, 423, 460, 480, 501, 517, 558, 575, 618, 638, 659, 683, 730, 747, 778, 800, 827, 850, 903
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
As n->infinity what is an asymptotic expression for a(n)? Reply from Carl Pomerance: Erdos showed that a(n) is o(n^2). Linnik and Vinogradov, Vestnik Leningrad Univ. 13 (1960), 41-49 showed it is O(n^2/(log n)^c) for some c > 0. Finer estimations were achieved in the book Divisors by Hall and Tenenbaum (Cambridge, 1988), see Theorem 23 on p. 33.
An easy lower bound is to consider primes p > n/2, times anything < n. This gives n * (n/2 logn) - ((n/2 log n)^2)/2, after subtracting double counting of p*p'; or roughly n^2/2 log n. - Rich Schroeppel, Jul 05 2003
A033677(n) is the smallest k such that n appears in the k X k multiplication table and a(k) is the number of n with A033677(n) <= k.
Erdos showed in 1955 that a(n)=O(n^2/(log n)^c) for some c>0. In 1960, Erdos proved a(n) = n^2/(log n)^(b+o(1)), where b = 1-(1+loglog 2)/log 2 = 0.08607... In 2004, Ford proved a(n) is bounded between two positive constant multiples of n^2/((log n)^b (log log n)^(3/2)). - Kevin Ford (ford(AT)math.uiuc.edu), Apr 20 2006
|
|
|
REFERENCES
|
P. Erdos, Some remarks on number theory, Riveon Lematematika 9 (1955), 45-48 (Hebrew. English summary).
P. Erdos, An asymptotic inequality in the theory of numbers, Vestnik Leningrad. Univ. 15 (1960), 41-49 (Russian).
|
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n = 1..1000
K. Ford (2008) The distribution of integers with a divisor in a given interval. Annals of Math. 168(2), 367-433. arXiv:math/0401223
D. Koukoulopoulos, On the number of integers in a generalized multiplication table. Journal für die reine und angewandte Mathematik, 2012.
C. Pomerance (1998) Paul Erdos, Number Theorist Extraordinaire, Notices Amer. Math. Soc. 45(1), 19-23.
|
|
|
FORMULA
|
a(n) = sum_{l=1}^{n^2} sum_{d|l} moebius(l/d) * floor( m(d,n) * n / l ), where m(d,n) is the maximum divisor of d not exceeding n. - Max Alekseyev, Jul 14 2011
|
|
|
MATHEMATICA
|
u = {}; Table[u = Union[u, n*Range[n]]; Length[u], {n, 100}] (* T. D. Noe, Jan 07 2012 *)
|
|
|
PROG
|
(PARI) multab(N)=local(v, cv, s, t); v=vector(N); cv=vector(N*N); v[1]=cv[1]=1; for(k=2, N, s=0:for(l=1, k, t=k*l: if(cv[t]==0, s++); cv[t]++); v[k]=v[k-1]+s); v (from R. Stephan)
(Haskell)
import Data.List (nub)
a027424 n = length $ nub [i*j | i <- [1..n], j <- [1..n]]
-- Reinhard Zumkeller, Jan 01 2012
(PARI) A027424(n)={my(u=0); sum(j=1, n, sum(i=1, j, !bittest(u, i*j) & u+=1<<(i*j)))} \\ - M. F. Hasler, Oct 08 2012
|
|
|
CROSSREFS
|
Cf. A027384, A027417, A033677, A108407.
Equals A027384 - 1. First differences are in A062854.
Cf. A027426.
Sequence in context: A128261 A187263 A000791 * A191130 A134031 A130473
Adjacent sequences: A027421 A027422 A027423 * A027425 A027426 A027427
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
STATUS
|
approved
|
| |
|
|
