A062854 -id:A062854 - 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).

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

Offset: 1

N. J. A. Sloane

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

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

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 06 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.

Cf. A027384, A027417, A033677, A108407, A027426.
Equals A027384 - 1. First differences are in A062854.
Column 2 of A322967.
Cf. A074738 (constant in asymptotic).

import Data.List (nub)
a027424 n = length $ nub [i*j | i <- [1..n], j <- [1..n]]
-- Reinhard Zumkeller, Jan 01 2012

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

u = {}; Table[u = Union[u, n*Range[n]]; Length[u], {n, 100}] (* T. D. Noe, Jan 07 2012 *)

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

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

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

a(n) = #setbinop((x,y)->x*y, vector(n, i, i)); \\ Michel Marcus, Jun 19 2015

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

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)

A126257 Number of distinct new terms in row n of Pascal's triangle.

Original entry on oeis.org

1, 0, 1, 1, 2, 2, 2, 3, 4, 4, 4, 5, 6, 6, 7, 5, 7, 8, 9, 9, 9, 8, 11, 11, 12, 12, 13, 13, 13, 14, 15, 15, 16, 16, 17, 16, 17, 18, 19, 19, 20, 20, 21, 21, 22, 21, 23, 23, 24, 24, 25, 25, 26, 26, 27, 26, 26, 28, 29, 29, 30, 30, 31, 31, 32, 32, 32, 33, 34, 34, 34, 35, 36, 36, 37, 37, 38

Offset: 0

Nick Hobson, Dec 24 2006

Partial sums are in A126256.

n occurs a(n) times in A265912. - Reinhard Zumkeller, Dec 18 2015

			Row 6 of Pascal's triangle is: 1, 6, 15, 20, 15, 6, 1. Of these terms, only 15 and 20 do not appear in rows 0-5. Hence a(6)=2.

Nick Hobson, Table of n, a(n) for n = 0..1000
Nick Hobson, Python program for this sequence

Cf. A007318, A062854, A126254, A126255, A126256.

Cf. A034868, A265912.

import Data.List.Ordered (minus, union)
a126257 n = a126257_list !! n
a126257_list = f [] a034868_tabf where
   f zs (xs:xss) = (length ys) : f (ys `union` zs) xss
                   where ys = xs `minus` zs
-- Reinhard Zumkeller, Dec 18 2015

lim=77; z=listcreate(1+lim^2\4); print1(1, ", "); r=1; for(a=1, lim, for(b=1, a\2, s=Str(binomial(a, b)); f=setsearch(z, s, 1); if(f, listinsert(z, s, f))); print1(1+#z-r, ", "); r=1+#z)

def A126257(n):
    if n:
        s, c = (1,), {1}
        for i in range(n-1):
            c.update(set(s:=(1,)+tuple(s[j]+s[j+1] for j in range(len(s)-1))+(1,)))
        return len(set((1,)+tuple(s[j]+s[j+1] for j in range(len(s)-1))+(1,))-c)
    return 1 # Chai Wah Wu, Oct 17 2023

A062851 Number of k such that 1 < k < n X n and k not of the form ij for 1 <= {i, j} <= n.

Original entry on oeis.org

0, 1, 3, 7, 11, 18, 24, 34, 45, 58, 68, 85, 97, 116, 136, 159, 175, 201, 219, 248, 277, 308, 330, 367, 400, 437, 475, 517, 545, 592, 622, 670, 717, 766, 815, 873, 909, 964, 1020, 1083, 1123, 1189, 1231, 1298, 1366, 1433, 1479, 1557, 1623, 1700, 1774, 1854

Offset: 1

Ron A. Lalonde (ronronronlalonde(AT)hotmail.com), Jun 25 2001

nonn

Smallest k for given n is given by A007918, largest by A005563 (except for some initial terms).

			a(4)=7 because there are 9 unique products in the 4 X 4 multiplication table (1 2 3 4 6 8 9 12 16), which excludes 7 non-product integers within the range 1 to 16 (5 7 10 11 13 14 15).

a(n) = n^2 - A027424.

Cf. A027424, A062854, A062855, A062856, A062857, A062859.

def A062851(n): return n**2-len({i*j for i in range(1,n+1) for j in range(1,i+1)}) # Chai Wah Wu, Oct 13 2023

A062855 First differences of A062851.

Original entry on oeis.org

0, 1, 2, 4, 4, 7, 6, 10, 11, 13, 10, 17, 12, 19, 20, 23, 16, 26, 18, 29, 29, 31, 22, 37, 33, 37, 38, 42, 28, 47, 30, 48, 47, 49, 49, 58, 36, 55, 56, 63, 40, 66, 42, 67, 68, 67, 46, 78, 66, 77, 74, 80, 52, 85, 78, 89, 83

Offset: 1

Ron A. Lalonde (ronronronlalonde(AT)hotmail.com), Jun 25 2001

nonn

			a(4)=4 because there are 7 integer non-products for the 4 X 4 multiplication table (5 7 10 11 13 14 15), which is 4 more than the 3 non-products for the 3 X 3 multiplication table (5 7 8).

Cf. A027424, A062851, A062854, A062856, A062857, A062858, A062859.

from itertools import takewhile
from sympy import divisors
def A062855(n): return (n<<1)-1-sum(1 for i in range(1,n+1) if all(d<=i for d in takewhile(lambda d:dChai Wah Wu, Oct 13 2023

a(n) = 2*n-1-A062854(n). - Chai Wah Wu, Oct 13 2023

A062856 In the square multiplication table of size A062857(n), the smallest number which appears n times.

Original entry on oeis.org

1, 2, 4, 6, 12, 12, 36, 60, 60, 60, 120, 120, 120, 120, 360, 360, 360, 360, 360, 360, 840, 840, 840, 840, 2520, 2520, 2520, 2520, 2520, 2520, 2520, 2520, 2520, 2520, 5040, 5040, 5040, 5040, 5040, 5040, 5040, 5040, 5040, 5040, 5040, 5040, 10080, 10080

Offset: 1

Ron Lalonde (ronronronlalonde(AT)hotmail.com), Jun 25 2001

nonn

Smallest number to appear n times in any m X m multiplication table.

			a(7)=36 because 36 is the first product to appear in the m X m multiplication tables 7 times as m increases from 1 to infinity.

Cf. A027424, A062851, A062854, A062855, A062857, A062858, A062859.

b[1] = {1, 1}; b[n_] := b[n] = For[m = b[n-1][[1]], True, m++, T = Table[i j, {i, m}, {j, m}] // Flatten // Tally; sel = SelectFirst[T, #[[2]] >= n&]; If[sel != {}, Print[n, " ", m, " ", sel[[1]]]; Return[{m, sel[[1]]}] ]];
a[n_] := b[n][[2]];
Table[a[n], {n, 1, 50}] (* Jean-François Alcover, Mar 25 2019 *)

from itertools import count
from collections import Counter
def A062856(n):
    if n == 1: return 1
    c = Counter()
    for m in count(1):
        for i in range(1,m):
            ij = i*m
            c[ij] += 2
            if c[ij]>=n:
                return ij
        c[m*m] = 1 # Chai Wah Wu, Oct 16 2023

More terms from Don Reble, Nov 08 2001

A062857 Size of smallest square multiplication table which contains some number at least n times.

Original entry on oeis.org

1, 2, 4, 6, 12, 12, 18, 20, 30, 30, 40, 40, 60, 60, 72, 72, 90, 90, 120, 120, 140, 140, 168, 168, 180, 180, 210, 210, 252, 252, 280, 280, 315, 315, 336, 336, 360, 360, 420, 420, 504, 504, 560, 560, 630, 630, 672, 672, 720, 720, 792, 792, 840, 840, 924, 924, 990

Offset: 1

Ron Lalonde (ronronronlalonde(AT)hotmail.com), Jun 25 2001

nonn

a(n) is the least number m such that there exists k with 1 <= k <= m^2 such that k has at least n divisors t with k/m <= t <= m. - Robert Israel, Jan 30 2017

			a(7)=18 because the 18 X 18 multiplication table is the smallest to contain a product of frequency 7 (namely the number A062856(7)=36).

The least such number is A062856(n).

Cf. A027424, A062851, A062854, A062855, A062856, A062858, A062859.

N = 1000; % to get all terms with a(n) <= N
M = sparse(1,N^2);
A(1) = 1;
imax = 1;
for k = 2:N
  M(k*[1:k-1]) = M(k*[1:k-1])+2;
  M(k^2) = 1;
  newimax = max(M);
  A(imax+1:newimax) = k;
  imax = newimax;
end
A  % Robert Israel, Jan 30 2017

a[1] = 1; a[n_] := a[n] = For[m = a[n-1], True, m++, T = Table[i j, {i, m}, {j, m}] // Flatten // Tally; sel = SelectFirst[T, #[[2]] >= n&]; If[sel != {}, Print[n, " ", m, " ", sel[[1]]]; Return[m]]];
Table[a[n], {n, 1, 60}] (* Jean-François Alcover, Mar 25 2019 *)

from itertools import count
from collections import Counter
def A062857(n):
    if n == 1: return 1
    c = Counter()
    for m in count(1):
        for i in range(1,m):
            ij = i*m
            c[ij] += 2
            if c[ij]>=n:
                return m
        c[m*m] = 1 # Chai Wah Wu, Oct 16 2023

More terms from Don Reble, Nov 08 2001

Name clarified by Robert Israel, Jan 30 2017

A062859 Size of smallest triangular multiplication table which contains some number n times.

Original entry on oeis.org

1, 4, 12, 18, 30, 40, 60, 72, 90, 120, 140, 168, 180, 210, 252, 280, 315, 336, 360, 420, 504, 560, 630, 672, 720, 792, 840, 924, 990, 1008, 1155, 1232, 1260, 1320, 1386, 1540, 1584, 1680, 1848, 1980, 2016, 2310, 2376, 2520, 2640, 2772, 2970, 3024, 3080

Offset: 1

Ron A. Lalonde (ronronronlalonde(AT)hotmail.com), Jun 25 2001

nonn

			a(4)=18 because the size-18 triangular multiplication table is the smallest to contain a particular number 4 times (namely the number A062858(4)=36).

The least such number is A062858(n).

Cf. A027424, A062851, A062854, A062855, A062856, A062857, A062858, A000217.

from itertools import count
from collections import Counter
def A062859(n):
    c = Counter()
    for m in count(1):
        for i in range(1,m+1):
            ij = i*m
            c[ij] += 1
            if c[ij]>=n:
                return m # Chai Wah Wu, Oct 16 2023

More terms from Don Reble, Nov 08 2001

A108407 Number of added unique known entries when going from the n X n to the (n+1) X (n+1) multiplication table.

Original entry on oeis.org

0, 0, 1, 0, 2, 0, 3, 3, 4, 0, 6, 0, 6, 6, 8, 0, 9, 0, 10, 9, 10, 0, 14, 9, 12, 12, 15, 0, 18, 0, 17, 15, 16, 15, 23, 0, 18, 18, 24, 0, 25, 0, 24, 24, 22, 0, 31, 18, 28, 24, 29, 0, 32, 24, 34, 27, 28, 0, 41, 0, 30, 35, 38, 29, 40, 0, 38, 33, 44, 0, 49, 0, 36, 41, 43, 32, 47, 0, 52

Offset: 1

Ralf Stephan, Jun 03 2005

nonn

			When going to 8 X 8, the added entries 8,16,24 are already known, so a(7)=3:
.1..2..3..4..5..6..7....8 *
....4..6..8.10.12.14...16 *
.......9.12.15.18.21...24 *
.........16.20.24.28...32
............25.30.35...40
...............36.42...48
..................49...56
.......................64

Seiichi Manyama, Table of n, a(n) for n = 1..1000

Unique values of sequence are in A108408.

Cf. A027424 (total unique entries), A062854 (added unique unknown entries).

A108407 := proc(n)
    n+1-A062854(n+1) ;
end proc:
seq(A108407(n),n=1..40) ; # R. J. Mathar, Oct 02 2020

nmax = 100;
A062854 = Table[u = If[n == 1, {}, Union[u, n Range[n]]]; Length[u], {n, 1, nmax+1}] // Differences // Prepend[#, 1]&;
a[n_] := n + 1 - A062854[[n+1]];
Table[a[n], {n, 1, nmax}] (* Jean-François Alcover, Oct 02 2020 *)

from itertools import takewhile
from sympy import divisors
def A108407(n): return n+1-sum(1 for i in range(1,n+2) if all(d<=i for d in takewhile(lambda d:d<=n,divisors((n+1)*i)))) # Chai Wah Wu, Oct 13 2023

For prime p, a(p-1) = 0.

a(n) = n+1 - A062854(n+1).

A062858 In the triangular multiplication table of size A062859(n), the smallest number which appears n times.

Original entry on oeis.org

1, 4, 12, 36, 60, 120, 120, 360, 360, 360, 840, 840, 2520, 2520, 2520, 2520, 2520, 5040, 5040, 5040, 5040, 5040, 5040, 10080, 10080, 27720, 27720, 27720, 27720, 55440, 55440, 55440, 55440, 55440, 55440, 55440, 55440, 55440, 55440, 55440

Offset: 1

Ron Lalonde (ronronronlalonde(AT)hotmail.com), Jun 25 2001

nonn

Smallest number to appear n times in any m X m multiplication table (excluding the numbers below the diagonals).

			a(4)=36 because 36 is the smallest number to appear 4 times in the triangular multiplication table of size A062859(4)=18.

Cf. A027424, A062851, A062854, A062855, A062856, A062857, A062859, A000217.

from itertools import count
from collections import Counter
def A062858(n):
    c = Counter()
    for m in count(1):
        for i in range(1,m+1):
            ij = i*m
            c[ij] += 1
            if c[ij]>=n:
                return ij # Chai Wah Wu, Oct 16 2023

More terms from Don Reble, Nov 08 2001

A333995 a(n) = number of distinct composite numbers in the n X n multiplication table that are not in the n-1 X n-1 multiplication table.

Original entry on oeis.org

0, 1, 2, 3, 4, 4, 6, 5, 6, 6, 10, 6, 12, 8, 9, 8, 16, 9, 18, 10, 12, 12, 22, 10, 16, 14, 15, 13, 28, 12, 30, 15, 18, 18, 20, 13, 36, 20, 21, 16, 40, 17, 42, 20, 21, 24, 46, 17, 31, 22, 27, 23, 52

Offset: 1

Charles Kusniec, Sep 05 2020

nonn

			a(2) = 1 since the 1 X 1 and 2 X 2 multiplication tables are
---
  1
---
  1 2
  2 4
---
and the composite number 4 has appeared.
---
a(8)=5:
.1..2..3..4..5..6..7....8
....4..6..8.10.12.14...16
.......9.12.15.18.21...24
.........16.20.24.28...32 *
............25.30.35...40 *
...............36.42...48 *
..................49...56 *
.......................64 *

Cf. A010051, A062854, A108407.

from itertools import takewhile
from sympy import divisors, isprime
def A333995(n): return sum(1 for i in range(1,n+1) if all(d<=i for d in takewhile(lambda d:d1 else 0 # Chai Wah Wu, Oct 14 2023

a(n) = n - A108407(n-1) - A010051(n), n > 1. - Corrected by R. J. Mathar, Oct 02 2020

a(n) = A062854(n) - A010051(n) for n > 1. - Chai Wah Wu, Oct 14 2023

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Formula

A126257 Number of distinct new terms in row n of Pascal's triangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

PARI

Python

A062851 Number of k such that 1 < k < n X n and k not of the form ij for 1 <= {i, j} <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

A062855 First differences of A062851.

Views

Author

Keywords

Examples

Crossrefs

Programs

Python

Formula

A062856 In the square multiplication table of size A062857(n), the smallest number which appears n times.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Extensions

A062857 Size of smallest square multiplication table which contains some number at least n times.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

MATLAB

Mathematica

Python

Extensions

A062859 Size of smallest triangular multiplication table which contains some number n times.

Views

Author

Keywords

Examples

Crossrefs

Programs

Python