Problem Statement
You want to create your own random number generator to create some random unique integers between 1 and a number radix-1, so that if you start working in another language that doesn't have one of these classes, you can port the one you've already written. A quick and easy way to make a random number generator is to take a Base number and raise it to a power called the seed. Then, divide this number by the radix and get the remainder, which you'll call the generator (in other words, generator = (Base^seed)%radix, where '^' denotes exponentiation). Your random number generator will return this generator as your first random number. Subsequent random numbers will be calculated like this: Multiply the previous random number by the generator. Divide this result by the radix, and return the remainder of this division as the next random number (in other words newRandom=(generator*oldRandom)%radix).
Obviously, not every seed will create a full set of random numbers: sometimes they repeat before generating every value between 1 and radix-1(inclusive). This is a bad seed. A good seed will generate every number between 1 and radix-1 (inclusive) before repeating. Your job is to create a function called howManyGoodSeeds that will return the number of good seeds between 1 and radix-1 (inclusive).
Definition
- Class:
- RandomNumberGenerator
- Method:
- howManyGoodSeeds
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int howManyGoodSeeds(int Base, int radix)
- (be sure your method is public)
Notes
- HINT: for finding numbers such as (999^1000)%1001: you won't want to calculate 999^1000 first, for that will overflow an integer. Instead use the following recurrence: (x^n)%m == ((x%m) * ((x^(n-1))%m))%m.
Constraints
- radix will be an integer between 2 and 1000, inclusive.
- Base will be between 1 and radix-1, inclusive.
Examples
1
10
Returns: 0
1 to any power is 1, and 1 will never generate other numbers other than one. Therefore 1 can not produce good seeds.
2
11
Returns: 4
1, 3, 7, 9 are all good seeds: seed=1 means generator = 2^1%11 = 2 and it generates them in this order: [2,4,8,5,10,9,7,3,6,1]. seed=3 means generator = 2^3%11 = 8 and it generates them in this order: [8,9,6,4,10,3,2,5,7,1]. seed=7 means generator = 2^7%11 = 7 and it generates them in this order: [7,5,2,3,10,4,6,9,8,1]. seed=9 means generator = 2^9%11 = 6 and it generates them in this order: [6,3,7,9,10,5,8,4,2,1]. Observe that 1 is at the end of every list. The number 10 always being the 5th element in each list is just an artifact of choosing 11 as a radix.
641
991
Returns: 0
3
257
Returns: 128
2
341
Returns: 0
11
101
Returns: 40
4
500
Returns: 0
2
641
Returns: 0
3
641
Returns: 256
5
641
Returns: 0
9
437
Returns: 0
31
971
Returns: 384
93
971
Returns: 384
43
971
Returns: 384
43
733
Returns: 240
89
733
Returns: 0
101
733
Returns: 240
3
7
Returns: 2
5
7
Returns: 2
6
7
Returns: 0
641
1000
Returns: 0
1
2
Returns: 1
3
993
Returns: 0
3
977
Returns: 480
3
257
Returns: 128
888
999
Returns: 0
999
1000
Returns: 0
500
1000
Returns: 0
11
101
Returns: 40
1
2
Returns: 1
641
991
Returns: 0
1
11
Returns: 0
3
1000
Returns: 0
6
8
Returns: 0
2
4
Returns: 0
6
257
Returns: 128