This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 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. 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. 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 Cf. A003075. First differences are in A083742. Sequence in context: A287105 A003075 A061562 * A086845 A243205 A259368 Adjacent sequences:  A006279 A006280 A006281 * A006283 A006284 A006285 KEYWORD nonn,easy,nice AUTHOR 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 15 22:25 EDT 2019. Contains 328038 sequences. (Running on oeis4.)