A181625 Problem 17 in Knuth's Art of Computer Programming, vol. 1, section 1.3.3 asks which is the average length L(k) of the cycles among the permutations on k elements. The n-th term of this sequence is the least k such that L(k) >= n.

1, 5, 9, 13, 18, 23, 28, 33, 39, 44, 50, 56, 62, 68, 74, 80, 86, 92, 99, 105, 112, 118, 125, 131, 138, 145, 152, 159, 165, 172, 179, 186, 193, 200, 207, 215, 222, 229, 236, 243, 251, 258, 265, 273, 280, 287, 295, 302, 310, 317, 325, 332, 340, 348, 355

Offset

1,2

Comments

For a given k, k >= a(n), k < a(n+1), the cycles denoting the permutations on k elements have average length L(k), L(k) >= n, L(k) < n+1.

Is this the same as A088907? [From R. J. Mathar, Nov 03 2010]

Links

Table of n, a(n) for n=1..55.

W. Bomfim, Image

Wikipedia, Harmonic number

calculator.runiter.com, Freeware graphing-calculator

ttmath, C++ multiprecision math software

Example

a(1) = 1 since the unique cycle denoting the permutations of one object A, is (A). The length of (A) is 1 and 1 >= 1.
a(8) = 33 because L(k) = A000027(k)*A002805(k)/A001008(k) so L(32) = 7.88... and L(33) = 8.07... .
Click the first link to see image showing values of L(k).

Prog

(C)
#include <iostream>
#include <C:\Wirth\Wirth15_2\ttmath-0.9.2-src/ttmath-0.9.2/ttmath/ttmath.h>
using namespace std;
int main(){
const unsigned int nMaxTermos = 60;
typedef ttmath::Big<TTMATH_BITS(32), TTMATH_BITS(7*32)> BigType; // See the ttmath link.
unsigned int n = 1;
BigType k = 1, H = /* =1/k*/ 1, average, one = 1;
do{ average = k / H;
....if(average >= n){
........cout << k << ", ";
........n++; }
....k = k + 1; H = H + one/k;
....}while(n < nMaxTermos);
return 0;
}

Crossrefs

Cf. A002805, A001008.

Sequence in context: A314724 A314725 A314726 * A314727 A314728 A314729

Adjacent sequences: A181622 A181623 A181624 * A181626 A181627 A181628

Keyword

nonn

Author

Washington Bomfim, Nov 02 2010

Extensions

Edited by Washington Bomfim, Nov 09 2010

Status

approved