login
This site is supported by donations to The OEIS Foundation.

 

Logo


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.

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.

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

N. J. A. Sloane.

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.

License Agreements, Terms of Use, Privacy Policy. .

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