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. 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 area-time complexity of binary multiplication, J. ACM 28 (1981), 521-534.  Corrigendum: ibid 29 (1982), 904.

LINKS

Richard P. Brent and Jonathan Webster, Table of n, a(n) for n = 0..28

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.

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

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

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 October 18 12:24 EDT 2018. Contains 316321 sequences. (Running on oeis4.)