|
| |
|
|
A006282
|
|
Sorting numbers: number of comparisons in Batcher's parallel sort.
(Formerly M2447)
|
|
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;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
REFERENCES
|
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
|
|
|
|
FORMULA
|
a(1)=0, a(n) = a(ceiling(n/2)) + a(floor(n/2)) + C(ceiling(n/2), floor(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.
|
|
|
EXAMPLE
|
G.f. = x^2 + 3*x^3 + 5*x^4 + 9*x^5 + 12*x^6 + 16*x^7 + 19*x^8 + 26*x^9 + 31*x^10 + ...
|
|
|
MATHEMATICA
|
c[m_, n_] /; m*n <= 1 = m*n; c[m_, n_] := c[m, n] = c[ Ceiling[m/2], Ceiling[n/2] ] + c[ Floor[m/2], Floor[n/2] ] + Floor[(m + n - 1)/2]; a[1] = 0; a[n_] := a[n] = a[ Ceiling[n/2] ] + a[ Floor[n/2] ] + c[ Ceiling[n/2], Floor[n/2] ]; Table[ a[n], {n, 1, 57}] (* Jean-François Alcover, Jan 19 2012, from formula *)
|
|
|
PROG
|
(PARI) (c(m, n) = local(i, j); i=ceil(m/2); j=ceil(n/2); if( m*n<2, m*n, c(i, j) + c(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) + c(i, j))}; /* Michael Somos, Feb 07 2004 */
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
