12
\$\begingroup\$

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. 5 vials placed balanced on a 24 hole centrifuge

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.

\$\endgroup\$
19
  • 3
    \$\begingroup\$ Shouldn't we need to have the vials evenly spaced to be balanced? I fail to see how the 5 vials in 24 holes example satisfies this. One "half" of the centrifuge will have more vials than the other half. That sounds like the definition of unbalanced to me. \$\endgroup\$ – Thorn Jul 24 '14 at 22:41
  • 6
    \$\begingroup\$ I think that by "balanced" what is meant is that the centre of mass of the vials is vertically above or below the centre of mass of the centrifuge. \$\endgroup\$ – Peter Taylor Jul 24 '14 at 23:11
  • 2
    \$\begingroup\$ @Thorn you need to think in two dimensions, not one. The coordinates of the first 3 vials are (0,1), (-sqrt(3)/2,-1/2) and (+sqrt(3)/2,-1/2.) The 5 vial arrangement is not symmetric (apart from possibly a mirror plane) but it is balanced. It's quite common for car wheels to have different numbers of spokes and wheelnuts (again, not symmetrical, but fully balanced because the spokes form a balanced set and the nuts form a balanced set.) Google 7 spoke wheel and have a look. \$\endgroup\$ – Level River St Jul 24 '14 at 23:17
  • 2
    \$\begingroup\$ “The algorithm should work at least up to n = 1'000'000.” Just to be sure: Did you really mean the algorithm or did you mean the program? My algorithm works as well for n = 1.000.000 as it does for n = 10. The program however, has some issues. \$\endgroup\$ – Wrzlprmft Jul 25 '14 at 17:06
  • 1
    \$\begingroup\$ @edc65. balanced != symmetrical... so long as you break your vials into sub-groups, where each sub-group is in a symmetrical state, then the sum outward force of all sub-groups will be in a balanced state. \$\endgroup\$ – Eoin Campbell Aug 1 '14 at 11:04
5
\$\begingroup\$

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))>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))>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.

\$\endgroup\$
1
  • \$\begingroup\$ I like the idea of using the complex unit roots! Could you please show some example outputs just for verification? I posted some suggestions. \$\endgroup\$ – flawr Jul 25 '14 at 14:33
4
\$\begingroup\$

Lua - 197

A non brute force method, it creates a list of factors and rules them out. It also rules out numbers that can be gotten with the addition of those factors as long as the greatest factor used is less than the amount of unfilled holes. One is always printed and isn't used in the algorithm.

i=io.read("*n")f={}print(1)for z=2,i do
x=z
if i%x<1 then
table.insert(f,1,x)end
for q=1,#f do
y=f[q]x=x*math.min(1,z%y)while x>=y and x-1~=y and y<=i-z do x=x-y end
end
if x>0 then print(z)end
end

Example output: (some put as ranges so I don't exceed the character limit)

1: 1

6: 1,5

10:1,3,7,9

24:1,23

63:1,2,4,5,8,11,13,17,20,22,23,25,26,29,32,34,38,41,44,47,50,53,58,59,61,62

100:1,3,13,23,33,43,53,63,73,83,93,97,99

163:1-162

40320:1,11,13,17,19,29,31,37,41,43,61,71,73,97,113,121,127,139,157,169,179,181,191,193,209,211,221,223,241,251,253,263,269,271,277,281,289,299,307,313,331,337,347,349,353,361,373,377,379,397,401,403,409,421,431,433,437,439,449,461,467,473,479,481,491,493,499,517,521,523,529,533,541,547,571,577,587,589,593,601,607,613,617,619,631,641,653,659,671,673,683,689,691,697,701,703,709,713,731,733,737,739,751,757,761,769,781,793,811,817,841,851,853,857,859,869,871,877,881,883,907,913,929,937,953,961,971,977,979,989,991,997,1003,1009,1019,1021,1027,1033,1037,1039,1049,1051,1069,1073,1079,1081,1093,1121,1133,1139,1151,1153,1163,1171,1177,1181,1189,1193,1201,1213,1217,1223,1237,1243,1249,1261,1271,1273,1277,1279,1289,1291,1297,1301,1303,1321,1331,1333,1357,1361,1363,1369,1373,1381,1387,1409,1417,1429,1441,1451,1453,1457,1459,1469,1471,1481,1483,1489,1501,1511,1513,1531,1537,1553,1567,1579,1597,1601,1609,1619,1621,1633,1643,1649,1651,1661,1663,1681,1691,1693,1697,1699,1709,1711,1717,1721,1723,1741,1751,1753,1777,1793,1801,1807,1819,1837,1849,1859,1861,1871,1873,1889,1891,1901,1903,1921,1931,1933,1937,1949,1951,1957,1961,1963,1969,1991,1993,2011,2017,2027,2029,2033,2041,2047,2053,2057,2059,2077,2081,2087,2089,2101,2113,2129,2137,2143,2161,2171,2173,2197,2207,2209,2221,2227,2237,2239,2251,2257,2269,2273,2281,2297,2311,2321,2353,2369,2381,2419,2431,2449,2461,2477,2491,2503,2509,2521,2531,2533,2537,2539,2549,2551,2557,2561,2563,2581,2591,2593,2617,2633,2641,2647,2659,2677,2689,2699,2701,2707,2713,2717,2719,2729,2731,2749,2753,2759,2761,2773,2801,2809,2827,2833,2843,2857,2867,2869,2879,2881,2893,2897,2899,2909,2911,2917,2921,2923,2929,2941,2951,2953,2971,2977,2993,3001,3007,3019,3037,3041,3049,3061,3071,3083,3089,3091,3103,3121,3131,3133,3149,3151,3161,3169,3179,3181,3187,3193,3211,3217,3229,3233,3251,3253,3257,3259,3277,3281,3289,3293,3301,3313,3317,3319,3329,3341,3347,3359,3361,3371,3373,3377,3379,3389,3391,3397,3401,3403,3421,3431,3433,3457,3473,3481,3487,3499,3517,3529,3539,3541,3551,3553,3569,3571,3581,3583,3601,3611,3613,3623,3629,3631,3637,3641,3649,3659,3667,3673,3691,3697,3707,3709,3713,3721,3733,3737,3739,3757,3761,3763,3769,3781,3791,3793,3797,3799,3809,3821,3827,3833,3839,3841,3851,3853,3859,3877,3881,3883,3889,3893,3901,3907,3931,3937,3947,3949,3953,3961,3967,3973,3977,3979,3991,4001,4013,4019,4031,4033,4043,4049,4051,4057,4061,4063,4069,4073,4093,4097,4103,4117,4129,4153,4159,4171,4177,4187,4189,4201,4211,4213,4223,4237,4241,4243,4253,4267,4273,4283,4297,4301,4303,4309,4313,4321,4331,4337,4339,4363,4369,4379,4381,4387,4393,4409,4411,4427,4429,4433,4441,4447,4453,4463,4469,4471,4477,4481,4493,4499,4511,4513,4517,4523,4537,4541,4553,4561,4577,4601,4607,4609,4619,4621,4637,4649,4661,4673,4691,4703,4717,4721,4733,4751,4757,4769,4787,4793,4801,4811,4813,4817,4829,4841,4853,4859,4877,4883,4889,4897,4901,4913,4919,4939,4957,4961,4973,4979,4997,5003,5009,5017,5021,5027,5041,5051,5053,5057,5059,5069,5071,5077,5081,5083,5101,5111,5113,5137,5153,5161,5167,5179,5197,5209,5219,5221,5231,5233,5249,5251,5261,5263,5281,5291,5293,5303,5309,5311,5317,5321,5329,5339,5347,5353,5371,5377,5387,5389,5393,5401,5413,5417,5419,5437,5441,5443,5449,5461,5471,5473,5477,5479,5489,5501,5507,5513,5519,5521,5531,5533,5539,5557,5561,5563,5569,5573,5581,5587,5611,5617,5627,5629,5633,5641,5647,5653,5657,5659,5671,5681,5693,5699,5711,5713,5723,5729,5731,5737,5741,5743,5749,5753,5771,5773,5777,5779,5791,5797,5801,5809,5821,5833,5851,5857,5881,5899,5917,5921,5939,5941,5951,5953,5963,5969,5981,5983,6001,6011,6023,6029,6031,6037,6049,6059,6061,6067,6073,6091,6107,6109,6113,6121,6131,6133,6137,6157,6161,6163,6169,6173,6191,6193,6197,6199,6221,6227,6233,6239,6241,6253,6257,6259,6277,6281,6283,6289,6301,6313,6331,6337,6347,6353,6361,6367,6373,6379,6401,6413,6431,6443,6449,6451,6457,6463,6469,6473,6481,6491,6493,6497,6499,6509,6511,6521,6523,6529,6541,6551,6553,6571,6577,6593,6611,6613,6617,6619,6631,6637,6641,6649,6667,6673,6689,6697,6721,6731,6733,6737,6739,6749,6751,6757,6761,6763,6781,6791,6793,6817,6833,6841,6847,6859,6877,6889,6899,6901,6911,6913,6929,6931,6941,6943,6961,6971,6973,6983,6989,6991,6997,7001,7009,7019,7027,7033,7051,7057,7067,7069,7073,7081,7093,7097,7099,7117,7121,7123,7129,7141,7151,7153,7157,7159,7169,7181,7187,7193,7199,7201,7211,7213,7219,7237,7241,7243,7249,7253,7261,7267,7291,7297,7307,7309,7313,7321,7327,7333,7337,7339,7351,7361,7373,7379,7391,7393,7403,7409,7411,7417,7421,7423,7429,7433,7451,7453,7457,7459,7471,7477,7481,7489,7501,7513,7531,7537,7561,7571,7573,7577,7579,7589,7591,7597,7601,7603,7627,7633,7649,7657,7673,7681,7691,7697,7699,7709,7711,7717,7723,7729,7739,7741,7747,7753,7757,7759,7769,7771,7789,7793,7799,7801,7813,7841,7853,7859,7871,7873,7883,7891,7897,7901,7909,7913,7921,7933,7937,7943,7957,7963,7969,7981,7991,7993,7997,7999,8009,8011,8017,8021,8023,8041,8051,8053,8077,8081,8083,8089,8093,8101,8107,8129,8137,8149,8161,8177,8191,8203,8209,8219,8221,8233,8243,8257,8269,8273,8287,8299,8317,8327,8329,8333,8341,8353,8363,8369,8371,8377,8401,8411,8413,8417,8419,8437,8441,8443,8459,8461,8467,8473,8479,8497,8501,8503,8509,8513,8531,8537,8543,8557,8563,8569,8579,8581,8587,8593,8597,8599,8609,8611,8641,8651,8653,8657,8669,8671,8677,8681,8683,8689,8717,8723,8737,8747,8749,8753,8761,8767,8773,8777,8779,8797,8801,8803,8809,8821,8833,8849,8857,8881,8917,8921,8923,8929,8933,8941,8947,8971,8977,8989,8993,9001,9017,9041,9043,9049,9053,9061,9067,9073,9083,9089,9091,9097,9101,9103,9109,9113,9133,9137,9143,9157,9169,9197,9203,9209,9217,9227,9229,9241,9253,9257,9259,9277,9281,9287,9301,9307,9313,9337,9341,9343,9349,9353,9361,9367,9389,9397,9409,9419,9421,9427,9433,9437,9439,9449,9451,9469,9473,9479,9481,9493,9517,9521,9523,9529,9533,9547,9553,9577,9589,9601,9617,9631,9643,9649,9659,9661,9673,9683,9697,9707,9713,9727,9739,9757,9761,9763,9769,9773,9781,9787,9809,9817,9829,9841,9857,9871,9883,9889,9899,9901,9913,9923,9937,9949,9953,9967,9979,9997,10001,10009,10013,10021,10027,10033,10049,10057,10069,10081,10091,10093,10097,10099,10109,10111,10117,10121,10123,10141,10151,10153,10177,10193,10201,10207,10219,10237,10249,10259,10261,10271,10273,10289,10291,10301,10303,10321,10331,10333,10343,10349,10351,10357,10361,10369,10379,10387,10393,10411,10417,10427,10429,10433,10441,10453,10457,10459,10477,10481,10483,10489,10501,10511,10513,10517,10519,10529,10541,10547,10553,10559,10561,10571,10573,10579,10597,10601,10603,10609,10613,10621,10627,10651,10657,10667,10669,10673,10681,10687,10693,10697,10699,10711,10721,10733,10739,10751,10753,10763,10769,10771,10777,10781,10783,10789,10793,10811,10813,10817,10819,10831,10837,10841,10849,10861,10873,10891,10897,10921,10931,10933,10937,10939,10949,10951,10957,10961,10963,10987,10993,11009,11017,11033,11041,11051,11057,11059,11069,11071,11077,11083,11089,11099,11101,11107,11113,11117,11119,11129,11131,11149,11153,11159,11161,11173,11201,11213,11219,11231,11233,11243,11251,11257,11261,11269,11273,11281,11293,11297,11303,11317,11323,11329,11341,11351,11353,11357,11359,11369,11371,11377,11381,11383,11401,11411,11413,11437,11441,11443,11449,11453,11461,11467,11489,11497,11509,11521,11531,11533,11537,11539,11549,11551,11561,11563,11569,11581,11591,11593,11611,11617,11633,11647,11659,11677,11681,11689,11699,11701,11713,11723,11729,11731,11741,11743,11761,11771,11773,11777,11779,11789,11791,11797,11801,11803,11821,11831,11833,11857,11873,11881,11887,11899,11917,11929,11939,11941,11951,11953,11969,11971,11981,11983,12001,12011,12013,12017,12029,12031,12037,12041,12043,12049,12071,12073,12091,12097,12107,12109,12113,12121,12127,12133,12137,12139,12157,12161,12167,12169,12181,12193,12209,12217,12223,12241,12251,12253,12277,12287,12289,12301,12307,12317,12319,12331,12337,12349,12353,12361,12377,12391,12401,12433,12449,12461,12499,12511,12529,12541,12557,12571,12583,12589,12601,12611,12613,12617,12619,12629,12631,12637,12641,12643,12661,12671,12673,12697,12713,12721,12727,12739,12757,12769,12779,12781,12787,12793,12797,12799,12809,12811,12829,12833,12839,12841,12853,12881,12889,12907,12913,12923,12937,12947,12949,12959,12961,12973,12977,12979,12989,12991,12997,13001,13003,13009,13021,13031,13033,13051,13057,13073,13081,13087,13099,13117,13121,13129,13141,13151,13163,13169,13171,13183,13201,13211,13213,13229,13231,13241,13249,13259,13261,13267,13273,13291,13297,13309,13313,13331,13333,13337,13339,13357,13361,13369,13373,13381,13393,13397,13399,13409,13421,13427,13439,13441,13451,13453,13457,13459,13469,13471,13477,13481,13483,13501,13511,13513,13537,13553,13561,13567,13579,13597,13609,13619,13621,13631,13633,13649,13651,13661,13663,13681,13691,13693,13703,13709,13711,13717,13721,13729,13739,13747,13753,13771,13777,13787,13789,13793,13801,13813,13817,13819,13837,13841,13843,13849,13861,13871,13873,13877,13879,13889,13901,13907,13913,13919,13921,13931,13933,13939,13957,13961,13963,13969,13973,13981,13987,14011,14017,14027,14029,14033,14041,14047,14053,14057,14059,14071,14081,14093,14099,14111,14113,14123,14129,14131,14137,14141,14143,14149,14153,14171,14173,14177,14179,14191,14197,14201,14209,14221,14233,14251,14257,14281,14291,14293,14297,14299,14309,14311,14317,14321,14323,14347,14353,14369,14377,14393,14401,14411,14417,14419,14429,14431,14437,14443,14449,14459,14461,14467,14473,14477,14479,14489,14491,14509,14513,14519,14521,14533,14561,14573,14579,14591,14593,14603,14611,14617,14621,14629,14633,14641,14653,14657,14663,14677,14683,14689,14701,14711,14713,14717,14719,14729,14731,14737,14741,14743,14761,14771,14773,14797,14801,14803,14809,14813,14821,14827,14849,14857,14869,14881,14891,14893,14897,14899,14909,14911,14921,14923,14929,14941,14951,14953,14971,14977,14993,15007,15019,15037,15041,15049,15059,15061,15073,15083,15089,15091,15101,15103,15121,15131,15133,15137,15139,15149,15151,15157,15161,15163,15181,15191,15193,15217,15233,15241,15247,15259,15277,15289,15299,15301,15311,15313,15329,15331,15341,15343,15361,15371,15373,15377,15389,15391,15397,15401,15403,15409,15431,15433,15451,15457,15467,15469,15473,15481,15487,15493,15497,15499,15517,15521,15527,15529,15541,15553,15569,15577,15583,15601,15611,15613,15637,15647,15649,15661,15667,15677,15679,15691,15697,15709,15713,15721,15737,15751,15761,15793,15809,15821,15859,15871,15889,15901,15917,15931,15943,15949,15961,15971,15973,15977,15979,15989,15991,15997,16001,16003,16021,16031,16033,16057,16073,16081,16087,16099,16117,16129,16139,16141,16147,16153,16157,16159,16169,16171,16189,16193,16199,16201,16213,16241,16249,16267,16273,16283,16297,16307,16309,16319,16321,16333,16337,16339,16349,16351,16357,16361,16363,16369,16381,16391,16393,16411,16417,16433,16441,16447,16459,16477,16481,16489,16501,16511,16523,16529,16531,16543,16561,16571,16573,16589,16591,16601,16609,16619,16621,16627,16633,16651,16657,16669,16673,16691,16693,16697,16699,16717,16721,16729,16733,16741,16753,16757,16759,16769,16781,16787,16799,16801,16811,16813,16817,16819,16829,16831,16837,16841,16843,16861,16871,16873,16897,16913,16921,16927,16939,16957,16969,16979,16981,16991,16993,17009,17011,17021,17023,17041,17051,17053,17063,17069,17071,17077,17081,17089,17099,17107,17113,17131,17137,17147,17149,17153,17161,17173,17177,17179,17197,17201,17203,17209,17221,17231,17233,17237,17239,17249,17261,17267,17273,17279,17281,17291,17293,17299,17317,17321,17323,17329,17333,17341,17347,17371,17377,17387,17389,17393,17401,17407,17413,17417,17419,17431,17441,17453,17459,17471,17473,17483,17489,17491,17497,17501,17503,17509,17513,17533,17537,17543,17557,17569,17593,17599,17611,17617,17627,17629,17641,17651,17653,17663,17677,17681,17683,17693,17707,17713,17723,17737,17741,17743,17749,17753,17761,17771,17777,17779,17803,17809,17819,17821,17827,17833,17849,17851,17867,17869,17873,17881,17887,17893,17903,17909,17911,17917,17921,17933,17939,17951,17953,17957,17963,17977,17981,17993,18001,18017,18041,18047,18049,18059,18061,18077,18089,18101,18113,18131,18143,18157,18161,18173,18191,18197,18209,18227,18233,18241,18251,18253,18257,18269,18281,18293,18299,18317,18323,18329,18337,18341,18353,18359,18379,18397,18401,18413,18419,18437,18443,18449,18457,18461,18467,18481,18491,18493,18497,18499,18509,18511,18517,18521,18523,18541,18551,18553,18577,18593,18601,18607,18619,18637,18649,18659,18661,18671,18673,18689,18691,18701,18703,18721,18731,18733,18743,18749,18751,18757,18761,18769,18779,18787,18793,18811,18817,18827,18829,18833,18841,18853,18857,18859,18877,18881,18883,18889,18901,18911,18913,18917,18919,18929,18941,18947,18953,18959,18961,18971,18973,18979,18997,19001,19003,19009,19013,19021,19027,19051,19057,19067,19069,19073,19081,19087,19093,19097,19099,19111,19121,19133,19139,19151,19153,19163,19169,19171,19177,19181,19183,19189,19193,19211,19213,19217,19219,19231,19237,19241,19249,19261,19273,19291,19297,19321,19339,19357,19361,19379,19381,19391,19393,19403,19409,19421,19423,19441,19451,19463,19469,19471,19477,19489,19499,19501,19507,19513,19531,19547,19549,19553,19561,19571,19573,19577,19597,19601,19603,19609,19613,19631,19633,19637,19639,19661,19667,19673,19679,19681,19693,19697,19699,19717,19721,19723,19729,19741,19753,19771,19777,19787,19793,19801,19807,19813,19819,19841,19853,19871,19883,19889,19891,19897,19903,19909,19913,19921,19931,19933,19937,19939,19949,19951,19961,19963,19969,19981,19991,19993,20011,20017,20033,20051,20053,20057,20059,20071,20077,20081,20089,20107,20113,20129,20137,20161,20171,20173,20177,20179,20189,20191,20197,20201,20203,20221,20231,20233,20257,20273,20281,20287,20299,20317,20329,20339,20341,20351,20353,20369,20371,20381,20383,20401,20411,20413,20423,20429,20431,20437,20441,20449,20459,20467,20473,20491,20497,20507,20509,20513,20521,20533,20537,20539,20557,20561,20563,20569,20581,20591,20593,20597,20599,20609,20621,20627,20633,20639,20641,20651,20653,20659,20677,20681,20683,20689,20693,20701,20707,20731,20737,20747,20749,20753,20761,20767,20773,20777,20779,20791,20801,20813,20819,20831,20833,20843,20849,20851,20857,20861,20863,20869,20873,20891,20893,20897,20899,20911,20917,20921,20929,20941,20953,20971,20977,21001,21011,21013,21017,21019,21029,21031,21037,21041,21043,21067,21073,21089,21097,21113,21121,21131,21137,21139,21149,21151,21157,21163,21169,21179,21181,21187,21193,21197,21199,21209,21211,21229,21233,21239,21241,21253,21281,21293,21299,21311,21313,21323,21331,21337,21341,21349,21353,21361,21373,21377,21383,21397,21403,21409,21421,21431,21433,21437,21439,21449,21451,21457,21461,21463,21481,21491,21493,21517,21521,21523,21529,21533,21541,21547,21569,21577,21589,21601,21617,21631,21643,21649,21659,21661,21673,21683,21697,21709,21713,21727,21739,21757,21767,21769,21773,21781,21793,21803,21809,21811,21817,21841,21851,21853,21857,21859,21877,21881,21883,21899,21901,21907,21913,21919,21937,21941,21943,21949,21953,21971,21977,21983,21997,22003,22009,22019,22021,22027,22033,22037,22039,22049,22051,22081,22091,22093,22097,22109,22111,22117,22121,22123,22129,22157,22163,22177,22187,22189,22193,22201,22207,22213,22217,22219,22237,22241,22243,22249,22261,22273,22289,22297,22321,22357,22361,22363,22369,22373,22381,22387,22411,22417,22429,22433,22441,22457,22481,22483,22489,22493,22501,22507,22513,22523,22529,22531,22537,22541,22543,22549,22553,22573,22577,22583,22597,22609,22637,22643,22649,22657,22667,22669,22681,22693,22697,22699,22717,22721,22727,22741,22747,22753,22777,22781,22783,22789,22793,22801,22807,22829,22837,22849,22859,22861,22867,22873,22877,22879,22889,22891,22909,22913,22919,22921,22933,22957,22961,22963,22969,22973,22987,22993,23017,23029,23041,23057,23071,23083,23089,23099,23101,23113,23123,23137,23147,23153,23167,23179,23197,23201,23203,23209,23213,23221,23227,23249,23257,23269,23281,23297,23311,23323,23329,23339,23341,23353,23363,23377,23389,23393,23407,23419,23437,23441,23449,23453,23461,23467,23473,23489,23497,23509,23521,23531,23533,23537,23539,23549,23551,23557,23561,23563,23581,23591,23593,23617,23633,23641,23647,23659,23677,23689,23699,23701,23711,23713,23729,23731,23741,23743,23761,23771,23773,23783,23789,23791,23797,23801,23809,23819,23827,23833,23851,23857,23867,23869,23873,23881,23893,23897,23899,23917,23921,23923,23929,23941,23951,23953,23957,23959,23969,23981,23987,23993,23999,24001,24011,24013,24019,24037,24041,24043,24049,24053,24061,24067,24091,24097,24107,24109,24113,24121,24127,24133,24137,24139,24151,24161,24173,24179,24191,24193,24203,24209,24211,24217,24221,24223,24229,24233,24251,24253,24257,24259,24271,24277,24281,24289,24301,24313,24331,24337,24361,24371,24373,24377,24379,24389,24391,24397,24401,24403,24427,24433,24449,24457,24473,24481,24491,24497,24499,24509,24511,24517,24523,24529,24539,24541,24547,24553,24557,24559,24569,24571,24589,24593,24599,24601,24613,24641,24653,24659,24671,24673,24683,24691,24697,24701,24709,24713,24721,24733,24737,24743,24757,24763,24769,24781,24791,24793,24797,24799,24809,24811,24817,24821,24823,24841,24851,24853,24877,24881,24883,24889,24893,24901,24907,24929,24937,24949,24961,24971,24973,24977,24979,24989,24991,25001,25003,25009,25021,25031,25033,25051,25057,25073,25087,25099,25117,25121,25129,25139,25141,25153,25163,25169,25171,25181,25183,25201,25211,25213,25217,25219,25229,25231,25237,25241,25243,25261,25271,25273,25297,25313,25321,25327,25339,25357,25369,25379,25381,25391,25393,25409,25411,25421,25423,25441,25451,25453,25457,25469,25471,25477,25481,25483,25489,25511,25513,25531,25537,25547,25549,25553,25561,25567,25573,25577,25579,25597,25601,25607,25609,25621,25633,25649,25657,25663,25681,25691,25693,25717,25727,25729,25741,25747,25757,25759,25771,25777,25789,25793,25801,25817,25831,25841,25873,25889,25901,25939,25951,25969,25981,25997,26011,26023,26029,26041,26051,26053,26057,26059,26069,26071,26077,26081,26083,26101,26111,26113,26137,26153,26161,26167,26179,26197,26209,26219,26221,26227,26233,26237,26239,26249,26251,26269,26273,26279,26281,26293,26321,26329,26347,26353,26363,26377,26387,26389,26399,26401,26413,26417,26419,26429,26431,26437,26441,26443,26449,26461,26471,26473,26491,26497,26513,26521,26527,26539,26557,26561,26569,26581,26591,26603,26609,26611,26623,26641,26651,26653,26669,26671,26681,26689,26699,26701,26707,26713,26731,26737,26749,26753,26771,26773,26777,26779,26797,26801,26809,26813,26821,26833,26837,26839,26849,26861,26867,26879,26881,26891,26893,26897,26899,26909,26911,26917,26921,26923,26941,26951,26953,26977,26993,27001,27007,27019,27037,27049,27059,27061,27071,27073,27089,27091,27101,27103,27121,27131,27133,27143,27149,27151,27157,27161,27169,27179,27187,27193,27211,27217,27227,27229,27233,27241,27253,27257,27259,27277,27281,27283,27289,27301,27311,27313,27317,27319,27329,27341,27347,27353,27359,27361,27371,27373,27379,27397,27401,27403,27409,27413,27421,27427,27451,27457,27467,27469,27473,27481,27487,27493,27497,27499,27511,27521,27533,27539,27551,27553,27563,27569,27571,27577,27581,27583,27589,27593,27611,27613,27617,27619,27631,27637,27641,27649,27661,27673,27691,27697,27721,27731,27733,27737,27739,27749,27751,27757,27761,27763,27787,27793,27809,27817,27833,27841,27851,27857,27859,27869,27871,27877,27883,27889,27899,27901,27907,27913,27917,27919,27929,27931,27949,27953,27959,27961,27973,28001,28013,28019,28031,28033,28043,28051,28057,28061,28069,28073,28081,28093,28097,28103,28117,28123,28129,28141,28151,28153,28157,28159,28169,28171,28177,28181,28183,28201,28211,28213,28237,28241,28243,28249,28253,28261,28267,28289,28297,28309,28321,28337,28351,28363,28369,28379,28381,28393,28403,28417,28429,28433,28447,28459,28477,28487,28489,28493,28501,28513,28523,28529,28531,28537,28561,28571,28573,28577,28579,28597,28601,28603,28619,28621,28627,28633,28639,28657,28661,28663,28669,28673,28691,28697,28703,28717,28723,28729,28739,28741,28747,28753,28757,28759,28769,28771,28801,28811,28813,28817,28829,28831,28837,28841,28843,28849,28877,28883,28897,28907,28909,28913,28921,28927,28933,28937,28939,28957,28961,28963,28969,28981,28993,29009,29017,29041,29077,29081,29083,29089,29093,29101,29107,29131,29137,29149,29153,29161,29177,29201,29203,29209,29213,29221,29227,29233,29243,29249,29251,29257,29261,29263,29269,29273,29293,29297,29303,29317,29329,29357,29363,29369,29377,29387,29389,29401,29413,29417,29419,29437,29441,29447,29461,29467,29473,29497,29501,29503,29509,29513,29521,29527,29549,29557,29569,29579,29581,29587,29593,29597,29599,29609,29611,29629,29633,29639,29641,29653,29677,29681,29683,29689,29693,29707,29713,29737,29749,29761,29777,29791,29803,29809,29819,29821,29833,29843,29857,29867,29873,29887,29899,29917,29921,29923,29929,29933,29941,29947,29969,29977,29989,30001,30017,30031,30043,30049,30059,30061,30073,30083,30097,30109,30113,30127,30139,30157,30161,30169,30173,30181,30187,30193,30209,30217,30229,30241,30251,30253,30257,30259,30283,30299,30301,30307,30313,30323,30329,30337,30347,30349,30353,30361,30367,30383,30389,30391,30397,30413,30419,30431,30433,30449,30451,30467,30469,30473,30481,30487,30493,30497,30523,30529,30539,30547,30553,30557,30559,30571,30577,30593,30617,30623,30637,30641,30643,30649,30661,30673,30683,30689,30691,30697,30701,30703,30713,30721,30733,30743,30757,30763,30769,30803,30809,30811,30817,30823,30829,30833,30841,30859,30881,30889,30913,30923,30929,30931,30937,30941,30943,30949,30953,30973,30977,30983,30997,31009,31033,31039,31051,31057,31067,31069,31081,31091,31093,31103,31117,31121,31123,31133,31147,31153,31163,31177,31181,31183,31189,31193,31201,31211,31217,31219,31243,31249,31259,31261,31267,31273,31289,31291,31307,31309,31313,31321,31327,31333,31343,31349,31351,31357,31361,31373,31379,31391,31393,31403,31411,31417,31427,31429,31433,31441,31447,31453,31457,31459,31483,31489,31499,31501,31513,31517,31519,31529,31531,31537,31543,31553,31571,31583,31597,31601,31603,31609,31613,31621,31627,31643,31649,31651,31657,31663,31669,31673,31681,31693,31697,31723,31729,31753,31763,31769,31771,31777,31781,31783,31789,31793,31819,31837,31841,31849,31873,31883,31889,31891,31897,31901,31903,31909,31921,31931,31933,31937,31939,31949,31951,31957,31961,31963,31981,31991,31993,32017,32033,32051,32057,32063,32077,32083,32089,32093,32101,32107,32113,32129,32149,32161,32173,32183,32189,32191,32197,32201,32203,32209,32213,32233,32237,32243,32257,32267,32269,32273,32281,32293,32297,32299,32317,32321,32323,32329,32341,32351,32353,32357,32359,32369,32381,32387,32393,32399,32401,32411,32413,32419,32437,32441,32443,32449,32453,32461,32467,32491,32497,32507,32509,32513,32521,32527,32533,32537,32539,32551,32561,32573,32579,32591,32593,32603,32609,32611,32617,32621,32623,32629,32633,32651,32653,32657,32659,32671,32677,32681,32689,32701,32713,32731,32737,32761,32779,32797,32801,32819,32821,32831,32833,32843,32849,32861,32863,32881,32891,32903,32909,32911,32917,32929,32939,32941,32947,32953,32971,32987,32989,32993,33001,33011,33013,33017,33037,33041,33043,33049,33053,33071,33073,33077,33079,33101,33107,33113,33119,33121,33133,33137,33139,33157,33161,33163,33169,33181,33193,33211,33217,33227,33233,33241,33247,33253,33259,33281,33293,33311,33323,33329,33331,33337,33343,33349,33353,33361,33371,33373,33377,33379,33389,33391,33401,33403,33409,33421,33431,33433,33451,33457,33473,33491,33493,33497,33499,33511,33517,33521,33529,33547,33553,33569,33577,33601,33611,33613,33617,33629,33641,33653,33659,33683,33689,33697,33701,33713,33739,33757,33773,33779,33797,33809,33821,33827,33833,33841,33851,33853,33857,33869,33871,33877,33881,33883,33889,33911,33913,33931,33937,33953,33961,33967,33979,33997,34001,34009,34019,34021,34031,34033,34043,34049,34051,34061,34063,34081,34091,34093,34103,34109,34117,34121,34129,34141,34147,34171,34177,34187,34189,34193,34201,34211,34213,34217,34219,34241,34243,34249,34253,34261,34271,34273,34277,34289,34301,34313,34319,34331,34333,34337,34339,34357,34361,34369,34373,34381,34387,34393,34411,34417,34427,34429,34441,34453,34457,34459,34471,34481,34493,34499,34511,34513,34523,34529,34537,34541,34543,34549,34553,34561,34571,34577,34579,34603,34609,34619,34621,34627,34633,34649,34651,34667,34669,34673,34681,34687,34693,34703,34709,34711,34717,34721,34733,34739,34751,34753,34757,34763,34777,34781,34793,34801,34817,34841,34847,34849,34859,34861,34877,34889,34901,34913,34931,34943,34957,34961,34973,34991,34997,35009,35027,35033,35041,35051,35053,35057,35069,35081,35093,35099,35117,35123,35129,35137,35141,35153,35159,35179,35197,35201,35213,35219,35237,35243,35249,35257,35261,35267,35281,35291,35293,35297,35309,35321,35327,35333,35339,35351,35377,35389,35393,35411,35417,35423,35429,35449,35453,35473,35477,35489,35513,35519,35521,35531,35533,35537,35549,35561,35573,35597,35603,35617,35627,35629,35633,35657,35663,35669,35681,35699,35713,35723,35729,35741,35747,35753,35771,35789,35801,35807,35809,35813,35831,35837,35851,35857,35867,35869,35879,35881,35887,35893,35897,35921,35923,35929,35947,35953,35963,35969,35971,35977,35989,35993,36011,36013,36017,36019,36031,36037,36047,36049,36053,36061,36077,36083,36089,36097,36107,36109,36121,36131,36133,36137,36139,36149,36151,36157,36161,36163,36187,36193,36203,36209,36217,36221,36223,36229,36233,36241,36247,36257,36269,36287,36289,36299,36301,36307,36313,36317,36319,36329,36331,36349,36353,36359,36361,36373,36401,36409,36427,36433,36443,36457,36467,36469,36479,36481,36493,36497,36499,36509,36511,36517,36521,36523,36529,36541,36551,36553,36571,36577,36593,36601,36607,36619,36637,36641,36649,36661,36671,36683,36689,36691,36703,36721,36731,36733,36749,36751,36761,36769,36779,36781,36787,36793,36811,36817,36829,36833,36851,36853,36857,36859,36877,36881,36889,36893,36901,36913,36917,36919,36929,36941,36947,36959,36961,36979,36991,37003,37021,37063,37069,37081,37091,37097,37099,37109,37111,37117,37123,37129,37141,37151,37153,37171,37193,37201,37207,37237,37241,37249,37259,37267,37273,37277,37279,37291,37297,37309,37313,37319,37321,37333,37339,37361,37369,37393,37403,37409,37417,37427,37439,37447,37453,37477,37481,37483,37489,37493,37501,37507,37529,37537,37549,37561,37577,37591,37603,37609,37619,37621,37633,37649,37661,37699,37711,37729,37741,37757,37771,37783,37789,37801,37817,37831,37841,37867,37873,37889,37897,37913,37921,37927,37937,37969,37997,38011,38047,38077,38081,38089,38107,38113,38123,38137,38147,38149,38159,38161,38173,38177,38179,38189,38191,38203,38209,38219,38221,38233,38237,38239,38249,38251,38257,38273,38279,38281,38293,38299,38317,38321,38329,38341,38351,38363,38369,38371,38383,38401,38411,38413,38417,38419,38429,38431,38441,38443,38449,38461,38471,38473,38491,38497,38513,38527,38539,38557,38561,38569,38579,38581,38593,38603,38609,38611,38621,38623,38641,38653,38657,38663,38677,38683,38701,38711,38713,38719,38729,38737,38741,38743,38749,38761,38771,38797,38803,38809,38813,38821,38827,38833,38849,38869,38881,38893,38903,38909,38911,38917,38921,38923,38929,38933,38953,38957,38963,38977,38981,38989,38993,39001,39013,39017,39023,39037,39043,39049,39061,39073,39089,39097,39121,39149,39161,39167,39169,39173,39211,39217,39229,39233,39241,39257,39281,39283,39289,39293,39301,39307,39313,39329,39337,39353,39379,39397,39401,39409,39433,39451,39457,39481,39493,39497,39499,39511,39521,39533,39539,39551,39553,39563,39569,39577,39581,39583,39589,39593,39601,39607,39617,39629,39647,39649,39653,39659,39671,39691,39701,39703,39709,39713,39721,39761,39773,39779,39791,39793,39803,39811,39821,39827,39833,39839,39841,39857,39863,39869,39877,39881,39883,39889,39901,39913,39923,39929,39931,39937,39947,39953,39961,39979,40003,40007,40009,40013,40021,40037,40051,40057,40067,40081,40093,40109,40127,40129,40139,40141,40157,40171,40219,40241,40247,40253,40267,40273,40277,40289,40297,40301,40307,40319

65536: This makes my answer go over the character limit (32768 numbers)

105953: 1-105952
\$\endgroup\$
4
  • \$\begingroup\$ I think something is wrong here, you cannot balance one on a 100 hole centrifuge but you can balance 8,18,28,48,58,68,78,88 (this list is perhaps not complete). \$\endgroup\$ – flawr Jul 25 '14 at 13:41
  • \$\begingroup\$ I must've accidentally cut the one out, as for the other numbers, have to look into that \$\endgroup\$ – Nexus Jul 25 '14 at 13:47
  • \$\begingroup\$ Thank you very much for updating your list! If possible, you could just count the number of outputs for the cases where you get such huge lists - I did not think that throu really=) \$\endgroup\$ – flawr Jul 26 '14 at 13:12
  • \$\begingroup\$ @flawr I updated the list \$\endgroup\$ – Nexus Jul 26 '14 at 14:59
0
\$\begingroup\$

Pyth - 39 37 bytes

A direct translation of @Wrzlprmft's python answer.

f.Am>.asm^.n1c*.jZyk.nZQd^10_9.cUQTSQ

Explanation and probably further golfing coming soon.

Try it online here.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.