Cody

Problem 46681. Determine the kth Primitive Root of Unity

Solution 3120386

Submitted on 8 Oct 2020 by Tim
  • Size: 89
  • This is the leading solution.
This solution is locked. To view this solution, you need to provide a solution of the same size or smaller.

Test Suite

Test Status Code Input and Output
1   Pass
n=100000; k=1024; p=[12289,13313,15361,18433,19457,25601,37889,39937,40961,50177,58369,59393,61441,64513,65537,70657,76801,79873,80897,83969,86017,87041,95233]; r=[49,7,84,159,5,31,95,143,40,35,29,9,21,156,431,53,231,230,6,329,82,30,223]; [prime_numbers, primitive_roots] = primitiveKthRootofUnity(n,k) assert(isequal(prime_numbers,p)) assert(isequal(primitive_roots,r))

prime_numbers = Columns 1 through 14 12289 13313 15361 18433 19457 25601 37889 39937 40961 50177 58369 59393 61441 64513 Columns 15 through 23 65537 70657 76801 79873 80897 83969 86017 87041 95233 primitive_roots = 49 7 84 159 5 31 95 143 40 35 29 9 21 156 431 53 231 230 6 329 82 30 223

2   Pass
n=10000; k=256; p=[257,769,3329,7681,7937,9473]; r=[3,7,17,198,71,88]; [prime_numbers, primitive_roots] = primitiveKthRootofUnity(n,k) assert(isequal(prime_numbers,p)) assert(isequal(primitive_roots,r))

prime_numbers = 257 769 3329 7681 7937 9473 primitive_roots = 3 7 17 198 71 88

3   Pass
n=10000; k=210; p=[211,421,631,1051,1471,2311,2521,2731,3361,3571,4201,4621,4831,5881,6091,6301,7351,7561,8191,8821,9241,9661,9871]; r=[2,4,27,3,12,135,39,46,38,139,9,99,96,51,17,152,86,118,46,215,184,148,181]; [prime_numbers, primitive_roots] = primitiveKthRootofUnity(n,k) assert(isequal(prime_numbers,p)) assert(isequal(primitive_roots,r))

prime_numbers = Columns 1 through 14 211 421 631 1051 1471 2311 2521 2731 3361 3571 4201 4621 4831 5881 Columns 15 through 23 6091 6301 7351 7561 8191 8821 9241 9661 9871 primitive_roots = 2 4 27 3 12 135 39 46 38 139 9 99 96 51 17 152 86 118 46 215 184 148 181