TopCoder Statistics - Problem Statement

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

1000

Returns: 3018714402027
182

Returns: 488623
3

Returns: 3
15

Returns: 35
270

Returns: 6987901
323

Returns: 27431758
98

Returns: 16960
430

Returns: 307824977
471

Returns: 709759227
896

Returns: 745408824452
525

Returns: 2008523557
501

Returns: 1274892125
720

Returns: 55894677570
191

Returns: 660655
889

Returns: 676301564345
677

Returns: 28165345366
848

Returns: 379135648951
348

Returns: 50050571
125

Returns: 57199
343

Returns: 44470326
146

Returns: 133123
140

Returns: 105371
377

Returns: 97558561
921

Returns: 1051574721415
756

Returns: 97501548558
715

Returns: 51675405572
478

Returns: 815172700
117

Returns: 40557
502

Returns: 1299559906
159

Returns: 216887
921

Returns: 1051574721415
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
997

Returns: 2902820283286
991

Returns: 2683501004908
983

Returns: 2415584018270
977

Returns: 2231688453890
971

Returns: 2061234357322
967

Returns: 1954641531896
953

Returns: 1621405824525
947

Returns: 1495903486004
941

Returns: 1379723068032
937

Returns: 1307150420390
929

Returns: 1172716951103
919

Returns: 1023254606037
911

Returns: 916932622159
907

Returns: 867848981159
887

Returns: 657687142087
883

Returns: 621968457024
881

Returns: 604785459785
877

Returns: 571818966004
863

Returns: 469365943387
859

Returns: 443493626599
857

Returns: 431053708853
853

Returns: 407203321410
839

Returns: 333209887681
829

Returns: 288427113649
827

Returns: 280176565688
823

Returns: 264372446164
821

Returns: 256779627993
811

Returns: 221877405056
809

Returns: 215453184594
797

Returns: 180514863855
1000

Returns: 3018714402027
997

Returns: 2902820283286
998

Returns: 2940964457767
600

Returns: 7747013059
973

Returns: 2116665185001
999

Returns: 2979577185567
991

Returns: 2683501004908
7

Returns: 9
11

Returns: 20

Statistics

Problem Statement for "NumPermutationOrders"

Problem Statement

Definition

Constraints

Examples