NumPermutationOrders | Topcoder Archive

Problem Statement

Let S = {1, 2,..., n} be a set of positive integers. A permutation on S is a function that takes each element of S to a distinct element of S (i.e., it is one-to-one). The identity permutation takes each element of S to itself. Given a permutation f on S, we can ask how many times f must be applied until we arrive at the identity permutation. The smallest such positive value is called the order of f (i.e., the smallest positive k such that f^k = identity). For example, suppose f behaves as follows (for n=3):

	1->2, 2->1, 3->3

Then applying f twice results in the identity permutation, since every element is taken to itself:

    1->2->1, 2->1->2, 3->3->3

Since applying f once is not the identity permutation, the order of f is 2. Considering all permutations on S, return how many possible orders there are.

Definition

Class:: NumPermutationOrders
Method:: howMany
Parameters:: int
Returns:: long
Method signature:: long howMany(int n)
(be sure your method is public)

Constraints

n will be between 1 and 1000, inclusive.

Examples

```
1
```
```
Returns: 1
```
Here the only permutation is the identity.
```
2
```
```
Returns: 2
```
Here there are two possible permutations: the identity (order 1), and the permutation that swaps 1 and 2 (order 2).
```
3
```
```
Returns: 3
```
Here there are 3! = 6 possible permutations: the identity (order 1), 3 permutations that swap two elements (order 2), and 2 permutations that do not fix any element (order 3).
```
4
```
```
Returns: 4
```
```
10
```
```
Returns: 16
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.