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-4 of 4 results.

A260795 Number of steps required by the Hwang-Deutsch merging algorithm.

Original entry on oeis.org

2, 3, 5, 8, 12, 17, 25, 36, 52, 73, 105, 148, 212, 297, 425, 596, 852, 1193, 1705, 2388, 3412, 4777, 6825, 95556, 13652, 19113, 27305, 38228, 54612, 76457, 109225, 152916, 218452, 305833, 436905, 611668, 873812, 1223337, 1747625, 2446676, 3495252, 4893353, 6990505
Offset: 3

Views

Author

N. J. A. Sloane, Aug 06 2015

Keywords

Links

Crossrefs

Cf. A260794, A200310, A260996, A260997.

Extensions

More terms from Amiram Eldar, May 11 2024

A239100 Solution to the problem of finding the number of comparisons needed for optimal merging of 3 elements with n elements.

Original entry on oeis.org

0, 1, 1, 2, 3, 4, 6, 8, 10, 13, 17, 22, 28, 37, 47, 59, 75, 96, 120, 153, 194, 242, 309, 391, 487, 619, 784, 976, 1241, 1570, 1954, 2485, 3143, 3911, 4971, 6288, 7824, 9945, 12578, 15650, 19893, 25159, 31303, 39787, 50320, 62608, 79577, 100642, 125218, 159157
Offset: 1

Views

Author

N. J. A. Sloane, Mar 24 2014

Keywords

Links

Crossrefs

Cf. A200310, A200111.

Programs

  • PARI
    a(n) = if (n<9, v=[0, 1, 1, 2, 3, 4, 6, 8]; v[n], ndt = n\3; nmt = n%3; if (nmt==0, 43*2^(ndt-2)\7 - 2, if (nmt == 1, 107*2^(ndt-3)\7 - 2, (17*2^ndt-6)\7 - 1))); \\ Michel Marcus, Mar 26 2014
  • Python
    def A239100(n):
    if n <= 8: return (0,1,1,2,3,4,6,8)[n-1]
    r, b = divmod(n,3)
    return ((107<Chai Wah Wu, Mar 28 2023

Formula

For r >= 3, a(3r) = floor(43*2^(r-2)/7)-2,
a(3r+1) = floor(107*2^(r-3)/7)-2,
a(3r+2) = floor((17*2^r-6)/7)-1; initial terms are shown in sequence.
From Chai Wah Wu, Mar 28 2023: (Start)
a(n) = a(n-1) + a(n-3) - a(n-4) + a(n-6) - a(n-7) + 2*a(n-9) - 2*a(n-10) for n > 18.
G.f.: x*(2*x^17 - x^16 - x^15 + x^14 + x^13 - x^12 + 2*x^11 - x^10 + x^8 + x^6 + x^5 + x^3 + x)/((x - 1)*(2*x^3 - 1)*(x^6 + x^3 + 1)). (End)

Extensions

More terms from Michel Marcus, Mar 26 2014

A260794 Number of steps required by R. L. Graham's generalized binary merging algorithm.

Original entry on oeis.org

2, 3, 5, 7, 11, 15, 19, 27, 35, 43
Offset: 3

Views

Author

N. J. A. Sloane, Aug 06 2015

Keywords

Links

Crossrefs

Cf. A260795, A200310.

A200311 Number of comparisons needed for optimal merging of 2 elements with n elements.

Original entry on oeis.org

2, 3, 4, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13
Offset: 1

Views

Author

N. J. A. Sloane, Nov 15 2011

Keywords

References

  • R. L. Graham, On sorting by comparisons, in Proceedings of the ATLAS Symposium, 1971, pp. 263-269; http://www.math.ucsd.edu/~ronspubs/71_07_sorting.pdf.
  • F. K. Hwang and S. Lin, Optimal merging of 2 elements with n elementsw, Acta Informatica, 1 (1971), 145-158.

Links

Crossrefs

Cf. A200310, A239100.

Programs

  • Maple
    s:=[2,3];
for n from 4 to 13 do
  for i from A200310(n-1)+1 to A200310(n) do s:=[op(s),n]; od:
od:

Formula

Let f(i) = A200310(i). Then for i in the range f(n-1)+1 through f(n), a(i) = n.
Showing 1-4 of 4 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.