login
This site is supported by donations to The OEIS Foundation.

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

R. P. Brent and C. Pomerance, The multiplication table, and random factored integers, http://maths-people.anu.edu.au/~brent/pd/multiplication.pdf, 2012.

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 \\ Ralf Stephan

(PARI) a(n)=#Set(concat(Vec(matrix(n, n, i, j, i*j)))) \\ Charles R Greathouse IV, Mar 27 2014

(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, A027426.

Equals A027384 - 1. First differences are in A062854.

Sequence in context: A187263 A230876 A000791 * A191130 A134031 A228172

Adjacent sequences:  A027421 A027422 A027423 * A027425 A027426 A027427

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane.

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified April 24 04:20 EDT 2014. Contains 240947 sequences.