cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-6 of 6 results.

A064038 Numerator of average number of swaps needed to bubble sort a string of n distinct letters.

Original entry on oeis.org

0, 1, 3, 3, 5, 15, 21, 14, 18, 45, 55, 33, 39, 91, 105, 60, 68, 153, 171, 95, 105, 231, 253, 138, 150, 325, 351, 189, 203, 435, 465, 248, 264, 561, 595, 315, 333, 703, 741, 390, 410, 861, 903, 473, 495, 1035, 1081, 564, 588, 1225, 1275, 663, 689, 1431, 1485, 770
Offset: 1

Views

Author

Antti Karttunen, Aug 23 2001

Keywords

Comments

Denominators are given by the simple periodic sequence [1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, ...] (= A014695) thus we get an average of 1/2, 3/2, 3, 5, 15/2, 21/2, 14, 18, etc. swappings required to bubble sort a string of 2, 3, 4, 5, 6, ... letters.

References

  • E. Reingold, J. Nievergelt and N. Deo, Combinatorial Algorithms, Prentice-Hall, 1977, section 7.1, p. 287.

Links

Crossrefs

Cf. A014695 (denominators), A190186, A190187, A350660.
Cf. A000217, A001809, A007742, A014634, A026741, A033567, A033991, A060819, A061041.

Programs

  • Magma
    [Numerator(n*(n-1)/4): n in [1..100]]; // G. C. Greubel, Sep 21 2018
  • Maple
    [seq(numer((n*(n-1))/4), n=1..120)];
  • Mathematica
    f[n_] := Numerator[n (n - 1)/4]; Array[f, 56]
f[n_] := n/GCD[n, 4]; Array[f[#] f[# - 1] &, 56]
LinearRecurrence[{3,-6,10,-12,12,-10,6,-3,1},{0,1,3,3,5,15,21,14,18},80] (* Harvey P. Dale, Jan 23 2023 *)
  • PARI
    vector(100, n, numerator(n*(n-1)/4)) \\ G. C. Greubel, Sep 21 2018

Formula

a(n) = numerator(A001809(n)/(n!)).
a(4n) = A033991(n).
a(4n+1) = A007742(n).
a(4n+2) = A014634(n).
a(4n+3) = A033567(n+1).
a(n+1) = A061041(8*n-4). - Paul Curtz, Jan 03 2011
G.f.: -x^2*(1+4*x^3+x^6) / ( (x-1)^3*(1+x^2)^3 ). - R. J. Mathar, Jan 03 2011
a(n+1) = A060819(n)*A060819(n+1).
a(n+1) = A000217(n)/(period 4:repeat 2,1,1,2=A014695(n+2)=A130658(n+3)).
a(n) = 3*a(n-4) -3*a(n-8) +a(n-12). - Paul Curtz, Mar 04 2011
a(n) = +3*a(n-1) -6*a(n-2) +10*a(n-3) -12*a(n-4) +12*a(n-5) -10*a(n-6) +6*a(n-7) -3*a(n-8) +1*a(n-9). - Joerg Arndt, Mar 04 2011
a(n+1) = A026741(A000217(n)). - Paul Curtz, Apr 04 2011
a(n) = numerator(Sum_{k=0..n-1} k/2). - Arkadiusz Wesolowski, Aug 09 2012
a(n) = n*(n-1)*(3-i^(n*(n-1)))/8, where i=sqrt(-1). - Bruno Berselli, Oct 01 2012, corrected by Vaclav Kotesovec, Aug 09 2022
Sum_{n>=2} 1/a(n) = 4 - Pi/2. - Amiram Eldar, Aug 09 2022
E.g.f.: x^2*(3*exp(x) + cos(x) + sin(x))/8. - Stefano Spezia, Aug 23 2025

A190187 Denominator of expression W_n occurring in analysis of bubble sort.

Original entry on oeis.org

1, 1, 3, 6, 15, 90, 630, 720, 45360, 64800, 4989600, 59875200, 778377600, 1556755200, 163459296000, 373621248000, 44460928512000, 800296713216000, 15205637551104000, 3949516247040000, 6386367771463680000, 20071441567457280000, 3231502092360622080000, 5965850016665763840000, 1938901255416373248000000, 7201633234403672064000000
Offset: 1

Views

Author

N. J. A. Sloane, May 05 2011

Keywords

Examples

			1, 2, 10/3, 29/6, 97/15, 739/90, 6331/630, 8617/720, 633127/45360, 1037497/64800, ...

References

  • D. E. Knuth, The Art of Computer Programming, Vol. 3, Section 5.2.2, p. 129.

Links

Crossrefs

Cf. A190186.

Programs

  • Maple
    W:=proc(n) local t1,r,s;
t1:=add( add(s!*r^(n-s), s=r+1..n), r=0..n-1);
t1/n!;
end;
  • Mathematica
    Denominator[Table[n! + Sum[ Sum[s!*k^(n - s), {s, k + 1, n}], {k, 1, n - 1}]/n!, {n, 1, 50}]] (* G. C. Greubel, Dec 28 2017 *)
  • PARI
    for(n=1,30, print1(denominator(1 + sum(k=1,n-1, sum(s=k+1, n, s!*k^(n-s)))/n!), ", ")) \\ G. C. Greubel, Dec 28 2017

Formula

W_n = Sum_{r=0..(n-1)}( Sum_{s=(r+1)..n} s!*r^(n-s) )/n!.
W_n = denominator(A190194(n)/n!).

A190194 a(n) = Sum_{r=0..n-1} Sum_{s=r+1..n} s! * r^(n-s).

Original entry on oeis.org

0, 1, 4, 20, 116, 776, 5912, 50648, 482552, 5065016, 58099832, 723315128, 9715154552, 140051879096, 2157103991672, 35355232693688, 614453167841912, 11287370521073336, 218535622980161912, 4447889360078673848, 94944254697268017272, 2120984032794061422776, 49489160848954807154552, 1203943675008917425902008, 30486416629523244528307832
Offset: 0

Views

Author

N. J. A. Sloane, May 05 2011

Keywords

Comments

The expression a(n)/n! = A190186/A190187 arises in the analysis of bubble sort [Knuth].

References

  • D. E. Knuth, The Art of Computer Programming, Vol. 3, Section 5.2.2, p. 129.

Links

Crossrefs

Cf. A190186, A190187.

Programs

  • Maple
    f:=proc(n) local t1,r,s;
t1:=add( add(s!*r^(n-s), s=r+1..n), r=0..n-1);
end;
  • Mathematica
    Join[{0}, Table[Sum[n! + Sum[s!*k^(n - s), {s, k + 1, n - 1}], {k, 0, n - 1}], {n, 1, 50}]] (* G. C. Greubel, Dec 28 2017 *)
  • PARI
    for(n=0,30, print1(if(n==0,0, sum(k=0,n-1, n! + sum(s=k+1,n-1, s!*k^(n-s)))), ", ")) \\ G. C. Greubel, Dec 28 2017

A190184 Decimal expansion of sqrt(1+x+sqrt(1+2*x)), where x=sqrt(2/3).

Original entry on oeis.org

1, 8, 5, 4, 4, 9, 3, 6, 3, 0, 0, 4, 2, 5, 5, 8, 2, 6, 3, 6, 8, 3, 6, 4, 0, 1, 3, 2, 4, 5, 2, 7, 7, 8, 4, 7, 7, 7, 7, 8, 2, 7, 6, 9, 5, 4, 6, 6, 9, 8, 2, 5, 0, 1, 4, 1, 6, 9, 0, 5, 0, 1, 9, 7, 0, 4, 8, 4, 8, 9, 4, 1, 7, 1, 3, 9, 8, 0, 4, 0, 1, 8, 3, 1, 9, 4, 2, 0, 4, 5, 9, 9, 1, 9, 9, 8, 5, 0, 0, 8, 7, 1, 8, 7, 1, 6, 4, 7, 1, 6, 8, 8, 3, 4, 6, 2, 2, 8, 8, 9
Offset: 1

Views

Author

Clark Kimberling, May 05 2011

Keywords

Comments

The rectangle R whose shape (i.e., length/width) is sqrt(1+x+sqrt(1+2x)), where x=sqrt(2/3), can be partitioned into rectangles of shapes sqrt(2) and sqrt(3) in a manner that matches the periodic continued fraction [sqrt(2), sqrt(3), sqrt(2), sqrt(3),...]. R can also be partitioned into squares so as to match the nonperiodic continued fraction [1,1,5,1,6,1,5,1,1,...] at A190185. For details, see A188635.

Examples

			1.854493630042558263683640132452778477778...

Links

Crossrefs

Cf. A190185.

Programs

  • Magma
    [Sqrt(1+Sqrt(2/3)+Sqrt(1+2*Sqrt(2/3)))]; // G. C. Greubel, Dec 28 2017
  • Mathematica
    FromContinuedFraction[{2^(1/2), 3^(1/2), {2^(1/2), 3^(1/2)}}]
FullSimplify[%]
ContinuedFraction[%, 100]  (* A190185 *)
RealDigits[N[%%, 120]]      (* A190186 *)
N[%%%, 40]
RealDigits[Sqrt[1+Sqrt[2/3]+Sqrt[1+2*Sqrt[2/3]]], 10, 100][[1]] (* G. C. Greubel, Dec 28 2017 *)
  • PARI
    sqrt(1+sqrt(2/3)+sqrt(1+2*sqrt(2/3))) \\ G. C. Greubel, Dec 28 2017

Extensions

Definition corrected by Bruno Berselli, May 13 2011

A190185 Continued fraction of sqrt(1+x+sqrt(1+2*x)), where x=sqrt(2/3).

Original entry on oeis.org

1, 1, 5, 1, 6, 1, 5, 1, 1, 40, 1, 1, 1, 1, 1, 1, 1, 13, 1, 1, 1, 5, 1, 15, 1, 3, 1, 2, 2, 5, 1, 1, 1, 1, 4, 5, 65, 1, 13, 1, 3, 4, 1, 1, 1, 4, 13, 1, 1, 2, 1, 3, 2, 2, 1, 10, 1, 20, 4, 15, 6, 1, 3, 10, 1, 78, 1, 1, 11, 15, 1, 11, 179, 2, 1, 2, 1, 1, 1, 6, 1, 1, 1, 2, 3, 2, 6, 1, 1, 7, 5, 1, 4, 1, 9, 1, 1, 2, 10, 3
Offset: 1

Views

Author

Clark Kimberling, May 05 2011

Keywords

Comments

Equivalent to the periodic continued fraction [sqrt(2), sqrt(3), sqrt(2), sqrt(3),...]. For geometric interpretations of both continued fractions, see A190184 and A188635.

Links

Crossrefs

Cf. A188635, A190184.

Programs

  • Magma
    ContinuedFraction(Sqrt(1 + Sqrt(2/3) + Sqrt(1 + 2*Sqrt(2/3)))); // G. C. Greubel, Dec 28 2017
  • Mathematica
    FromContinuedFraction[{2^(1/2), 3^(1/2), {2^(1/2), 3^(1/2)}}]
FullSimplify[%]
ContinuedFraction[%, 100]  (* A190185 *)
RealDigits[N[%%, 120]]      (* A190186 *)
N[%%%, 40]
ContinuedFraction[Sqrt[1 + Sqrt[2/3] + Sqrt[1 + 2*Sqrt[2/3]]], 100] (* G. C. Greubel, Dec 28 2017 *)
  • PARI
    contfrac(sqrt(1 + sqrt(2/3) + sqrt(1 + 2*sqrt(2/3)))) \\ G. C. Greubel, Dec 28 2017

Extensions

Definition corrected by Bruno Berselli, May 13 2011

A350660 a(n) is the average number of key comparisons, rounded to the nearest integer, required to sort n records with distinct keys using bubble sort (Algorithm B in Don Knuth's TAOCP Vol. 3).

Original entry on oeis.org

1, 3, 5, 9, 13, 18, 24, 31, 39, 48, 58, 69, 80, 93, 107, 121, 137, 153, 171, 189, 209, 229, 251, 273, 297, 321, 346, 373, 400, 428, 458, 488, 519, 551, 584, 619, 654, 690, 727, 765, 804, 845, 886, 928, 971, 1015, 1060, 1106, 1153, 1201, 1250, 1300, 1351, 1403
Offset: 2

Views

Author

Hugo Pfoertner, Feb 01 2022

Keywords

Examples

			        n        b(n)
        |         |         a(n)=
        |         |      round(b(n))
        |         |           |   b(n)/n^2
        2        1/1          1   0.2500
        3        8/3          3   0.2963
        4       31/6          5   0.3229
        5      128/15         9   0.3413
        6     1151/90        13   0.3552
        7    11309/630       18   0.3663
        8    17303/720       24   0.3755
        9  1408073/45360     31   0.3832
       10  2526503/64800     39   0.3899
      100                  4768   0.4768
     1000                496458   0.4965
    10000                         0.4995
   100000                         0.4999
  1000000                         0.5000

References

  • D. E. Knuth, The Art of Computer Programming Second Edition. Vol. 3, Sorting and Searching. Chapter 5.2.2 Sorting by Exchanging, pages 106-109, 128-130. Addison-Wesley, Reading, MA, 1998.

Crossrefs

Cf. A001620, A190186, A190187, A190194, A350428, A350568, A350569.

Formula

a(n) = round(b(n)).
b(n) = binomial(n+1,2) - A190186(n)/A190187(n).
b(n) = binomial(m,2) - ((m/2)*(log(m) + gamma +log(2)) - 2*sqrt(2*Pi*m)/3 + 49/36 + O(n^(-1/2))) with gamma = A001620, and m = n + 1 (Knuth's asymptotic formula (37), TAOCP vol. 3, page 130).
a(n)/n^2 -> 1/2 for n -> infinity.
Showing 1-6 of 6 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.