login
The OEIS is supported by the many generous donors to the OEIS 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). 34
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: 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.
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
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.
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
REFERENCES
Hall, Richard Roxby, and Gérald Tenenbaum. Divisors. Cambridge University Press, 1988.
Y. V. Linnik and I. M. Vinogradov, An asymptotic inequality in the theory of numbers, Vestnik Leningrad. Univ. 15 (1960), 41-49 (in Russian).
LINKS
Seiichi Manyama, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe, first 2329 terms from N. J. A. Sloane)
R. P. Brent and C. Pomerance, The multiplication table, and random factored integers, Presented at 56th Annual Meeting of Australian Math. Soc., Ballarat, Sept. 2012.
R. P. Brent and C. Pomerance, The multiplication table, and random factored integers, Presented at 56th Annual Meeting of Australian Math. Soc., Ballarat, Sept. 2012. [Cached copy, with permission]
R. P. Brent and C. Pomerance, Some mysteries of multiplication, and how to generate random factored integers, Presented in Hong Kong, Feb. 2015.
R. P. Brent and C. Pomerance, Some mysteries of multiplication, and how to generate random factored integers, Presented in Hong Kong, Feb. 2015. [Cached copy, with permission]
Richard Brent, Carl Pomerance, David Purdum, and Jonathan Webster, Algorithms for the Multiplication Table Problem, arXiv:1908.04251 [math.NT], 2019.
P. Erdős, Some remarks on number theory, Riveon Lematematika 9 (1955), 45-48 (in Hebrew. English summary).
K. Ford, The distribution of integers with a divisor in a given interval. Annals of Math. 168(2), 367-433. arXiv:math/0401223, (2008).
Kevin Hartnett, How a Strange Grid Reveals Hidden Connections Between Simple Numbers, Quanta Magazine, Feb. 6 2019.
M. Hassani, Approximation of the Multiplication Table Function, preprint arXiv:math/0603644 [math.NT], 2006.
D. Koukoulopoulos, On the number of integers in a generalized multiplication table, arXiv:1102.3236 [math.NT], 2011-2013; Journal für die reine und angewandte Mathematik, 2012.
Yoni Nazarathy, Integers Sequences in the Footsteps of Giants [Blog post and video about this sequence]
C. Pomerance (1998) Paul Erdős, 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
a(2^i-1) = A027417(i)-1. - N. J. A. Sloane, Sep 01 2018
From Mats Granvik, Nov 26 2019: (Start)
n^2 = Sum_{m=1..n^2} Sum_{k=1..n^2} [k|m]*[m <= n*k]*[k <= n]
a(n) = Sum_{m=1..n^2} sign( Sum_{k=1..n^2} [k|m]*[m <= n*k]*[k <= n] ), conjecture.
(End)
MAPLE
A027424m := proc(d, n)
local a, dvs ;
a := 0 ;
for dvs in numtheory[divisors](d) do
if dvs <= n then
a := max(a, dvs) ;
end if;
end do:
a ;
end proc:
A027424 := proc(n)
add(add(numtheory[mobius](L/d) *floor(A027424m(d, n) *n/L), d=numtheory[divisors](L)), L=1..n^2) ;
end proc:
seq(A027424(n), n=1..40) ; # R. J. Mathar, Oct 02 2020
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) 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
(PARI) a(n)=#Set(concat(Vec(matrix(n, n, i, j, i*j)))) \\ Charles R Greathouse IV, Mar 27 2014
(PARI) a(n) = #setbinop((x, y)->x*y, vector(n, i, i); ); \\ Michel Marcus, Jun 19 2015
(Haskell)
import Data.List (nub)
a027424 n = length $ nub [i*j | i <- [1..n], j <- [1..n]]
-- Reinhard Zumkeller, Jan 01 2012
(Python)
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
CROSSREFS
Equals A027384 - 1. First differences are in A062854.
Column 2 of A322967.
Sequence in context: A187263 A230876 A000791 * A294476 A258087 A191130
KEYWORD
nonn,nice
AUTHOR
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 01:34 EDT 2024. Contains 370952 sequences. (Running on oeis4.)