A080804 -id:A080804 - cp's OEIS frontend

A080811 a(1) = 8, a(n)= smallest n-th power obtained by inserting digits anywhere in a(n-1).

8, 81, 68921, 671898241, 67499118303941862584001, 6576499147308118090309591239435044518621593475579845001

Offset: 1

Amarnath Murthy, Mar 22 2003

Cf. A080804, A080805, A080806, A080807, A080808, A080809, A080810, A080812.

buffedStr := proc(n,candid) local f ; if length(n) = 0 then RETURN(true) ; fi ; f := SearchText(substring(n,1),candid) ; if f = 0 then RETURN(false) ; else if buffedStr(substring(n,2..-1),substring(candid,f+1..-1)) = true then RETURN(true) ; else RETURN(false) ; fi ; fi ; end: A080811 := proc(preva,n) local i,tst ; i := 1 ; while true do tst := i^n ; if buffedStr(convert(preva,string),convert(tst,string)) = true then RETURN(tst) ; fi ; i := i+1 ; od: end: an :=8 ; for n from 2 to 15 do an := A080811(an,n) ; end ; # R. J. Mathar, Sep 20 2006

2 more terms from R. J. Mathar, Sep 20 2006

One more term. Sean A. Irvine, Aug 31 2009

A080809 a(1) = 6; thereafter, a(n)= smallest n-th power obtained by inserting digits anywhere in a(n-1).

Original entry on oeis.org

6, 16, 216, 2085136, 62019685191371643, 82626753081964483505319130781618465733184

Offset: 1

Amarnath Murthy, Mar 22 2003

Cf. A080804, A080805, A080806, A080807, A080808, A080810, A080811, A080812.

buffedStr := proc(n,candid) local f ; if length(n) = 0 then RETURN(true) ; fi ; f := SearchText(substring(n,1),candid) ; if f = 0 then RETURN(false) ; else if buffedStr(substring(n,2..-1),substring(candid,f+1..-1)) = true then RETURN(true) ; else RETURN(false) ; fi ; fi ; end: A080809 := proc(preva,n) local i,tst ; i := 1 ; while true do tst := i^n; if buffedStr(convert(preva,string),convert(tst,string)) = true then RETURN(tst) ; fi ; i := i+1 ; od: end: an :=6 ; for n from 2 to 15 do an := A080809(an,n) ; end ; # R. J. Mathar, Sep 20 2006

a(n)=A080514(n), n>1. - R. J. Mathar, Sep 18 2008

More terms from R. J. Mathar, Sep 20 2006

Copied a term from A080514. - Sean A. Irvine, Sep 01 2009

A080810 a(1) = 7, a(n)= smallest n-th power obtained by inserting digits anywhere in a(n-1).

Original entry on oeis.org

7, 576, 17576, 1475789056, 1420778345789277056227207, 149247077443060991182553045537892735703095362592472033442634721

Offset: 1

Amarnath Murthy, Mar 22 2003

			24^2=576. 26^3=17576. 196^4=1475789056. 67687^5=1420778345789277056227207.

Cf. A080804, A080805, A080806, A080807, A080808, A080809, A080811, A080812.

buffedStr := proc(n,candid) local f ; if length(n) = 0 then RETURN(true) ; fi ; f := SearchText(substring(n,1),candid) ; if f = 0 then RETURN(false) ; else if buffedStr(substring(n,2..-1),substring(candid,f+1..-1)) = true then RETURN(true) ; else RETURN(false) ; fi ; fi ; end: A080810 := proc(preva,n) local i,tst ; i := 1 ; while true do tst := i^n ; if buffedStr(convert(preva,string),convert(tst,string)) = true then RETURN(tst) ; fi ; i := i+1 ; od: end: an :=7 ; for n from 2 to 15 do an := A080810(an,n) ; end ; # R. J. Mathar, Sep 20 2006

Corrected and extended by R. J. Mathar, Sep 20 2006

One more term. Sean A. Irvine, Sep 01 2009

A080812 a(1) = 9, a(n)= smallest n-th power obtained by inserting digits anywhere in a(n-1).

Original entry on oeis.org

9, 49, 4096, 3748096, 4932784804069376, 44934932784038660743085694310776796224

Offset: 1

Amarnath Murthy, Mar 22 2003

Essentially the same as A080808.

Cf. A080804 - A080811.

3 more terms from Sean A. Irvine, Sep 06 2009

A360495 Triangle read by rows: T(n,k) is the minimum number of pairwise comparisons needed (in the worst case) to determine the k-th largest of n distinct numbers, for 1 <= k <= n.

Original entry on oeis.org

0, 1, 1, 2, 3, 2, 3, 4, 4, 3, 4, 6, 6, 6, 4, 5, 7, 8, 8, 7, 5, 6, 8, 10, 10, 10, 8, 6, 7, 9, 11, 12, 12, 11, 9, 7, 8, 11, 12, 14, 14, 14, 12, 11, 8, 9, 12, 14, 15, 16, 16, 15, 14, 12, 9, 10, 13, 15, 17, 18, 18, 18, 17, 15, 13, 10, 11, 14, 17, 18, 19, 20, 20, 19, 18, 17, 14, 11

Offset: 1

Paolo Xausa, Feb 09 2023

Also known in the literature as the selection problem, where T(n,k) is usually denoted by V_t(n), with t = k.
Knuth (1998) provides a historical background (the problem arose in 1883, when C. L. Dodgson--alias Lewis Carroll--proposed a better way to design tennis tournaments so that the true second- and third-best players could be determined) and a survey of recent results, including some upper and lower bounds (see Formula section).
No general formula for the exact value of T(n,k) is known, except for specific cases (e.g., k = 1 and k = 2).
Terms are taken from Gasarch, Kelly and Pugh (1996), p. 92, Table 1, and from Oksanen (2005).

			Triangle begins:
  n\k|  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 ...
  ---+-------------------------------------------------
   1 |  0
   2 |  1  1
   3 |  2  3  2
   4 |  3  4  4  3
   5 |  4  6  6  6  4
   6 |  5  7  8  8  7  5
   7 |  6  8 10 10 10  8  6
   8 |  7  9 11 12 12 11  9  7
   9 |  8 11 12 14 14 14 12 11  8
  10 |  9 12 14 15 16 16 15 14 12  9
  11 | 10 13 15 17 18 18 18 17 15 13 10
  12 | 11 14 17 18 19 20 20 19 18 17 14 11
  13 | 12 15 18 20 21 22 23 22 21 20 18 15 12
  14 | 13 16 19 21 23 24  ?  ? 24 23 21 19 16 13
  15 | 14 17 20 23 25  ?  ?  ?  ?  ? 25 23 20 17 14
  ...

Charles L. Dodgson, Lawn Tennis Tournaments: True Method of Assigning Prizes, with a Proof of the Fallacy of the Present Method, Macmillan, London, 1883.
Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd edition, Addison-Wesley, Reading, MA, 1998, pp. 207-216.
J. Schreier, On tournament elimination systems, Mathesis Polska 7, 1932, pp. 154-160 (in Polish).
Hugo Steinhaus, Mathematical Snapshots, Third American Edition, Oxford University Press, New York, 1983, pp. 54-55.

Paolo Xausa, Table of n, a(n) for n = 1..91 (rows 1..13 of triangle, flattened).
Martin Aigner, Selecting the top three elements, Discrete Applied Mathematics, Volume 4, Issue 4, August 1982, pp. 247-267.
Samuel W. Bent and John W. John, Finding the median requires 2n comparisons, STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computing, December 1985, pp. 213-216.
Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest and Robert E. Tarjan, Time bounds for selection, Journal of Computer and System Sciences, Volume 7, Issue 4, 1973, pp. 448-461.
Walter Cunto and J. Ian Munro, Average case selection, STOC '84: Proceedings of the sixteenth annual ACM symposium on Theory of computing, December 1984, pp. 369-375.
Jutta Eusterbrock, Errata to "Selecting the top three elements" by M. Aigner: A result of a computer-assisted proof search, Discrete Applied Mathematics, Volume 41, Issue 2, 26 January 1993, pp. 131-137.
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.
Abdollah Hadian and Milton Sobel, Selecting the t-th Largest Using Binary Errorless Comparisons, Technical Report 121, University of Minnesota, May 1969.
David G. Kirkpatrick, A Unified Lower Bound for Selection and Set Partitioning Problems, Journal of the ACM, Volume 28, Issue 1, January 1981, pp. 150-165.
David G. Kirkpatrick, Closing a Long-Standing Complexity Gap for Selection: V_3(42) = 50, in Brodnik, López-Ortiz, Raman and Viola (eds), Space-Efficient Data Structures, Streams, and Algorithms. Lecture Notes in Computer Science, vol 8066, Springer, Berlin, Heidelberg, 2013, pp. 61-76.
S. S. Kislitsyn, On the selection of the k-th element of an ordered set by pairwise comparisons, Sibirskii Matematicheskii Zhurnal, 1964, Volume 5, Number 3, pp. 557-564 (in Russian).
Kenneth Oksanen, Selecting the i-th largest of n elements, last updated 2005 (local PDF version, with permission).
Wikipedia, Selection algorithm.
Chee K. Yap, New upper bounds for selection, Communications of the ACM, Volume 19, Issue 9, September 1976, pp. 501-508.

Cf. A036604, A080804 (2nd column), A215476, A374236 (row sums).

T(n,1) = T(n,n) = n-1.
T(n,2) = n-2+ceiling(log_2(n)) = A080804(n-1), for n >= 2.
T(n,k) = T(n,n-k+1).
T(n,ceiling(n/2)) = A215476(n).
Some upper bounds:
T(n,k) <= n-k+(k-1)*ceiling(log_2(n-k+2)).
T(n,3) <= n+1+ceiling(log_2((n-1)/4))+ceiling(log_2((n-1)/5)).
T(n,k) <= 15*n-163, for n > 32.
Some lower bounds:
T(n,k) >= n+k-3+Sum_{j=0,k-2} ceiling(log_2((n-k+2)/(k+j))), for 2 <= k <= (n+1)/2.
T(n,k) >= n+m-2*ceiling(sqrt(m)), where m = 2+ceiling(log_2(binomial(n,k)/(n-k+1))).

cp's OEIS Frontend

A080811 a(1) = 8, a(n)= smallest n-th power obtained by inserting digits anywhere in a(n-1).

Views

Author

Keywords

Crossrefs

Programs

Maple

Extensions

A080809 a(1) = 6; thereafter, a(n)= smallest n-th power obtained by inserting digits anywhere in a(n-1).

Views

Author

Keywords

Crossrefs

Programs

Maple

Formula

Extensions

A080810 a(1) = 7, a(n)= smallest n-th power obtained by inserting digits anywhere in a(n-1).

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Extensions

A080812 a(1) = 9, a(n)= smallest n-th power obtained by inserting digits anywhere in a(n-1).

Views

Author

Keywords

Comments

Crossrefs

Extensions

A360495 Triangle read by rows: T(n,k) is the minimum number of pairwise comparisons needed (in the worst case) to determine the k-th largest of n distinct numbers, for 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A080807 a(1) = 3, a(n)= smallest n-th power obtained by inserting digits anywhere in a(n-1).

Views

Author

Keywords

Comments

Crossrefs

Extensions