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.

Previous Showing 11-13 of 13 results.

A027874 Minimal degree path length of a tree with n leaves.

Original entry on oeis.org

0, 4, 9, 16, 23, 30, 38, 46, 54, 64, 74, 84, 94, 104, 114, 124, 134, 144, 155, 166, 177, 188, 199, 210, 221, 232, 243, 256, 269, 282, 295, 308, 321, 334, 347, 360, 373, 386, 399, 412, 425, 438, 451, 464, 477, 490, 503, 516, 529, 542, 555, 568, 581, 594, 608
Offset: 1

Views

Author

Don Knuth

Keywords

References

  • Theorem 5.4.9L in D. E. Knuth, `The Art of Computer Programming', Volume 3.

Links

Crossrefs

Cf. A003314.

Programs

  • Maple
    a:= n-> (q-> `if`(n>2*3^q, 3*(q+1)*n+2*(n-3^(q+1)),
         3*q*n+4*(n-3^q)))(ilog[3](n)):
seq(a(n), n=1..60);  # Alois P. Heinz, Feb 22 2018
  • Mathematica
    a[n_] := For[q = 0, True, q++, If[2*3^(q-1) <= n <= 3^q, Return[3*q*n + 2*(n-3^q)], If[3^q <= n <= 2*3^q, Return[3*q*n + 4*(n-3^q)]]]]; Array[a, 55] (* Jean-François Alcover, Oct 26 2015 *)

Formula

a(n) = 3*q*n+2*(n-3^q), if 2*3^(q-1)<=n<=3^q; 3*q*n+4*(n-3^q), if 3^q<=n<=2*3^q.

Extensions

More terms from James Sellers

A097384 Total number of comparisons to find each of the values 1 through n using a binary search with 3-way comparisons (less than, equal and greater than), always choosing the mid-most value to compare to.

Original entry on oeis.org

0, 2, 3, 6, 9, 11, 13, 17, 21, 25, 29, 32, 35, 38, 41, 46, 51, 56, 61, 66, 71, 76, 81, 85, 89, 93, 97, 101, 105, 109, 113, 119, 125, 131, 137, 143, 149, 155, 161, 167, 173, 179, 185, 191, 197, 203, 209, 214, 219, 224, 229, 234, 239, 244, 249, 254, 259, 264, 269, 274
Offset: 1

Views

Author

Franklin T. Adams-Watters, Aug 11 2004

Keywords

Comments

Pure binary search with equality.

Examples

			a_5 = 9 = 5 + a_2 + a_2; this is the smallest example where choosing the middle value is not optimal.

References

  • Hsien-Kuei Hwang, S Janson, TH Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint, 2016; http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf. Also Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585

Crossrefs

See A097383 for the sequence with an optimized binary search. A003314 is the sequence with only 2-way comparisons.

Formula

n + a_{floor((n-1)/2)} + a_{ceiling((n-1)/2)}.

A295513 a(n) = n*bil(n) - 2^bil(n) where bil(0) = 0 and bil(n) = floor(log_2(n)) + 1 for n>0.

Original entry on oeis.org

-1, -1, 0, 2, 4, 7, 10, 13, 16, 20, 24, 28, 32, 36, 40, 44, 48, 53, 58, 63, 68, 73, 78, 83, 88, 93, 98, 103, 108, 113, 118, 123, 128, 134, 140, 146, 152, 158, 164, 170, 176, 182, 188, 194, 200, 206, 212, 218, 224, 230, 236, 242, 248, 254, 260, 266, 272, 278
Offset: 0

Views

Author

Peter Luschny, Dec 02 2017

Keywords

Links

Crossrefs

Cf. A001855, A003314, A033156, A054248, A061168, A083652, A097383, A123753, A295508.

Programs

  • Maple
    A295513 := proc(n) local i, s, z; s := -1; i := n-1; z := 1;
while 0 <= i do s := s+i; i := i-z; z := z+z od; s end:
seq(A295513(n), n=0..57);
  • Mathematica
    a[n_] := n IntegerLength[n, 2] - 2^IntegerLength[n, 2];
Table[a[n], {n, 0, 58}]
  • Python
    def A295513(n): return n*(m:=(n-1).bit_length())-(1<Chai Wah Wu, Mar 29 2023

Formula

A001855(n) = a(n) + 1.
A033156(n) = a(n) + 2n.
A003314(n) = a(n) + n.
A083652(n) = a(n+1) + 2.
A061168(n) = a(n+1) - n + 1.
A123753(n) = a(n+1) + n + 2.
A097383(n) = a(n+1) - div(n-1, 2).
A054248(n) = a(n) + n + rem(n, 2).
Previous Showing 11-13 of 13 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.