cp's OEIS Frontend

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

%I A027424 #152 Aug 21 2024 22:51:44
%S A027424 1,3,6,9,14,18,25,30,36,42,53,59,72,80,89,97,114,123,142,152,164,176,
%T A027424 199,209,225,239,254,267,296,308,339,354,372,390,410,423,460,480,501,
%U A027424 517,558,575,618,638,659,683,730,747,778,800,827,850,903
%N A027424 Number of distinct products ij with 1 <= i, j <= n (number of distinct terms in n X n multiplication table).
%C A027424 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 A027424 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 A027424 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 A027424 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 A027424 Hall, Richard Roxby, and Gérald Tenenbaum. Divisors. Cambridge University Press, 1988.
%D A027424 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 A027424 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 A027424 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 A027424 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 A027424 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 A027424 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 A027424 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 A027424 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 A027424 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 A027424 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 A027424 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 A027424 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 A027424 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 A027424 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 A027424 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 A027424 a(2^i-1) = A027417(i)-1. - _N. J. A. Sloane_, Sep 01 2018
%F A027424 From _Mats Granvik_, Nov 26 2019: (Start)
%F A027424 n^2 = Sum_{m=1..n^2} Sum_{k=1..n^2} [k|m]*[m <= n*k]*[k <= n]
%F A027424 a(n) = Sum_{m=1..n^2} sign( Sum_{k=1..n^2} [k|m]*[m <= n*k]*[k <= n] ), conjecture.
%F A027424 (End)
%p A027424 A027424m := proc(d,n)
%p A027424     local a,dvs ;
%p A027424     a := 0 ;
%p A027424     for dvs in numtheory[divisors](d) do
%p A027424         if dvs <= n then
%p A027424             a := max(a,dvs) ;
%p A027424         end if;
%p A027424     end do:
%p A027424     a ;
%p A027424 end proc:
%p A027424 A027424 := proc(n)
%p A027424     add(add(numtheory[mobius](L/d) *floor(A027424m(d,n) *n/L), d=numtheory[divisors](L)), L=1..n^2) ;
%p A027424 end proc:
%p A027424 seq(A027424(n),n=1..40) ; # _R. J. Mathar_, Oct 02 2020
%t A027424 u = {}; Table[u = Union[u, n*Range[n]]; Length[u], {n, 100}] (* _T. D. Noe_, Jan 07 2012 *)
%o A027424 (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 A027424 (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 A027424 (PARI) a(n)=#Set(concat(Vec(matrix(n,n,i,j,i*j)))) \\ _Charles R Greathouse IV_, Mar 27 2014
%o A027424 (PARI) a(n) = #setbinop((x,y)->x*y, vector(n, i, i)); \\ _Michel Marcus_, Jun 19 2015
%o A027424 (Haskell)
%o A027424 import Data.List (nub)
%o A027424 a027424 n = length $ nub [i*j | i <- [1..n], j <- [1..n]]
%o A027424 -- _Reinhard Zumkeller_, Jan 01 2012
%o A027424 (Python)
%o A027424 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 A027424 Cf. A027384, A027417, A033677, A108407, A027426.
%Y A027424 Equals A027384 - 1. First differences are in A062854.
%Y A027424 Column 2 of A322967.
%Y A027424 Cf. A074738 (constant in asymptotic).
%K A027424 nonn,nice
%O A027424 1,2
%A A027424 _N. J. A. Sloane_