|
|
A027417
|
|
Number of distinct products i*j 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
|
|
|
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
|
|
|
FORMULA
|
|
|
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
|
|
|
|