login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 area-time complexity of binary multiplication,  J. ACM 28 (1981),  521-534.  Corrigendum: ibid 29 (1982), 904.

R. P. Brent and C. Pomerance, The multiplication table, and random factored integers, http://maths-people.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://maths-people.anu.edu.au/~brent/pd/multiplication-HK.pdf

LINKS

Table of n, a(n) for n=0..25.

R. P. Brent and H. T. Kung, The area-time complexity of binary multiplication.

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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 22 13:09 EST 2018. Contains 299454 sequences. (Running on oeis4.)