A027424 -id:A027424 - cp's OEIS frontend

A322967 Square array A(n,k), n >= 1, k >= 1, read by antidiagonals, where A(n,k) is the number of distinct products Product_{j=1..k} b_j with 1 <= b_j<= n.

1, 1, 2, 1, 3, 3, 1, 4, 6, 4, 1, 5, 10, 9, 5, 1, 6, 15, 16, 14, 6, 1, 7, 21, 25, 30, 18, 7, 1, 8, 28, 36, 55, 40, 25, 8, 1, 9, 36, 49, 91, 75, 65, 30, 9, 1, 10, 45, 64, 140, 126, 140, 80, 36, 10, 1, 11, 55, 81, 204, 196, 266, 175, 100, 42, 11

Offset: 1

Seiichi Manyama, Dec 31 2018

			In case of (n,k) = (3,2):
  | 1  2  3
--+--------
1 | 1, 2, 3
2 | 2, 4, 6
3 | 3, 6, 9
Distinct products are 1,2,3,4,6,9. So A(3,2) = 6.
Square array begins:
   1,  1,   1,   1,   1,   1,    1,    1,    1, ...
   2,  3,   4,   5,   6,   7,    8,    9,   10, ...
   3,  6,  10,  15,  21,  28,   36,   45,   55, ...
   4,  9,  16,  25,  36,  49,   64,   81,  100, ...
   5, 14,  30,  55,  91, 140,  204,  285,  385, ...
   6, 18,  40,  75, 126, 196,  288,  405,  550, ...
   7, 25,  65, 140, 266, 462,  750, 1155, 1705, ...
   8, 30,  80, 175, 336, 588,  960, 1485, 2200, ...
   9, 36, 100, 225, 441, 784, 1296, 2025, 3025, ...

Seiichi Manyama, Antidiagonals n = 1..25, flattened

Columns 1-5 give A001477, A027424, A027425, A100437, A284988

Main diagonal gives A110713.

Table[Length@ Union@ Flatten[TensorProduct @@ ConstantArray[Range@ #, k]] &[n - k + 1], {n, 11}, {k, n, 1, -1}] // Flatten (* Michael De Vlieger, Jan 01 2019 *)

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

A219729 Sum_{x <= n} largest divisor of x that is <= sqrt(x).

Original entry on oeis.org

1, 2, 3, 5, 6, 8, 9, 11, 14, 16, 17, 20, 21, 23, 26, 30, 31, 34, 35, 39, 42, 44, 45, 49, 54, 56, 59, 63, 64, 69, 70, 74, 77, 79, 84, 90, 91, 93, 96, 101, 102, 108, 109, 113, 118, 120, 121, 127, 134, 139, 142, 146, 147, 153, 158, 165, 168, 170, 171, 177, 178

Offset: 1

Michel Marcus, Nov 26 2012

nonn

G. Tenenbaum proved that limit(log(a(n)/n^(3/2)))/log(log(n)) is -b with b = 1-(1+loglog 2)/log 2 = 0.08607... (same constant as in A027424 comment) (théorème 1).

Ivan Neretin, Table of n, a(n) for n = 1..10000
Steven Finch, Multiples and divisors, January 27, 2004. [Cached copy, with permission of the author]
Gérald Tenenbaum, Sur deux fonctions de diviseurs, J. London Math. Soc. (1976) s2-14 (3): 521-526; alternative copy.

Cf. A027424, A033676, A219730.

t = Table[d = Divisors[n]; d[[Ceiling[Length[d]/2]]], {n, 100}]; Accumulate[t] (* T. D. Noe, Nov 26 2012 *)

A126959 a(k) = k! * lim_{n->oo} card({ i*j; i=1..k, j=1..n })/n.

Original entry on oeis.org

1, 3, 12, 58, 352, 2376, 19296, 168912, 1670976, 18000000, 219916800, 2781561600, 39605760000, 584889984000, 9253091635200, 154909552896000, 2834240274432000, 52918877491200000, 1074184895250432000

Offset: 1

M. F. Hasler, Mar 19 2007, Mar 22 2007

nonn

a(k) = k! card { i*j, i<=k, j<=k# } / k# where k# = lcm(1,2,3...,k) a(k)/(k+1)! <= 1/2 for all k.

			a(2)=3/2 since #{ i*j, i=1..2, j=1..2 } / 2 = #{ 1,2, 2,4 } / 2 = #{1,2,4} / 2.
a(3)=2 since #{ i*j, i=1..3, j=1..6 } / 6 = #{ 1,2,3,4,5,6, 2,4,6,8,10,12, 3,6,9,12,15,18 } / 6 = #{ 1,2,3,4,5,6,8,9,10,12,15,18 } / 6.

A. A. Buchstab, "Asymptotic estimates of a general number-theoretic function", Mat. Sbornik 44 (1937), 1239-1246.

M. F. Hasler, Table of n, a(n) for n = 1..36
N. G. de Bruijn, On the number of uncancelled elements in the sieve of Eratosthenes, Proc. Neder. Akad. Wetensch, 1950.
"Counting Integers and their Multiplicities" on mersenneforum.org

Cf. A101459, A027424.

p:=proc(n) option remember;local s,t,i,j: s:=1; t:={}:
for i from n-1 by -1 to 1+n/(min@op@eval@numtheory[factorset])(n) do
t := t union { ilcm(n,i)/n };
t := select( x-> numtheory[divisors](x) intersect t = { x }, t ):
for j in combinat[powerset](t) do s := s+(-1)^nops(j)/ilcm(op(j)) od:
od; s/n end:
A126959 := k -> k!*add( p(n), n=1..k);

p(n)={ local( cnt=lcm(vector(n-1,j,j)), L=vector(cnt,j,n*j), s=cnt ); forstep( i=n-1, n/factor(n)[1,1]+1, -1, forstep( j=lcm(n,i)/n, #L, lcm(n,i)/n, if( L[j] && (L[j] % i == 0), L[j]=0; cnt--)); s+=cnt ); s/#L/n } a=vector(16); a[1]=1; for( k=2, #a, a[k]=k*a[k-1]+k!*p(k));

A184677 Number of numbers <= p^2 with largest prime factor <= p, where p is the n-th prime; a(0) = 1.

Original entry on oeis.org

1, 3, 7, 16, 30, 61, 88, 138, 177, 248, 361, 423, 569, 690, 777, 924, 1137, 1370, 1495, 1765, 1979, 2129, 2452, 2711, 3075, 3563, 3871, 4078, 4412, 4639, 4996, 6027, 6427, 6988, 7272, 8181, 8494, 9135, 9803, 10320, 11031, 11768, 12140, 13315, 13713, 14330

Offset: 0

Reinhard Zumkeller, Jun 27 2011

nonn

a(n) = #{m: m<=A001248(n) and A006530(m)<=A000040(n)} for n > 0.

			a(1) = #{1,2,4} = 3 = number of binary powers <= 4;
a(2) = #{1,2,3,4,6,8,9} = 7 = number of 3-smooth numbers <= 9;
a(3) = #{1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25} = 16 = number of 5-smooth numbers <= 25.

Charles R Greathouse IV, Table of n, a(n) for n = 0..1000

Smooth numbers: A000079, A003586, A051037, A002473, A051038, A080197, A080681, A080682, A080683.

Cf. A027424.

Block[{nn = 45, w}, w = Array[FactorInteger[#][[All, 1]] &, Prime[nn]^2]; {1}~Join~Table[Count[w[[1 ;; p^2]], ?(AllTrue[#, # <= p &] &)], {p, Prime@ Range@ nn}]] (* _Michael De Vlieger, Mar 13 2021 *)

a(n)=if(n==0, return(1)); my(p=prime(n),s=p); forfactored(k=p+1,p^2, if(vecmax(k[2][,1])<=p, s++)); s \\ Charles R Greathouse IV, Nov 27 2017

A263996 Smallest possible cardinality of the union of the set of pairwise sums and the set of pairwise products from a set of n positive integers.

Original entry on oeis.org

1, 4, 7, 11, 15, 20, 26, 30, 36, 44, 49, 57, 64, 71, 80, 86, 96, 104, 112, 121, 131, 141, 150, 160, 169, 179, 190, 200, 212, 222, 235, 248, 260, 272, 283, 296, 307, 320, 335, 348, 360, 371

Offset: 1

Hugo Pfoertner, Nov 15 2015

nonn

The November 2015 - February 2016 round of Al Zimmermann's programming contests asked for optimal sets producing a(40), a(80), a(120), ..., a(1000).

			a(1) = 1 because for the set {2} the union of {2+2} and {2*2} = {4}.
a(7) = 26: The set {1,2,3,4,6,8,12} has the set of pairwise sums {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,20,24} and the set of pairwise products {1,2,3,4,6,8,9,12,16,18,24,32,36,48,64,72,96,144}. The cardinality of the union of the two sets, {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,20,24,32,36,48,64,72,96,144}, is 26. This is the first nontrivial case with a(n) < A263995(n), which uses the set {1..n}.

Richard K. Guy, Unsolved Problems in Number Theory, 3rd ed., Springer-Verlag New York, 2004. Problem F18.

Hugo Pfoertner, Table of n, a(n) for n = 1..205
P. Erdős and E. Szemeredi, On sums and products of integers, Studies in Pure Mathematics, Birkhäuser, Basel, 1983, pp. 213-218. DOI:10.1007/978-3-0348-5438-2_19
Kevin Hartnett, How a Strange Grid Reveals Hidden Connections Between Simple Numbers, Quanta Magazine, Feb. 6 2019.
Al Zimmermann's Programming Contests, Sums and Products I, Nov 2015 - Feb 2016.

Cf. A027424, A263995.

A281505 Numbers of the form y^2 - x^2 such that x^2 + y^2 is a prime and 0 < x < y.

Original entry on oeis.org

3, 5, 9, 11, 15, 19, 21, 25, 29, 35, 39, 45, 49, 51, 55, 59, 61, 65, 69, 71, 75, 79, 85, 91, 95, 99, 101, 105, 115, 121, 129, 131, 139, 141, 145, 159, 165, 169, 171, 175, 181, 189, 195, 199, 201, 205, 209, 215, 219, 221

Offset: 1

Thomas Ordowski, Jan 23 2017

nonn

What is the natural density of this set of these numbers?
There are 204 terms up to 10^3, 1849 up to 10^4, 16881 up to 10^5, 160194 up to 10^6, 1531730 up to 10^7, and 14766494 up to 10^8. - Charles R Greathouse IV, Jan 23 2017
Numbers of the form s*t where 0 < s < t and (s^2 + t^2)/2 is prime. - Robert Israel, Jan 23 2017

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Sam Chow and Carl Pomerance, Triangles with prime hypotenuse, arXiv:1703.10953 [math.NT], 2017.
Cihan Sabuncu, Right-angled triangles with almost prime hypotenuse, arXiv:2401.16334 [math.NT], 2024. Mentions this sequence.

Cf. A002144, A048161 is a subsequence, A070079 contains the same numbers.

filter:= proc(n)
  ormap(s -> isprime((s^2 + (n/s)^2)/2), select(s -> s^2Robert Israel, Jan 23 2017

filter[n_] := AnyTrue[Select[Divisors[n], #^2 < n & ], PrimeQ[(#^2 + (n/#)^2)/2] & ];
Select[Range[1, 1000, 2], filter] (* Jean-François Alcover, Nov 27 2017, after Robert Israel *)

list(lim)=my(v=List()); for(a=1,sqrtint(lim\=1), for(x=1,(lim-a^2)\2\a, if(isprime((x+a)^2+x^2), listput(v,(x+a)^2-x^2)))); Set(v) \\ Charles R Greathouse IV, Jan 23 2017

a(n) = n(log n)^c /(log log n)^O(1), where c = 1 - (1 + log log 2)/log 2 = 0.086... Cf. A027424. - Conjectured by Carl Pomerance, Jan 25 2017

More terms from Altug Alkan, Jan 23 2017

a(17)-a(50) from Charles R Greathouse IV, Jan 23 2017

A284988 Number of distinct products ijklm for 1 <= i <= j <= k <= l <= m <= n.

Original entry on oeis.org

1, 6, 21, 36, 91, 126, 266, 336, 441, 546, 994, 1120, 1890, 2184, 2562, 2856, 4482, 4932, 7392, 8052, 9042, 10032, 14377, 15092, 17237, 18887, 20812, 22297, 30635, 31856, 42783, 45240, 49023, 52806, 57707, 59436, 77623, 83083, 89180, 92365, 118188, 122248, 154188

Offset: 1

Seiichi Manyama, Apr 07 2017

nonn

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

Cf. A027424, A027425, A100437.

A321165 Sum of distinct products i*j with 1 <= i, j <= n.

Original entry on oeis.org

1, 7, 25, 61, 136, 244, 440, 680, 1022, 1472, 2198, 2882, 4065, 5241, 6681, 8265, 10866, 13116, 16726, 19786, 23566, 27922, 34270, 38902, 45502, 52600, 60430, 68326, 80941, 89671, 105047, 116855, 130913, 146519, 163214, 177002, 203013, 224673, 247605, 268005, 303306

Offset: 1

Seiichi Manyama, Jan 10 2019

nonn

			a(2) = 1 + 2 + 4 = 7.
a(3) = 1 + 2 + 3 + 4 + 6 + 9 = 25.

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

Column 2 of A321163.

Cf. A027424.

a(n) = vecsum(setbinop((x, y)->x*y, vector(n, i, i); )); \\ Michel Marcus, Jan 10 2019

a(p) = a(p - 1) + p ^ 2 * (p + 1) / 2 for prime p. - David A. Corneth, Jan 10 2019

A334454 Number of distinct composite numbers in the n X n multiplication table.

Original entry on oeis.org

0, 1, 3, 6, 10, 14, 20, 25, 31, 37, 47, 53, 65, 73, 82, 90, 106, 115, 133, 143, 155, 167, 189, 199, 215, 229, 244, 257, 285, 297, 327, 342, 360, 378, 398, 411, 447, 467, 488, 504, 544, 561, 603, 623, 644, 668, 714, 731, 762, 784, 811, 834, 886

Offset: 1

Charles Kusniec, Sep 08 2020

nonn

Number of distinct products i*j for 2<=i<=j<=n. - Chai Wah Wu, Oct 14 2023

			There are a(7) = 20 distinct composite numbers in the 7x7 multiplication table:
1   2   3   4   5   6   7
    4*  6*  8* 10* 12  14*
        9* 12* 15* 18* 21*
           16* 20* 24* 28*
               25* 30* 35*
                   36* 42*
                       49*

Cf. A027424, A333996.

A334454 := proc(n)
    local dcom,i,j;
    dcom := {} ;
    for i from 1 to n do
        for j from 1 to i do
            if not isprime(i*j) and i*j> 1 then
                dcom := dcom union {i*j} ;
            end if;
        end do:
    end do:
    print(n,dcom) ;
    nops(dcom) ;
end proc:
seq(A334454(n),n=1..70) ; # R. J. Mathar, Oct 02 2020

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

cp's OEIS Frontend

A322967 Square array A(n,k), n >= 1, k >= 1, read by antidiagonals, where A(n,k) is the number of distinct products Product_{j=1..k} b_j with 1 <= b_j<= n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

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

A219729 Sum_{x <= n} largest divisor of x that is <= sqrt(x).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A126959 a(k) = k! * lim_{n->oo} card({ i*j; i=1..k, j=1..n })/n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

PARI

A184677 Number of numbers <= p^2 with largest prime factor <= p, where p is the n-th prime; a(0) = 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A263996 Smallest possible cardinality of the union of the set of pairwise sums and the set of pairwise products from a set of n positive integers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A281505 Numbers of the form y^2 - x^2 such that x^2 + y^2 is a prime and 0 < x < y.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A284988 Number of distinct products i*j*k*l*m for 1 <= i <= j <= k <= l <= m <= n.

Views

A284988 Number of distinct products ijklm for 1 <= i <= j <= k <= l <= m <= n.