login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


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

%I

%S 1,3,6,9,14,18,25,30,36,42,53,59,72,80,89,97,114,123,142,152,164,176,

%T 199,209,225,239,254,267,296,308,339,354,372,390,410,423,460,480,501,

%U 517,558,575,618,638,659,683,730,747,778,800,827,850,903

%N Number of distinct products ij with 1 <= i, j <= n (number of distinct terms in n X n multiplication table).

%C As n->infinity what is an asymptotic expression for a(n)? Reply from Carl Pomerance: Erdős showed that a(n) is o(n^2). Linnik and Vinogradov (1960) 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.

%C An easy lower bound is to consider primes p > n/2, times anything < n. This gives n^2/(2 log n). - Richard C. Schroeppel, Jul 05 2003

%C 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.

%C Erdős showed in 1955 that a(n)=O(n^2/(log n)^c) for some c>0. In 1960, Erdős 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

%D Hall, Richard Roxby, and Gérald Tenenbaum. Divisors. Cambridge University Press, 1988.

%D Y. V. Linnik and I. M. Vinogradov, An asymptotic inequality in the theory of numbers, Vestnik Leningrad. Univ. 15 (1960), 41-49 (in Russian).

%H Seiichi Manyama, <a href="/A027424/b027424.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from T. D. Noe, first 2329 terms from N. J. A. Sloane)

%H R. P. Brent and C. Pomerance, <a href="http://maths-people.anu.edu.au/~brent/pd/multiplication.pdf">The multiplication table, and random factored integers</a>, Presented at 56th Annual Meeting of Australian Math. Soc., Ballarat, Sept. 2012.

%H R. P. Brent and C. Pomerance, <a href="/A027424/a027424.pdf">The multiplication table, and random factored integers</a>, Presented at 56th Annual Meeting of Australian Math. Soc., Ballarat, Sept. 2012. [Cached copy, with permission]

%H R. P. Brent and C. Pomerance, <a href="http://maths-people.anu.edu.au/~brent/pd/multiplication-HK.pdf">Some mysteries of multiplication, and how to generate random factored integers</a>, Presented in Hong Kong, Feb. 2015.

%H R. P. Brent and C. Pomerance, <a href="/A027424/a027424_1.pdf">Some mysteries of multiplication, and how to generate random factored integers</a>, Presented in Hong Kong, Feb. 2015. [Cached copy, with permission]

%H Richard Brent, Carl Pomerance, David Purdum, Jonathan Webster, <a href="https://arxiv.org/abs/1908.04251">Algorithms for the Multiplication Table Problem</a>, arXiv:1908.04251 [math.NT], 2019.

%H P. Erdős, <a href="http://www.renyi.hu/~p_erdos/1961-24.pdf">Some remarks on number theory</a>, Riveon Lematematika 9 (1955), 45-48 (in Hebrew. English summary).

%H K. Ford, <a href="http://annals.math.princeton.edu/wp-content/uploads/annals-v168-n2-p01.pdf">The distribution of integers with a divisor in a given interval</a>. Annals of Math. 168(2), 367-433. arXiv:<a href="http://arxiv.org/abs/math/0401223">math/0401223</a>, (2008).

%H M. Hassani, <a href="http://arxiv.org/abs/math/0603644">Approximation of the Multiplication Table Function</a>, preprint arXiv:math/0603644 [math.NT], 2006.

%H D. Koukoulopoulos, <a href="http://arxiv.org/abs/1102.3236">On the number of integers in a generalized multiplication table</a>, arXiv:1102.3236 [math.NT], 2011-2013; Journal für die reine und angewandte Mathematik, 2012.

%H Yoni Nazarathy, <a href="https://medium.com/@yoni_26949/integers-sequences-in-the-footsteps-of-giants-d814bb668df1">Integers Sequences in the Footsteps of Giants</a> [Blog post and video about this sequence]

%H C. Pomerance (1998) <a href="http://www.ams.org/notices/199801/vertesi.pdf">Paul Erdős, Number Theorist Extraordinaire</a>, Notices Amer. Math. Soc. 45(1), 19-23.

%F 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

%F a(2^i-1) = A027417(i)-1. - _N. J. A. Sloane_, Sep 01 2018

%F From _Mats Granvik_, Nov 26 2019: (Start)

%F n^2 = Sum_{m=1..n^2} Sum_{k=1..n^2} [k|m]*[m <= n*k]*[k <= n]

%F a(n) = Sum_{m=1..n^2} sign( Sum_{k=1..n^2} [k|m]*[m <= n*k]*[k <= n] ), conjecture.

%F (End)

%t u = {}; Table[u = Union[u, n*Range[n]]; Length[u], {n, 100}] (* _T. D. Noe_, Jan 07 2012 *)

%o (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_

%o (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

%o (PARI) a(n)=#Set(concat(Vec(matrix(n,n,i,j,i*j)))) \\ _Charles R Greathouse IV_, Mar 27 2014

%o (PARI) a(n) = #setbinop((x,y)->x*y, vector(n, i, i);); \\ _Michel Marcus_, Jun 19 2015

%o (Haskell)

%o import Data.List (nub)

%o a027424 n = length $ nub [i*j | i <- [1..n], j <- [1..n]]

%o -- _Reinhard Zumkeller_, Jan 01 2012

%Y Cf. A027384, A027417, A033677, A108407, A027426.

%Y Equals A027384 - 1. First differences are in A062854.

%Y Column 2 of A322967.

%K nonn,nice

%O 1,2

%A _N. J. A. Sloane_

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 25 23:23 EDT 2020. Contains 337346 sequences. (Running on oeis4.)