place vials in your centrifuge This question originates in this reddit thread by reddit user taho_teg but it is expanded to a more general 'puzzle'.

You have a centrifuge with 24 holes for the vials uniformly distributed in a circle around the central axis. If you now have a number of vials and you want to start the centrifuge, you need to make sure that they are placed in a balanced manner. The only numbers of vials you cannot balance are 1 and 23. You can for example balance 4 obviously, but you can also balance 5 by making a 'triangle' with 3 vials and placing the other two on two opposite sites.

Goal

You have to write a program that accepts the number of holes (that are uniformly distributed in a circle around the rotating axis) of your centrifuge as input, and that outputs a list of numbers of vials that cannot be balanced in the centrifuge.

You have to do the calculation and cannot just hardcode the precomputed solutions.

Input and output have to be implemented in a way so that the program code does not have to be changed for calling the program for different inputs. It is also acceptable to write a function (or a similar construct in your language) that can be called via a console.

Be also aware that if you have 6 holes in your centrifuge, you can centrifuge 2 and 3 vials, but you cannot balance 5 since the 'triangle' and the opposite two will overlap at one point. Another example would be for n=15 you cannot balance 11 vials, you can balance 6 and 5 vials, but the combination of those solutions will overlap (this is of course not yet the criterion that it is impossible to do so).

Update

It seems some people did not understand the given example, so I made a graphic here. PLEASE write a short description of how your algorithm works as well as some example outputs for verification. Please include following examples:

n = 1, 6, 10, 24, 63, 100 = 10^2, 163 (prime), 40320 = 8!, 65536=2^2^2^2^2, 105953 (prime)


Note that 40320 and 65536 will produce huge lists, it will perhaps be a good idea to only indicate the length of those lists.

If you know some interesting numbers to add to that list please let me know!
The algorithm should work at least up to n = 1'000'000.


Example outputs:

These are some example outputs-but perhaps faulty because I just calculated them manually.

1: 1
2: 1
3: 1,2
4: 1,3
5: 1,2,3,4
6: 1,5
7: 1,2,3,4,5,6
8: 1,3,5,7
9: 1,2,4,5,7,8
10:1,3,7,9
11:1,2,3,4,5,6,7,8,9,10
12:1,11
13:1,2,3,4,5,6,7,8,9,10,11,12
14:1,3,5,9,11,13
15:1,2,4,7,8,11,13,14


Hint

If you have a centrifuge with n holes, and you cannot balance e.g. 6 vials, you will also not be able to blance n-6 vials - it is basically the same task to balance m vials on an empty centrifuge or to balance a filled centrifuge by taking away m vials. So you if you have the number m in your list you will also have to include n-m.
Sage – 102 104/115

Why use number theory, when there is brute force?

v=lambda n:[j for j in range(n+1)if all(sum(e^(i*2*I*pi/n)for i in c)for c in Combinations(range(n),j))]


For a given number of vials, this goes over all ways to position the vials and calculates their center of mass by using complex arithmetics. If the center of mass is zero for none of these ways, the number is returned.

Unfortunately, this does not work in certain cases (10,14), because Sage fails to simplify some expressions to zero (which may be related to this bug). One could regard this as a flaw of the interpreter and not the program and still say that the algorithm and program are fine. 

The following 113-character alternative relies on floats instead of symbols and does not suffer from these problems:

v=lambda n:[j for j in range(n+1)if all(abs(sum(exp(i*2j*pi/n)for i in c))&gt;1e-9for c in Combinations(range(n),j))]




Test output of the 113-character version (for n in range(14): print n,v(n)):

0 []
1 [1]
2 [1]
3 [1, 2]
4 [1, 3]
5 [1, 2, 3, 4]
6 [1, 5]
7 [1, 2, 3, 4, 5, 6]
8 [1, 3, 5, 7]
9 [1, 2, 4, 5, 7, 8]
10 [1, 3, 7, 9]
11 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
12 [1, 11]
13 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
14 [1, 3, 5, 9, 11, 13]


I did not want to wait the runtime for higher n.



This originates from the following Python solution. Exact arithmetics and not having to import some modules is quite something.

Python – 173 154 156

from itertools import*
from cmath import*
v=lambda n:[j for j in range(n+1)if all(abs(sum(exp(i*2j*pi/n)for i in c))&gt;1e-9for c in combinations(range(n),j))]


Test output of this variant (for n in range(24): print n,v(n)):

0 []
1 [1]
2 [1]
3 [1, 2]
4 [1, 3]
5 [1, 2, 3, 4]
6 [1, 5]
7 [1, 2, 3, 4, 5, 6]
8 [1, 3, 5, 7]
9 [1, 2, 4, 5, 7, 8]
10 [1, 3, 7, 9]
11 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
12 [1, 11]
13 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
14 [1, 3, 5, 9, 11, 13]
15 [1, 2, 4, 7, 8, 11, 13, 14]
16 [1, 3, 5, 7, 9, 11, 13, 15]
17 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
18 [1, 17]
19 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
20 [1, 3, 17, 19]
21 [1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20]
22 [1, 3, 5, 7, 9, 13, 15, 17, 19, 21]
23 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]
24 [1, 23]


I did not want to wait the runtime for higher n.