Jeff Erickson - cp's OEIS frontend

User: Jeff Erickson

Jeff Erickson's wiki page.

Jeff Erickson has authored 5 sequences.

A215476 Minimum number of comparisons needed to find the median of n elements.

Original entry on oeis.org

0, 1, 3, 4, 6, 8, 10, 12, 14, 16, 18, 20, 23

Offset: 1

Jeff Erickson, Aug 12 2012

Dor and Zwick 1999 prove a(n) <= 2.95n + o(n).

Dor and Zwick 2001 prove a(n) >= (2+2^(-80))n - o(n).

D. Dor and U. Zwick, Median selection requires (2+epsilon)n comparisons, SIAM J. Discrete Math 14(3):312-325, 2001.
D. Dor and U. Zwick, Selecting the median, SIAM J. Comput. 28(5):1722-1758, 1999.
D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Sect. 5.3.2.
Kenneth Oksanen, Searching for selection algorithms, Elec. Notes Discrete Math. 27:77, 2006.

William Gasarch, Wayne Kelly and William Pugh, Finding the i-th largest of n for small i,n, ACM SIGACT News, Volume 27, Issue 2, June 1996, pp. 88-96.
Kenneth Oksanen, Selecting the i'th largest of n elements. (last modified April 2005)

Cf. A117627, A360495.

a(n) = A360495(n,ceiling(n/2)). - Paolo Xausa, Apr 09 2023

Added three more terms (from Kenneth Oksanen), Jeff Erickson, Aug 13 2012

A089604 "3-lazy binary" representation of n: to increment, add one to the last digit, then "carry" the rightmost 3 (replace 03->11, 13->21, or 23->31).

Original entry on oeis.org

0, 1, 2, 11, 12, 21, 22, 31, 112, 121, 122, 131, 212, 213, 222, 231, 312, 321, 1122, 1131, 1212, 1221, 1222, 1231, 1312, 1321, 2122, 2131, 2212, 2221, 2222, 2231, 2312, 2321, 3122, 3131, 3212, 3221, 11222

Offset: 0

Jeff Erickson, Dec 31 2003

Obvious generalization of A089591 and A089600.

Edited by Charles R Greathouse IV, Aug 03 2010

A089601 Interleaving of A089591 and A089600.

Original entry on oeis.org

0, 0, 1, 1, 2, 10, 11, 11, 12, 20, 21, 101, 102, 110, 111, 111, 112, 120, 121, 201, 202, 210, 211, 1011, 1012, 1020, 1021, 1101, 1102, 1110, 1111, 1111, 1112, 1120, 1121, 1201, 1202, 1210, 1211, 2011, 2012, 2020, 2021, 2101, 2102, 2110, 2111, 10111

Offset: 0

Jeff Erickson, Dec 31 2003

Cf. A089591, A089600.

A089591 := proc(n) option remember ; local nhalf ; if n <= 1 then RETURN(n) ; else nhalf := floor(n/2) ; if n mod 2 = 1 then RETURN(10*A089591(nhalf) +1) ; else RETURN(10*(A089591(nhalf-1)+1)) ; fi ; fi ; end: A089600 := proc(n) option remember ; local nhalf ; nhalf := floor(n/2) ; if n <= 1 then RETURN(n) ; else if n mod 2 = 1 then RETURN(10*A089600(nhalf) +1) ; else RETURN(10*A089591(nhalf-1)+2) ; fi ; fi ; end: A089601 := proc(n) if n mod 2 = 0 then A089600(n/2) ; else A089591((n-1)/2) ; fi ; end: seq(A089601(n),n=0..80) ; # R. J. Mathar, Jul 20 2007

To get a(n), drop last digit from either A089591(n) or A089600(n+1).

More terms from R. J. Mathar, Jul 20 2007

A089600 Another lazy binary representation of n: similar to A089591 except that the single carry is performed before the increment instead of after.

Original entry on oeis.org

0, 1, 2, 11, 12, 21, 102, 111, 112, 121, 202, 211, 1012, 1021, 1102, 1111, 1112, 1121, 1202, 1211, 2012, 2021, 2102, 2111, 10112, 10121, 10202, 10211, 11012, 11021, 11102, 11111, 11112, 11121, 11202, 11211, 12012, 12021, 12102, 12111, 20112

Offset: 0

Jeff Erickson, Dec 31 2003

A089591 := proc(n) option remember ; local nhalf ; if n <= 1 then RETURN(n) ; else nhalf := floor(n/2) ; if n mod 2 = 1 then RETURN(10*A089591(nhalf) +1) ; else RETURN(10*(A089591(nhalf-1)+1)) ; fi ; fi ; end: A089600 := proc(n) option remember ; local nhalf ; nhalf := floor(n/2) ; if n <= 1 then RETURN(n) ; else if n mod 2 = 1 then RETURN(10*A089600(nhalf) +1) ; else RETURN(10*A089591(nhalf-1)+2) ; fi ; fi ; end: for n from 0 to 200 do printf("%d, ",A089600(n)) ; od ; # R. J. Mathar, Mar 11 2007

Let b(n) = A089591(n). Then a(0) = b(0) = 0; b(n) = if n is odd then b((n-1)/2):1 else a(n/2):0; a(n) = if n is odd then a((n-1)/2):1 else b(n/2-1):2.

More terms from R. J. Mathar, Mar 11 2007

A089591 "Lazy binary" representation of n. Also called redundant binary representation of n.

Original entry on oeis.org

0, 1, 10, 11, 20, 101, 110, 111, 120, 201, 210, 1011, 1020, 1101, 1110, 1111, 1120, 1201, 1210, 2011, 2020, 2101, 2110, 10111, 10120, 10201, 10210, 11011, 11020, 11101, 11110, 11111, 11120, 11201, 11210, 12011, 12020, 12101, 12110, 20111

Offset: 0

Jeff Erickson, Dec 29 2003

Let a(0) = 0 and construct a(n) from a(n-1) by (i) incrementing the rightmost digit and (ii) if any digit is 2, replace the rightmost 2 with a 0 and increment the digit immediately to its left. (Note that changing "if" to "while" in this recipe gives the standard binary representation of n, A007088(n)).
Equivalently, a(2n+1) = a(n):1 and a(2n+2) = b(n):0, where b(n) is obtained from a(n) by incrementing the least significant digit and : denotes string concatenation.
If the digits of a(n) are d_k, d_{k-1}, ..., d_2, d_1, d_0, then n = Sum_{i=0..k} d_i*2^i, just as in standard binary notation.  The difference is that here we are a bit lazy, and allow a few digits to be 2's. The number of 2's in a(n) appears to be A037800(n+1). - N. J. A. Sloane, Jun 03 2023
Every pair of 2's is separated by a 0 and every pair of significant 0's is separated by a 2.
a(n) has exactly floor(log_2((n+2)/3))+1 digits [cf. A033484] and their sum is exactly floor(log_2(n+1)) [A000523].
The i-th digit of a(n) is ceiling( floor( ((n+1-2^i) mod 2^(i+1))/2^(i-1) ) / 2).
A137951 gives values of terms interpreted as ternary numbers, a(n)=A007089(A137951(n)). - Reinhard Zumkeller, Feb 25 2008

			a(8) = 120 -> 121 -> 201 = a(9); a(9) = 201 -> 202 -> 210 = a(10).

Gerth S. Brodal, Worst-case efficient priority queues, SODA 1996.
Michael J. Clancy and D. E. Knuth, A programming and problem-solving seminar, Technical Report STAN-CS-77-606, Department of Computer Science, Stanford University, Palo Alto, 1977.
Haim Kaplan and Robert E. Tarjan, Purely functional representations of catenable sorted lists, STOC 1996.
Chris Okasaki, Purely Functional Data Structures, Cambridge, 1998.

R. Zumkeller, Table of n, a(n) for n = 0..10000

Cf. A000523, A033484, A072998, A024629, A089600, A089601, A089604, A037800.

A158582: lazy binary different from regular binary, A089633: lazy binary and regular binary agree.

A089591 := proc(n) option remember ; local nhalf ; if n <= 1 then RETURN(n) ; else nhalf := floor(n/2) ; if n mod 2 = 1 then RETURN(10*A089591(nhalf) +1) ; else RETURN(10*(A089591(nhalf-1)+1)) ; fi ; fi ; end: for n from 0 to 200 do printf("%d, ",A089591(n)) ; od ; # R. J. Mathar, Mar 11 2007

a[n_] := a[n] = Module[{nhalf}, If[n <= 1, Return[n], nhalf = Floor[n/2]; If[Mod[n, 2]==1, Return[10*a[nhalf]+1], Return[10*(a[nhalf-1]+1)]]]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jan 19 2016, after R. J. Mathar *)

More terms from R. J. Mathar, Mar 11 2007
Edited by Charles R Greathouse IV, Apr 30 2010
Edited by N. J. A. Sloane, Jun 03 2023

cp's OEIS Frontend

User: Jeff Erickson

A215476 Minimum number of comparisons needed to find the median of n elements.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A089604 "3-lazy binary" representation of n: to increment, add one to the last digit, then "carry" the rightmost 3 (replace 03->11, 13->21, or 23->31).

Views

Author

Keywords

Comments

Extensions

A089601 Interleaving of A089591 and A089600.

Views

Author

Keywords

Crossrefs

Programs

Maple

Formula

Extensions

A089600 Another lazy binary representation of n: similar to A089591 except that the single carry is performed before the increment instead of after.

Views

Author

Keywords

Programs

Maple

Formula

Extensions

A089591 "Lazy binary" representation of n. Also called redundant binary representation of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions