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

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

Author

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

Keywords

• nonn
• hard

Comments

This is a subsequence of A027384.

Examples

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

References

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

Links

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

Crossrefs

Cf. A027384, A027424.

Programs

Mathematica

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

Python

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

Formula

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

Extensions

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