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