A027384 -id:A027384 - 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)

A027426 Number of distinct products ijk with 0 <= i,j,k <= n.

Original entry on oeis.org

1, 2, 5, 11, 17, 31, 41, 66, 81, 101, 121, 174, 195, 267, 302, 344, 379, 493, 537, 679, 733, 805, 877, 1076, 1131, 1248, 1344, 1451, 1538, 1834, 1910, 2249, 2363, 2516, 2669, 2851, 2941, 3401, 3588, 3790, 3920, 4478, 4625, 5243, 5441, 5655, 5917, 6647, 6799, 7197

Offset: 0

N. J. A. Sloane

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 201 terms from T. D. Noe)

Cf. A027384, A027429.

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

a:=proc(n): nops({seq(seq(seq(i*j*k,k=0..j),j=0..i),i=0..n)}) end: seq(a(n),n=0..50); # Emeric Deutsch, Jan 25 2007

a[n_] := Table[i*j*k, {i, 0, n}, {j, i, n}, {k, j, n}] // Flatten // Union // Length; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Jan 30 2018 *)

pr(n)=my(v=List());for(i=1,n, for(j=i,n, listput(v, i*j))); Set(v)
a(n)=my(v=pr(n),u=v); for(i=2,n,u=Set(concat(u,v*i))); #u+1 \\ Charles R Greathouse IV, Mar 04 2014

from itertools import combinations_with_replacement as mc
def a(n): return len(set(i*j*k for i, j, k in mc(range(n+1), 3)))
print([a(n) for n in range(50)]) # Michael S. Branicky, May 28 2021

a(n) = A027425(n) + 1. - T. D. Noe, Jan 16 2007

A225252 T(n,k) = number of distinct values of the sum of n products of two 0..k integers.

Original entry on oeis.org

2, 4, 3, 7, 8, 4, 10, 16, 12, 5, 15, 27, 25, 16, 6, 19, 42, 43, 34, 20, 7, 26, 59, 67, 59, 43, 24, 8, 31, 81, 95, 92, 75, 52, 28, 9, 37, 105, 130, 131, 117, 91, 61, 32, 10, 43, 134, 169, 179, 167, 142, 107, 70, 36, 11, 54, 167, 215, 233, 228, 203, 167, 123, 79, 40, 12, 60, 203, 267

Offset: 1

R. H. Hardin, May 04 2013

			Table starts:
..2..4..7..10..15..19..26..31..37..43...54...60...73...81...90...98..115..124
..3..8.16..27..42..59..81.105.134.167..203..241..285..331..381..436..495..556
..4.12.25..43..67..95.130.169.215.267..324..385..454..527..606..692..784..880
..5.16.34..59..92.131.179.233.296.367..445..529..623..723..831..948.1073.1204
..6.20.43..75.117.167.228.297.377.467..566..673..792..919.1056.1204.1362.1528
..7.24.52..91.142.203.277.361.458.567..687..817..961.1115.1281.1460.1651.1852
..8.28.61.107.167.239.326.425.539.667..808..961.1130.1311.1506.1716.1940.2176
..9.32.70.123.192.275.375.489.620.767..929.1105.1299.1507.1731.1972.2229.2500
.10.36.79.139.217.311.424.553.701.867.1050.1249.1468.1703.1956.2228.2518.2824
.11.40.88.155.242.347.473.617.782.967.1171.1393.1637.1899.2181.2484.2807.3148

R. H. Hardin, Table of n, a(n) for n = 1..1325

Row 1 is A027384.

Cf. A225255.

Empirical: column k is n*k^2 - A225255(k) for large n (n>2 suffices through k=1000).

A027427 Number of distinct products ij with 0 <= i < j <= n.

Original entry on oeis.org

0, 1, 2, 4, 7, 11, 14, 20, 25, 32, 37, 47, 52, 64, 71, 79, 88, 104, 112, 130, 140, 151, 162, 184, 193, 211, 224, 240, 253, 281, 292, 322, 338, 355, 372, 391, 404, 440, 459, 479, 494, 534, 550, 592, 612, 632, 655, 701, 718, 753, 775, 801, 824, 876

Offset: 0

N. J. A. Sloane

nonn

T. D. Noe, Table of n, a(n) for n = 0..1000

Cf. A027430, etc.

Cf. A027384, A027428, A027429.

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

A027427 := proc(n)
    local L, i, j ;
    L := {};
    for i from 0 to n do
        for j from i+1 to n do
            L := L union {i*j};
        end do:
    end do:
    nops(L);
end proc:  # R. J. Mathar, Jun 09 2016

a[n_] := Table[i*j, {i, 0, n}, {j, i+1, n}] // Flatten // Union // Length;
Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Feb 03 2018 *)

def A027427(n): return 1+len({i*j for i in range(1,n+1) for j in range(1,i)}) if n else 0 # Chai Wah Wu, Oct 13 2023

a(n) = A027428(n)+1. - T. D. Noe, Jan 16 2007

A027417 Number of distinct products i*j with 0 <= i, j <= 2^n - 1.

Original entry on oeis.org

1, 2, 7, 26, 90, 340, 1238, 4647, 17578, 67592, 259768, 1004348, 3902357, 15202050, 59410557, 232483840, 911689012, 3581049040, 14081089288, 55439171531, 218457593223, 861617935051, 3400917861268, 13433148229639, 53092686926155, 209962593513292

Offset: 0

David Lambert (dlambert(AT)ichips.intel.com)

This is a subsequence of A027384.

			For n = 2 we have a(2) = 7 because taking all products of the integers {0, 1, 2, 3 = 2^2 - 1} we get 7 distinct integers {0, 1, 2, 3, 4, 6, 9}.

R. P. Brent and H. T. Kung, The area-time complexity of binary multiplication, J. ACM 28 (1981), 521-534. Corrigendum: ibid 29 (1982), 904.
R. P. Brent, C. Pomerance, D. Purdum, and J. Webster, Algorithms for the multiplication table, Integers 21 (2021), paper #A92.

Richard P. Brent, Table of n, a(n) for n = 0..30
Richard P. Brent, The Multiplication Table Problem Revisited, Australian National University and CARMA, University of Newcastle (Australia, 2019).
R. P. Brent and H. T. Kung, The area-time complexity of binary multiplication.
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]
R. P. Brent, C. Pomerance and J. Webster, Algorithms for the multiplication table problem, Slides of a talk given in May 2018.
R. P. Brent, C. Pomerance, D. Purdum, and J. Webster, Algorithms for the multiplication table, arXiv:1908.04251 [math.NT], 2019-2021.

Cf. A027384, A027424.

Array[Length@ Union[Times @@@ Tuples[Range[0, 2^# - 1], {2}]] &, 12, 0] (* Michael De Vlieger, May 27 2018 *)

def A027417(n): return len({i*j for i in range(1,1<Chai Wah Wu, Oct 13 2023

a(n) = A027384(2^n-1). - R. J. Mathar, Jun 09 2016

Corrected offset, added entries a(13)-a(25) and included a reference to a paper by Brent and Kung (1982) that gives the entries through a(17) by Richard P. Brent, Aug 20 2012

A027420 Triangle T00, T10, T01, T20, T11, T02, etc., where Tmn = number of distinct products ij with min(m,n) <= i,j <= max(m,n).

Original entry on oeis.org

1, 2, 2, 4, 1, 4, 7, 3, 3, 7, 10, 6, 1, 6, 10, 15, 9, 3, 3, 9, 15, 19, 14, 6, 1, 6, 14, 19, 26, 18, 10, 3, 3, 10, 18, 26, 31, 25, 14, 6, 1, 6, 14, 25, 31, 37, 30, 20, 10, 3, 3, 10, 20, 30, 37, 43, 36, 25, 15, 6, 1, 6, 15, 25, 36, 43, 54, 42, 31, 20, 10, 3, 3, 10, 20, 31, 42, 54

Offset: 0

N. J. A. Sloane

T(n,0) = T(n,n) = A027384(n). - Reinhard Zumkeller, May 02 2014

Reinhard Zumkeller, Rows n = 0..125 of table, flattened

Cf. A027384.

Cf. A241944 (row sums), A002262, A025581.

import Data.List (nub)
a027420 n k = a027420_tabl !! n !! k
a027420_row n = a027420_tabl !! n
a027420_tabl = zipWith (zipWith z) a002262_tabl a025581_tabl
               where z u v = length $ nub $ [i * j | i <- zs, j <- zs]
                             where zs = [min u v .. max u v]
-- Reinhard Zumkeller, May 02 2014

t[m_, n_] := i*j /. {ToRules @ Reduce[ Min[m, n] <= i <= j <= Max[m, n], Integers]} // Union // Length; row[n_] := Table[ t[m, n-m], {m, 0, n} ]; Table[ row[n], {n, 0, 11}] // Flatten (* Jean-François Alcover, Apr 16 2013 *)

More terms from Olivier Gérard, Nov 15 1997

A027421 Triangle T(n,k) = number of distinct products i*j with k<=i,j<=n, for 0<=k<=n.

Original entry on oeis.org

1, 2, 1, 4, 3, 1, 7, 6, 3, 1, 10, 9, 6, 3, 1, 15, 14, 10, 6, 3, 1, 19, 18, 14, 10, 6, 3, 1, 26, 25, 20, 15, 10, 6, 3, 1, 31, 30, 25, 20, 15, 10, 6, 3, 1, 37, 36, 31, 26, 20, 15, 10, 6, 3, 1, 43, 42, 37, 32, 26, 21, 15, 10, 6, 3, 1, 54, 53, 47, 41, 34, 28, 21, 15, 10, 6, 3, 1

Offset: 0

N. J. A. Sloane

			Triangle begins:
   1;
   2,1;
   4,3,1;
   7,6,3,1;
  10,9,6,3,1;
  ...

Robert Israel, Table of n, a(n) for n = 0..10010 (rows 0 to 140, flattened)

Cf. A027384, A027422.

f:= proc(n,k) local i,j;
   nops({seq(seq(i*j,j=i..n),i=k..n)})
end proc:
seq(seq(f(n,k),k=0..n),n=0..15); # Robert Israel, Apr 27 2025

From Robert Israel, Apr 27 2025: (Start)
T(n,n) = 1.
T(n,n-1) = 3 for n >= 2.
For each j, T(n,n-j) = (j+1)*(j+2)/2 for sufficiently large n. (End)

More terms from Olivier Gérard, Nov 15 1997

A027422 Triangle T00, T10, T11, T20, T21, T22, etc. where Tmn = number of distinct products ij with m-n<=i,j<=m.

Original entry on oeis.org

1, 1, 2, 1, 3, 4, 1, 3, 6, 7, 1, 3, 6, 9, 10, 1, 3, 6, 10, 14, 15, 1, 3, 6, 10, 14, 18, 19, 1, 3, 6, 10, 15, 20, 25, 26, 1, 3, 6, 10, 15, 20, 25, 30, 31, 1, 3, 6, 10, 15, 20, 26, 31, 36, 37, 1, 3, 6, 10, 15, 21, 26, 32, 37, 42, 43, 1, 3, 6, 10, 15, 21, 28, 34, 41, 47, 53, 54, 1, 3, 6

Offset: 0

N. J. A. Sloane

			1 ;
1 2 ;
1 3 4 ;
1 3 6 7 ;
1 3 6 9 10 ;
1 3 6 10 14 15 ;
1 3 6 10 14 18 19 ;
1 3 6 10 15 20 25 26 ;
1 3 6 10 15 20 25 30 31 ;
1 3 6 10 15 20 26 31 36 37 ;
1 3 6 10 15 21 26 32 37 42 43 ;
1 3 6 10 15 21 28 34 41 47 53 54 ;
1 3 6 10 15 21 27 34 40 47 53 59 60 ;

R. J. Mathar, Table of n, a(n) for n = 0..1890

Cf. A027384, A027421.

A027422 := proc(m,n)
    local L,i,j ;
    L := {};
    for i from m-n to m do
        for j from i to m do
            L := L union {i*j};
        end do:
    end do:
    nops(L);
end proc: # R. J. Mathar, May 06 2016

More terms from Olivier Gérard, Nov 15 1997

A225253 Number of distinct values of the sum of 2 products of two 0..n integers.

Original entry on oeis.org

1, 3, 8, 16, 27, 42, 59, 81, 105, 134, 167, 203, 241, 285, 331, 381, 436, 495, 556, 622, 690, 764, 841, 920, 1002, 1091, 1184, 1279, 1378, 1482, 1588, 1700, 1813, 1932, 2053, 2177, 2308, 2443, 2579, 2719, 2862, 3012, 3164, 3322, 3481, 3645, 3814, 3985, 4158, 4339

Offset: 0

R. H. Hardin, May 04 2013

nonn

			a(3) = 16 as the possible products i*j where 0 <= i, j <= 3 are 0, 1, 2, 3, 4, 6, 9. From these numbers we can find the 16 distinct sums, listed with a few examples, 0, 1, 2, 3, 4, 5, 6, 7 = 3+4, 8, 9, 10, 11, 12 = 6+6, 13 = 4+9, 15, 18. - _David A. Corneth_, Sep 07 2023

David A. Corneth, Table of n, a(n) for n = 0..3000 (first 999 terms from R. H. Hardin)
David A. Corneth, PARI program

Row 2 of A225252.

Cf. A027384, A062854, A225254.

a(n) = #setbinop((x,y)->x+y, setbinop((x,y)->x*y, [0..n])); \\ Michel Marcus, Sep 06 2023

\\ See PARI link. David A. Corneth, Sep 07 2023

from itertools import combinations_with_replacement
def A225253(n): return len({x+y for x,y in combinations_with_replacement({i*j for i in range(n+1) for j in range(i+1)},2)}) # Chai Wah Wu, Oct 13 2023

a(0)=1 prepended by Alois P. Heinz, Oct 13 2023

A384666 Number of distinct values of the quadratic discriminant D=b^2-4ac, for a,b,c in the range [-n,n].

Original entry on oeis.org

1, 6, 17, 35, 56, 90, 125, 178, 223, 282, 344, 436, 499, 608, 701, 804, 904, 1062, 1164, 1339, 1450, 1604, 1765, 1988, 2114, 2335, 2525, 2735, 2909, 3194, 3366, 3679, 3887, 4137, 4389, 4661, 4840, 5237, 5536, 5835, 6068, 6507, 6759, 7195, 7473, 7773, 8148, 8645

Offset: 0

Darío Clavijo, Jun 06 2025

nonn

a(n) is lower bounded by n log n for n > 0.

The number of distinct a*c is 2*A027384(n)-1.

Cf. A000217, A027384.

def a(n):
    D, ac = {0}, {0}
    SQ = [i*i for i in range(0, n+1)]
    for i in range(1, n+1):
        ac.add(i)
        if (s:= SQ[i]) > n:
            ac.add(s)
    for a_ in range(2, n):
        for c in range(a_+ 1, n+1):
            ac.add(a_* c)
    for b in range(n + 1):
        b2 = SQ[b]
        for v in ac:
            ac4 = v << 2
            D.add(b2 + ac4)
            if b2 < ac4:
                D.add(b2 - ac4)
    return len(D)
print([a(n) for n in range(0, 48)])

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

A027426 Number of distinct products ijk with 0 <= i,j,k <= n.

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A225252 T(n,k) = number of distinct values of the sum of n products of two 0..k integers.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A027427 Number of distinct products ij with 0 <= i < j <= n.

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Python

Formula

A027417 Number of distinct products i*j with 0 <= i, j <= 2^n - 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A027420 Triangle T00, T10, T01, T20, T11, T02, etc., where Tmn = number of distinct products ij with min(m,n) <= i,j <= max(m,n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

Extensions

A027421 Triangle T(n,k) = number of distinct products i*j with k<=i,j<=n, for 0<=k<=n.

Views

Author

A384666 Number of distinct values of the quadratic discriminant D=b^2-4ac, for a,b,c in the range [-n,n].