|
Search: id:A006282
|
|
|
| A006282 |
|
Sorting numbers: number of comparisons in Batcher's parallel sort.
(Formerly M2447)
|
|
+0
3
|
|
| 0, 1, 3, 5, 9, 12, 16, 19, 26, 31, 37, 41, 48, 53, 59, 63, 74, 82, 91, 97, 107, 114, 122, 127, 138, 146, 155, 161, 171, 178, 186, 191, 207, 219, 232, 241, 255, 265, 276, 283, 298, 309, 321, 329, 342, 351, 361, 367, 383, 395, 408, 417, 431, 441, 452, 459, 474
(list; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
REFERENCES
|
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
R. W. Floyd and D. E. Knuth, The Bose-Nelson sorting problem, pp. 163-172 of J. N. Srivastava, ed., A Survey of Combinatorial Theory, North-Holland, 1973.
D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 5.3.4, Eq. (10).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=1..1000
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
Index entries for sequences related to sorting
|
|
FORMULA
|
a(1)=0, a(n)=a(ceiling(n/2))+a([ n/2 ])+C(ceiling(n/2), [ n/2 ]), n>1, where the C function is defined in Knuth by C[m,n] = m*n if m*n <=1 and C[m,n] = C[Ceiling[m/2],Ceiling[n/2]] + C[Floor[m/2],Floor[n/2]] + Floor[(m+n-1)/2]] otherwise.
|
|
PROGRAM
|
(PARI) {f(m, n)=local(i, j); i=ceil(m/2); j=ceil(n/2); if(m*n<2, m*n, f(i, j)+f(m\2, n\2)+(m+n-1)\2)} a(n)=local(i, j); i=ceil(n/2); j=floor(n/2); if(n<2, 0, a(i)+a(j)+f(i, j)) (Michael Somos)
|
|
CROSSREFS
|
Cf. A003075.
First differences are in A083742.
Sequence in context: A091785 A003075 A061562 this_sequence A086845 A127722 A060419
Adjacent sequences: A006279 A006280 A006281 this_sequence A006283 A006284 A006285
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
Search completed in 0.002 seconds
|
