

A027417


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


2



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.
R. P. Brent and C. Pomerance, The multiplication table, and random factored integers, http://mathspeople.anu.edu.au/~brent/pd/multiplication.pdf, 2012.
R. P. Brent, C. Pomerance, Some mysteries of multiplication, and how to generate random factored integers, Slides of a talk given in Feb. 2015; http://mathspeople.anu.edu.au/~brent/pd/multiplicationHK.pdf


LINKS

Table of n, a(n) for n=0..25.
R. P. Brent and H. T. Kung, The areatime complexity of binary multiplication.


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


CROSSREFS

Cf. A027384, A027424.
Sequence in context: A220304 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



