Advertisement
Guest User

Untitled

a guest
Aug 17th, 2017
125
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.01 KB | None | 0 0
  1. # Description
  2.  
  3. Given a positive integer N, return a set of integers between 0 and N such that every integer is equal to difference of two in the set, modulo N. Make the set as small as you can.
  4.  
  5. For example, given N = 26, you might return the set { 0, 3, 9, 11, 21, 22 }, (which has a size of 6). Every integer is the difference between two (not necessarily unique) integers in this set, modulo 26. For instance, 7 = 3 - 22 (mod 26).
  6.  
  7. It's not good enough to write a program that will eventually complete. You must be able to actually run your program to completion for five-digit values of N. Post (or link to) your output for N = 12345 along with your solution.
  8.  
  9. As far as I know, the size of the optimal (smallest) set is an open question, so your program does not have to be optimal. But it needs to be pretty close. The best I've found for N = 12345 is a set of size 179, so aim for that.
  10.  
  11. # Challenge
  12.  
  13. Find the smallest valid output for N = 123456. Smallest here refers to the size of the set of integers in the output.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement