Statistics

Problem Statement for "UGroupOrder"

Problem Statement

Two integers are relatively prime if they have no common factors other than 1. For example, 8 and 6 are not relatively prime since they are both divisible by 2. 27 and 10 are relatively prime since they have no common factors other than 1. Note that 1 is relatively prime to all numbers.

The Nth U-group is a special group of integers denoted U(N). An integer B is in U(N) if:
1) 0 < B < N
2) B is relatively prime to N

All arithmetic done in U(N) is performed modulo N. This means:
If C and D are in U(N) then: C*D means (C*D) mod N

The order of an element K in a U-group U(N) is the smallest positive integer E such that:
(K^E) mod N = 1
where ^ denotes exponentiation
In other words, how ever many times you have to multiply K times itself mod N to get 1. In a U-group, every element will have a finite order.

Given N you are going to return the order of each element in U-group U(N).
For example:
N = 8
U(N) = {1,3,5,7}
Orders = {1,2,2,2} since
(1^1) mod 8 = 1 mod 8 = 1
(3^2) mod 8 = (3*3) mod 8 = 9 mod 8 = 1
(5^2) mod 8 = (5*5) mod 8 = 25 mod 8 = 1
(7^2) mod 8 = (7*7) mod 8 = 49 mod 8 = 1
See examples for further clarification.

Create a class UGroupOrder that contains the method findOrders, which takes an int N and returns a int[] containing the order of each corresponding element in U(N).

Definition

Class:
UGroupOrder
Method:
findOrders
Parameters:
int
Returns:
int[]
Method signature:
int[] findOrders(int N)
(be sure your method is public)

Notes

  • The index of each returned element corresponds to the elements of U(N). The first element of U(N) corresponds to the first element in the return value. The second element of U(N) corresponds to the second element in the returned value ...
  • Note that (a*b) mod N = ((a mod N)*(b mod N)) mod N

Constraints

  • N will be between 2 and 51 inclusive

Examples

  1. 9

    Returns: { 1, 6, 3, 6, 3, 2 }

    1^1 mod 9 = 1 2^6 mod 9 = 1 4^3 mod 9 = 1 5^6 mod 9 = 1 7^3 mod 9 = 1 8^2 mod 9 = 1

  2. 8

    Returns: { 1, 2, 2, 2 }

    This is the example given in the problem statement.

  3. 15

    Returns: { 1, 4, 2, 4, 4, 2, 4, 2 }

  4. 51

    Returns: { 1, 8, 4, 16, 16, 8, 16, 16, 4, 16, 2, 8, 16, 16, 16, 8, 8, 16, 16, 16, 8, 2, 16, 4, 16, 16, 8, 16, 16, 4, 8, 2 }

  5. 10

    Returns: { 1, 4, 4, 2 }

  6. 2

    Returns: { 1 }

  7. 3

    Returns: { 1, 2 }

  8. 50

    Returns: { 1, 20, 4, 10, 5, 20, 20, 10, 5, 20, 20, 10, 5, 20, 20, 10, 5, 4, 20, 2 }

  9. 49

    Returns: { 1, 21, 42, 21, 42, 14, 7, 21, 42, 21, 42, 14, 7, 21, 42, 3, 6, 14, 7, 21, 42, 21, 42, 14, 7, 3, 6, 21, 42, 14, 7, 21, 42, 21, 42, 14, 7, 21, 42, 21, 42, 2 }

  10. 48

    Returns: { 1, 4, 2, 4, 4, 2, 4, 2, 2, 4, 2, 4, 4, 2, 4, 2 }

  11. 47

    Returns: { 1, 23, 23, 23, 46, 23, 23, 23, 23, 46, 46, 23, 46, 23, 46, 23, 23, 23, 46, 46, 23, 46, 46, 23, 23, 46, 23, 23, 46, 46, 46, 23, 46, 23, 46, 23, 23, 46, 46, 46, 46, 23, 46, 46, 46, 2 }

  12. 46

    Returns: { 1, 11, 22, 22, 11, 22, 11, 22, 22, 22, 22, 11, 11, 11, 11, 22, 11, 22, 11, 11, 22, 2 }

  13. 39

    Returns: { 1, 12, 6, 4, 12, 4, 6, 12, 2, 3, 6, 12, 12, 3, 6, 2, 12, 6, 4, 12, 4, 6, 12, 2 }

  14. 33

    Returns: { 1, 10, 5, 10, 10, 10, 2, 10, 10, 5, 10, 10, 10, 2, 5, 10, 10, 10, 5, 2 }

  15. 27

    Returns: { 1, 18, 9, 18, 9, 6, 3, 18, 9, 18, 9, 6, 3, 18, 9, 18, 9, 2 }

  16. 32

    Returns: { 1, 8, 8, 4, 4, 8, 8, 2, 2, 8, 8, 4, 4, 8, 8, 2 }

  17. 17

    Returns: { 1, 8, 16, 4, 16, 16, 16, 8, 8, 16, 16, 16, 4, 16, 8, 2 }

  18. 40

    Returns: { 1, 4, 4, 2, 2, 4, 4, 2, 2, 4, 4, 2, 2, 4, 4, 2 }

  19. 4

    Returns: { 1, 2 }

  20. 16

    Returns: { 1, 4, 4, 2, 2, 4, 4, 2 }

  21. 51

    Returns: { 1, 8, 4, 16, 16, 8, 16, 16, 4, 16, 2, 8, 16, 16, 16, 8, 8, 16, 16, 16, 8, 2, 16, 4, 16, 16, 8, 16, 16, 4, 8, 2 }

  22. 47

    Returns: { 1, 23, 23, 23, 46, 23, 23, 23, 23, 46, 46, 23, 46, 23, 46, 23, 23, 23, 46, 46, 23, 46, 46, 23, 23, 46, 23, 23, 46, 46, 46, 23, 46, 23, 46, 23, 23, 46, 46, 46, 46, 23, 46, 46, 46, 2 }

  23. 37

    Returns: { 1, 36, 18, 18, 36, 4, 9, 12, 9, 3, 6, 9, 36, 12, 36, 9, 36, 36, 36, 36, 18, 36, 12, 36, 18, 3, 6, 18, 12, 18, 4, 36, 9, 9, 36, 2 }

  24. 50

    Returns: { 1, 20, 4, 10, 5, 20, 20, 10, 5, 20, 20, 10, 5, 20, 20, 10, 5, 4, 20, 2 }

  25. 49

    Returns: { 1, 21, 42, 21, 42, 14, 7, 21, 42, 21, 42, 14, 7, 21, 42, 3, 6, 14, 7, 21, 42, 21, 42, 14, 7, 3, 6, 21, 42, 14, 7, 21, 42, 21, 42, 14, 7, 21, 42, 21, 42, 2 }

  26. 51

    Returns: { 1, 8, 4, 16, 16, 8, 16, 16, 4, 16, 2, 8, 16, 16, 16, 8, 8, 16, 16, 16, 8, 2, 16, 4, 16, 16, 8, 16, 16, 4, 8, 2 }

  27. 47

    Returns: { 1, 23, 23, 23, 46, 23, 23, 23, 23, 46, 46, 23, 46, 23, 46, 23, 23, 23, 46, 46, 23, 46, 46, 23, 23, 46, 23, 23, 46, 46, 46, 23, 46, 23, 46, 23, 23, 46, 46, 46, 46, 23, 46, 46, 46, 2 }

  28. 37

    Returns: { 1, 36, 18, 18, 36, 4, 9, 12, 9, 3, 6, 9, 36, 12, 36, 9, 36, 36, 36, 36, 18, 36, 12, 36, 18, 3, 6, 18, 12, 18, 4, 36, 9, 9, 36, 2 }

  29. 50

    Returns: { 1, 20, 4, 10, 5, 20, 20, 10, 5, 20, 20, 10, 5, 20, 20, 10, 5, 4, 20, 2 }

  30. 49

    Returns: { 1, 21, 42, 21, 42, 14, 7, 21, 42, 21, 42, 14, 7, 21, 42, 3, 6, 14, 7, 21, 42, 21, 42, 14, 7, 3, 6, 21, 42, 14, 7, 21, 42, 21, 42, 14, 7, 21, 42, 21, 42, 2 }

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.
This problem was used for: