1,2

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 in 1955 showed 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

C. Pomerance, "Paul Erdos,...", Notices Amer. Math. Soc., Vol. 45, No. 1, 1998, pp. 19-23.

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).

K. Ford, The distribution of integers with a divisor in a given interval, preprint.

T. D. Noe, Table of n, a(n) for n=1..1000

K. Ford, The distribution of integers with a divisor in a given interval.

(PARI) multab(N)=local(v, cv, s, t); v=vector(N); cv=vector(N*N); v[1]=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)

Cf. A027384, A033677, A108407.

Equals A027384 - 1. First differences are in A062854.

Sequence in context: A086838 A128261 A000791 this_sequence A134031 A130473 A082643

Adjacent sequences: A027421 A027422 A027423 this_sequence A027425 A027426 A027427

nonn

njas