

A027417


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


3



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

This is a subsequence of A027384.


REFERENCES

R. P. Brent and H. T. Kung, The areatime complexity of binary multiplication, J. ACM 28 (1981), 521534. Corrigendum: ibid 29 (1982), 904.


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


FORMULA

a(n) = A027384(2^n1).  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 *)


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



