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,2

Comments

This is a subsequence of A027384.

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.

Formula

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

Example

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

Mathematica

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

Prog

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

Crossrefs

Cf. A027384, A027424.

Sequence in context: A300451 A212961 A000697 * A134063 A087448 A289449

Adjacent sequences: A027414 A027415 A027416 * A027418 A027419 A027420

Keyword

nonn,hard

Author

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

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

Status

approved