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

%I #152 Aug 21 2024 22:51:44

%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, and 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 Kevin Hartnett, <a href="https://www.quantamagazine.org/the-sum-product-problem-shows-how-addition-and-multiplication-constrain-each-other-20190206">How a Strange Grid Reveals Hidden Connections Between Simple Numbers</a>, Quanta Magazine, Feb 06 2019.

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

%p A027424m := proc(d,n)

%p local a,dvs ;

%p a := 0 ;

%p for dvs in numtheory[divisors](d) do

%p if dvs <= n then

%p a := max(a,dvs) ;

%p end if;

%p end do:

%p a ;

%p end proc:

%p A027424 := proc(n)

%p add(add(numtheory[mobius](L/d) *floor(A027424m(d,n) *n/L), d=numtheory[divisors](L)), L=1..n^2) ;

%p end proc:

%p seq(A027424(n),n=1..40) ; # _R. J. Mathar_, Oct 02 2020

%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

%o (Python)

%o def A027424(n): return len({i*j for i in range(1,n+1) for j in range(1,i+1)}) # _Chai Wah Wu_, Oct 13 2023

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

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

%Y Column 2 of A322967.

%Y Cf. A074738 (constant in asymptotic).

%K nonn,nice

%O 1,2

%A _N. J. A. Sloane_