|
|
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.
|
|
0
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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.
|
|
LINKS
|
|
|
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.
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|