Ask Your Question

# mathhobbyist's profile - activity

 2019-04-15 23:21:43 -0500 received badge ● Notable Question (source) 2019-04-01 17:51:31 -0500 received badge ● Popular Question (source) 2019-03-21 16:13:15 -0500 asked a question How to find swich presses on lamp shutting problem? Is there a way to solve the following optimization problem in Sage given in https://www.ohjelmointiputka.net/post... : The following is an example case. I have $n=120$ lamps in a circle, and enumerated by $L_1,\ldots,L_{120}$. Some of them are switched on and some of them are switched off. I also have been given a positive integer $m=7.$ One every turn I choose one lamp $L_i$ and then the lamps $L_{i-m},\ldots,L_{i+m}$ will change their state, I mean if lamp $L_j$ was turned off then now it is turned on and vice versa. Indexes are modulo $n$ so the lamps $L_{118}, L_{119}, L_1,L_2$ are consecutive. Which switches one must press, if the initial states of the lamps are (from $L_1$ to $L_{120}$)  1010110110000100000101011001011111010111 1010011101001100000010001010011010110000 0000100110010100010010110111000000010110  where $1$ means that the corresponding lamp is on at the beginning and $0$ means that the corresponding lamp is off at the beginning. All cases in this problem are given as label, n.o. lamps, how many lamps original lamp states a switch affects per direction ================================================================================ B 6 1 101101 -------------------------------------------------------------------------------- C 10 2 1011010110 -------------------------------------------------------------------------------- D 20 1 11111011101010111111 -------------------------------------------------------------------------------- E 30 7 011100001010011011100001010011 -------------------------------------------------------------------------------- F 39 6 110100111111101000011000100110111100010 -------------------------------------------------------------------------------- G 53 9 0101100101111100100011100111101001001010 0010000010110 -------------------------------------------------------------------------------- H 120 7 1010110110000100000101011001011111010111 1010011101001100000010001010011010110000 0000100110010100010010110111000000010110 -------------------------------------------------------------------------------- I 220 27 1110111111101000100110011001100110100000 0010100011000111101100111111000001010000 1010110110011100100010011011010111100011 0101101000010000100110111101001001011010 1101001001110110001100011010111101001100 11010111110101010100 -------------------------------------------------------------------------------- J 500 87 1010001101101001110001101001000101010100 0001111111001101011000000011001111111011 1001110011010111111011010100010011011001 1001101110011011100001000111110101011111 1100111100001100110011101110101100001111 1100010010011010001111000000101110101101 1010100001100011111000111001000101101000 1011111111101111000000011111010001000000 1110011110111101010010011000000100010100 0011101011010011010110011110111000010010 0111100100011010010110001000011100101001 1110111010001001011001111011111011010110 10101101111011101110 -------------------------------------------------------------------------------- K 1002 83 0010100100100101000000110101111111101011 1101000101111110001110000110110110010101 1110110011011101100110111001110110010011 1101111010110011110101100001101010100011 1110001100011111110100011110100111111100 0011001011100110101100001101000001110010 0110100000100100100000011010000010111100 1110001110011110101001100111101101010000 0101010000011010011110101001001001000000 0011000100011011011001111010001101111000 0100001011010011001010111001111100110001 0011111110101101001100111101110000000000 1101100100000011000010010100010101001000 1100001000101001100110010100001000001101 1101000100001010011000101001101000100010 0011010001011101010100011101001101101100 0111110100110011001111000000001001001001 1001111001011111000010110000110010101000 1011001100111101000101000110000111010100 0010011011010111001101011001111000001011 1110101010101101111011111110100001100110 1000101100110011010000110000011011110011 0010000010000000111101101000001111101111 0100111110010101100011101001111101010000 1111100010011001110111111000101000000101 01 -------------------------------------------------------------------------------- L 2107 108 0111110100011000011111101110010101100011 1001111011101001001110111110001100011001 1001010100101011101101001000010111111111 1001101010111011110100100101000101100011 1110100010010010101110100000111100101000 0111101011111100010010110000100110100100 0100110101110010110011110010101101100111 1110010011000110110111010110010100101110 0111111101110000111001111100100010010001 1010110011000101100111111001011110101110 0111010110111110110101000101100100011000 1011000011011110001111100110100010100101 1101111100110011001110010010001010101111 1000001001000110011110010011011101110100 1011111100110010011000010110010110101010 0110101000011011110001010000010001000110 1001110101001001110110111111010011010111 1111011001000110111001000011101101110001 0000011111101000010101011111011011000011 1111000000011100010011011001011000110101 1101011111100001100010110010110011000000 0001001111100101110100100011011010011100 0000001111010101000111011000110110100001 1010110011100110111010111110110000010000 1000101001111001000110000101010000010111 1011100001000110001100010000001011101110 1001111110100010010000011000100101010101 1001001001110110101000001001001100001011 0011011100011111100111001110101101110001 0111010000010011110110011011000011101001 1111011010010000101111000010000001100110 1001011101001000010101001001011111111011 1000111000100001101100101110100011111100 1011001111101111110110101111101111011111 1001111100110101110101111110010010101101 1111111111000100100111100011101110110100 0100011011001010110100101101000000110010 0010010001001110110100011111100011111101 0100110111101101010101010100110110011011 0001111111000100000111011010101011000010 0011011110110110110100011001101111001000 1000000011110011100111100000001010010011 1000011101111100000101010101010010100101 1010001011010100011011001110110010100000 1000111101111000010111111101010110110111 0110001111100011001110000100100101001111 0000111111100010011001010000010110111000 1000110110001000001100110000001011000010 1000101101110000101100100010101111100011 1000010010111101000010000110011010000001 0010001100001000001100110111110100100111 1001100110001000100101011111001011001111 110001011111001101010101001 ================================================================================  I know there is a solution that compputes the minimum number of switch presses in https://ask.sagemath.org/question/393... . But the next task is to list those switches I need to press. I tried room = [] input = [] m = [] room.append('I') input.append('1110111111101000100110011001100110100000001010001100011110110011111100000101000010101101100111001000100110110101111000110101101000010000100110111101001001011010110100100111011000110001101011110100110011010111110101010100') m.append(27) F = GF(2) L_init = vector(F,input[0]) d = len(L_init) M = matrix(F,d,d) for i in range(d): for j in range(-m[0],m[0]+1 ): M[i,(i+j) % d] = 1 I = M.solve_right(L_init) K = M.right_kernel() best = None for k in K: A = (I+k).nonzero_positions() B= [] if len((I+k).nonzero_positions()) < best or best == None: S = room[0] + ' ' best = len((I+k).nonzero_positions()) for i in range(len(A)): S +=str(int(A[i])+1) + ' ' print(S) print("Optimal")  but this seems to be too slow. It has printed only I 1 2 4 6 8 10 11 12 13 18 19 20 21 22 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 55 56 62 65 66 67 68 70 71 72 74 75 77 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 112 114 115 119 120 121 123 124 126 127 128 130 131 132 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 165 I 1 2 4 6 8 11 12 13 18 19 20 21 22 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 56 62 66 67 68 70 71 72 74 75 77 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 110 112 114 115 119 121 123 124 126 127 128 130 131 132 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 175 220 I 1 2 4 6 8 12 13 18 19 20 21 22 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 55 56 62 67 68 70 71 72 74 75 77 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 112 114 115 119 123 124 126 127 128 130 131 132 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 165 175 176 I 1 2 4 6 8 12 18 19 20 21 22 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 56 62 67 70 71 72 74 75 77 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 110 112 114 115 119 124 126 127 128 130 131 132 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 175 176 178 220 I 1 2 4 6 8 12 18 19 21 22 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 55 56 62 67 70 71 72 74 77 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 112 114 115 119 124 126 127 128 131 132 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 165 175 176 178 185 I 1 2 4 6 8 12 18 19 21 23 24 25 26 28 31 32 39 40 41 44 45 47 49 51 53 56 62 67 70 71 72 74 79 80 83 85 87 88 90 94 95 99 100 101 103 106 109 110 112 114 115 119 124 126 127 128 131 133 135 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 175 176 178 185 187 220 I 1 2 4 6 8 12 18 19 21 23 24 26 28 31 32 39 40 41 44 45 47 49 51 53 55 56 62 67 70 71 72 74 79 83 85 87 88 90 94 95 99 100 101 103 106 109 112 114 115 119 124 126 127 128 131 133 136 137 139 140 142 145 146 148 151 153 156 158 159 160 161 165 175 176 178 185 187 190  after couple of days computation. So how can I found the optimal solution faster? 2019-03-21 13:14:03 -0500 commented answer How to find a minimum number of switch presses to shut down all lamps? Umm. I think this finds the optimal number of switches. But the problem asks also which switches I need to press. How can I find those? 2019-03-19 12:16:57 -0500 answered a question Solving an optimization problem by Sage There is a Python program to solve 11x11 case in https://stackoverflow.com/questions/3... 2018-12-13 01:29:53 -0500 received badge ● Notable Question (source) 2018-12-13 00:47:32 -0500 asked a question On finding to find a minimum number of switch presses to shut down all lamps This is a follow up to https://ask.sagemath.org/question/393... There is a problem on the The following is an example case. I have $n=120$ lamps in a circle, and enumerated by $L_1,\ldots,L_{120}$. Some of them are switched on and some of them are switched off. I also have been given a positive integer $m=7.$ One every turn I choose one lamp $L_i$ and then the lamps $L_{i-m},\ldots,L_{i+m}$ will change their state, I mean if lamp $L_j$ was turned off then now it is turned on and vice versa. Indexes are modulo $n$ so the lamps $L_{118}, L_{119}, L_1,L_2$ are consecutive. What is the minimum number of turns to shut off all lamps and which switches one must press, if the initial states of the lamps are (from $L_1$ to $L_{120}$)  1010110110000100000101011001011111010111 1010011101001100000010001010011010110000 0000100110010100010010110111000000010110  where $1$ means that the corresponding lamp is on at the beginning and $0$ means that the corresponding lamp is off at the beginning? All cases are listed as below: label, n.o. lamps, how many lamps original lamp states a switch affects per direction ================================================================================ B 6 1 101101 -------------------------------------------------------------------------------- C 10 2 1011010110 -------------------------------------------------------------------------------- D 20 1 11111011101010111111 -------------------------------------------------------------------------------- E 30 7 011100001010011011100001010011 -------------------------------------------------------------------------------- F 39 6 110100111111101000011000100110111100010 -------------------------------------------------------------------------------- G 53 9 0101100101111100100011100111101001001010 0010000010110 -------------------------------------------------------------------------------- H 120 7 1010110110000100000101011001011111010111 1010011101001100000010001010011010110000 0000100110010100010010110111000000010110 -------------------------------------------------------------------------------- I 220 27 1110111111101000100110011001100110100000 0010100011000111101100111111000001010000 1010110110011100100010011011010111100011 0101101000010000100110111101001001011010 1101001001110110001100011010111101001100 11010111110101010100 -------------------------------------------------------------------------------- J 500 87 1010001101101001110001101001000101010100 0001111111001101011000000011001111111011 1001110011010111111011010100010011011001 1001101110011011100001000111110101011111 1100111100001100110011101110101100001111 1100010010011010001111000000101110101101 1010100001100011111000111001000101101000 1011111111101111000000011111010001000000 1110011110111101010010011000000100010100 0011101011010011010110011110111000010010 0111100100011010010110001000011100101001 1110111010001001011001111011111011010110 10101101111011101110 -------------------------------------------------------------------------------- K 1002 83 0010100100100101000000110101111111101011 1101000101111110001110000110110110010101 1110110011011101100110111001110110010011 1101111010110011110101100001101010100011 1110001100011111110100011110100111111100 0011001011100110101100001101000001110010 0110100000100100100000011010000010111100 1110001110011110101001100111101101010000 0101010000011010011110101001001001000000 0011000100011011011001111010001101111000 0100001011010011001010111001111100110001 0011111110101101001100111101110000000000 1101100100000011000010010100010101001000 1100001000101001100110010100001000001101 1101000100001010011000101001101000100010 0011010001011101010100011101001101101100 0111110100110011001111000000001001001001 1001111001011111000010110000110010101000 1011001100111101000101000110000111010100 0010011011010111001101011001111000001011 1110101010101101111011111110100001100110 1000101100110011010000110000011011110011 0010000010000000111101101000001111101111 0100111110010101100011101001111101010000 1111100010011001110111111000101000000101 01 -------------------------------------------------------------------------------- L 2107 108 0111110100011000011111101110010101100011 1001111011101001001110111110001100011001 1001010100101011101101001000010111111111 1001101010111011110100100101000101100011 1110100010010010101110100000111100101000 0111101011111100010010110000100110100100 0100110101110010110011110010101101100111 1110010011000110110111010110010100101110 0111111101110000111001111100100010010001 1010110011000101100111111001011110101110 0111010110111110110101000101100100011000 1011000011011110001111100110100010100101 1101111100110011001110010010001010101111 1000001001000110011110010011011101110100 1011111100110010011000010110010110101010 0110101000011011110001010000010001000110 1001110101001001110110111111010011010111 1111011001000110111001000011101101110001 0000011111101000010101011111011011000011 1111000000011100010011011001011000110101 1101011111100001100010110010110011000000 0001001111100101110100100011011010011100 0000001111010101000111011000110110100001 1010110011100110111010111110110000010000 1000101001111001000110000101010000010111 1011100001000110001100010000001011101110 1001111110100010010000011000100101010101 1001001001110110101000001001001100001011 0011011100011111100111001110101101110001 0111010000010011110110011011000011101001 1111011010010000101111000010000001100110 1001011101001000010101001001011111111011 1000111000100001101100101110100011111100 1011001111101111110110101111101111011111 1001111100110101110101111110010010101101 1111111111000100100111100011101110110100 0100011011001010110100101101000000110010 0010010001001110110100011111100011111101 0100110111101101010101010100110110011011 0001111111000100000111011010101011000010 0011011110110110110100011001101111001000 1000000011110011100111100000001010010011 1000011101111100000101010101010010100101 1010001011010100011011001110110010100000 1000111101111000010111111101010110110111 0110001111100011001110000100100101001111 0000111111100010011001010000010110111000 1000110110001000001100110000001011000010 1000101101110000101100100010101111100011 1000010010111101000010000110011010000001 0010001100001000001100110111110100100111 1001100110001000100101011111001011001111 110001011111001101010101001 ================================================================================  From the first link, I was able to solve smaller cases. Like room = 'B' input = '101101' m = 1 F = GF(2) L_init = vector(F,input) d = len(L_init) M = matrix(F,d,d) for i in range(d): for j in range(-m,m+1 ): M[i,(i+j) % d] = 1 I = M.solve_right(L_init) K = M.right_kernel() ; K.dimension() lb = [(I+k).nonzero_positions() for k in K] la = [len((I+k).nonzero_positions()) for k in K] m = min(la) # print(m) notprinted = True res = "" for i in range(len(lb)): if m == la[i] and notprinted: for j in range(len(lb[i])): res += str(lb[i][j]+1) + " " #print(lb[i]) notprinted = False print(room + ' ' + res)  Gives solution B 1 3  and room = 'H' input = '1010110110000100000101011001011111010111' input += '1010011101001100000010001010011010110000' input += '0000100110010100010010110111000000010110' m = 7 F = GF(2) L_init = vector(F,input) d = len(L_init) M = matrix(F,d,d) for i in range(d): for j in range(-m,m+1 ): M[i,(i+j) % d] = 1 I = M.solve_right(L_init) K = M.right_kernel() ; K.dimension() lb = [(I+k).nonzero_positions() for k in K] la = [len((I+k).nonzero_positions()) for k in K] m = min(la) # print(m) notprinted = True res = "" for i in range(len(lb)): if m == la[i] and notprinted: for j in range(len(lb[i])): res += str(lb[i][j]+1) + " " #print(lb[i]) notprinted = False print(room + ' ' + res)  gives H 1 3 11 12 14 16 17 18 21 22 26 28 30 32 35 41 42 44 47 49 51 53 58 59 60 64 66 69 72 77 80 82 87 93 99 100 101 105 106 109 110 112 113 114 115 120  But the similar approach seems to be too slow on the cases I, J, K and L. So my question is how to shut down all lamps in those cases with minimal number of switch presses? I tried to run dan_fulea's code from the link but I was unable to read which switches should I press to shut down all lamps. I also saw the post https://math.stackexchange.com/questi... where was given an algorithm to solve the problem. But it looks too hard for me to implement it on Sagemath. This is my best approach to solve the case I but the algorithm seem to be too slow to finish computation: room = [] input = [] m = [] room.append('I') input.append('1110111111101000100110011001100110100000001010001100011110110011111100000101000010101101100111001000100110110101111000110101101000010000100110111101001001011010110100100111011000110001101011110100110011010111110101010100') m.append(27) F = GF(2) L_init = vector(F,input[0]) d = len(L_init) M = matrix(F,d,d) for i in range(d): for j in range(-m[0],m[0]+1 ): M[i,(i+j) % d] = 1 I = M.solve_right(L_init) K = M.right_kernel() best = None for k in K: A = (I+k).nonzero_positions() B= [] if len((I+k).nonzero_positions()) < best or best == None: S = room[0] + ' ' best = len((I+k).nonzero_positions()) for i in range(len(A)): S +=str(int(A[i])+1) + ' ' print(S) print("Optimal:") print(S)  2018-07-26 12:47:44 -0500 received badge ● Popular Question (source) 2018-07-19 08:10:04 -0500 received badge ● Nice Question (source) 2018-07-18 10:54:48 -0500 commented answer Solving an optimization problem by Sage Thanks for that! I think this proves the minimality of the example. But the case I would like to solve is much bigger. I think it might be solved by genetic algorithm of by simulated annealing but I have no experience of implementing those. 2018-07-16 23:44:03 -0500 received badge ● Associate Editor (source) 2018-07-16 11:56:45 -0500 received badge ● Popular Question (source) 2018-07-16 11:06:00 -0500 received badge ● Notable Question (source) 2018-07-16 10:04:04 -0500 asked a question Solving an optimization problem by Sage I would like to know how one can solve the following optimization problem using Sage. I would like to have a matrix where every element is an integer from 0 to 9. One can read numbers from the matrix by choosing the starting element and direction from one of the eight direction (horizontal, vertical, diagonal) and go to that direction 0 to 5 steps and concatenate the numbers. For example, one can read the squares of 1 to 10 from the following matrix: 0 0 1 8 2 3 6 4 9 5  Now the problem is to find an $n\times m$ matrix with digits from 0 to 9 where one can read the squares of 1 to 100 in a way described above where $nm$ is the smallest possible. How can I do that on Sage? Can Sage do it for example in the case 12x10 griid? Does for example simulated annealing or genetic algorithm work in here, or is it easy to implement the algorithm in https://stackoverflow.com/questions/9... ? I would like to see how good result we can achieve. 2018-04-03 14:29:06 -0500 received badge ● Popular Question (source) 2018-01-27 14:31:26 -0500 commented question Positive polynomial as a sum of squares I saw problems where was given polynomials with real coefficients and one variable and was asked to prove them to be positive. I was wondering a method to show them positive by completing them to a sum of squares. But I was not sure in what cases that gives a full proof as the coefficients are not always in closed form. I managed to do such proofs using Samuelson's inequality and then Sturm's theorem but I was wondering in which cases the sum of squares method provides a shorter proof. 2018-01-26 13:53:40 -0500 asked a question Positive polynomial as a sum of squares I found a question to prove the polynomial $58x^{10}-42x^9+11x^8+42x^7+53x^6-160x^5+118x^4+22x^3-56x^2-20x+74$ to be positive on $\mathbb{R}$. The solution was $(7x^5-4x^3+6x^2+2x-5)^2+(-3x^5+7x^4-3x^3+7)^2$. Is there a method in Sage to find such a representations? I tried the code modified from https://ask.sagemath.org/question/100... R = AA[x] def sum_of_two_squares(P): r""" P is assumed to be a polynomial defined on the Algebraic Real Field. Returns False is P is not positive. Returns a pair of polynomial (A,B) such that A^2 + B^2 = P otherwise """ # try to convert P if it is defined on a subfield of AA, say QQ. if P.parent() != R: P = P.change_ring(AA) LC = P.leading_coefficient() if LC < 0: return False # Q will be the part of P with real roots. Q = R(1) for i in P.roots(): if i[1] % 2 != 0: return False else: Q = Q * (R(x)-i[0])^i[1] if P == LC * Q: return (sqrt(LC) * sqrt(Q),R(0)) T = R(1) for fact,mult in R(P/Q).factor(): f = fact.change_ring(QQbar) T = T * (R(x)-f.roots()[0][0])^mult # extract real and imaginary part of T RE = R(0) IM = R(0) for i in range(T.degree()+1): RE += T[i].real()*R(x)^i IM += T[i].imag()*R(x)^i SLC = sqrt(LC) SQ = sqrt(Q) return (SLC*SQ*RE, SLC*SQ*IM) R = AA[x] P = R(58*x^10-42*x^9+11*x^8+42*x^7+53*x^6-160*x^5+118*x^4+22*x^3-56*x^2-20*x+74) A,B = sum_of_two_squares(P) A 7.615773105863908?*x^5 - 2.75743509005418?*x^4 - 44.2356981337271?*x^3 + 11.9854478203666?*x^2 + 25.5052589522359?*x - 3.05770635146248?  It looks like the code does not always find the simplest form of solution. So is there an algorithm that tries to find a representation such that it first tries to represent the polynomial as a sum of two constants, then sum of two polynomials of degree at most 1, then sum of two polynomials of degree at most 2 and so on and in every case the one can see the minimal polynomial of the coefficients over $\mathbb Q[x]$. 2017-12-06 15:43:26 -0500 received badge ● Good Question (source) 2017-11-09 10:44:37 -0500 marked best answer How to find an inverse of a matrix over a given field? How one can find an inverse of a matrix over a given finite field in Sage? 2017-11-07 08:45:39 -0500 received badge ● Nice Question (source) 2017-11-07 05:27:01 -0500 received badge ● Popular Question (source) 2017-11-01 07:36:33 -0500 commented question How to find a minimum number of switch presses to shut down all lamps? I'm looking for how small number of interrupters will turn of all the lamps so the second opinion of your question if I understood correctly. Let $n_x$ denote the number of switch presses that is required to turn all the lamps off in a room $x$. Then Metabolix and os have found switch presses such that $n_B+n_C+n_D+n_E+n_F+\ldots+n_L=1721$. The scoring system has also the property that the site adds $3600$ to the score if the given switches won't turn off all the lamps. Minimal score is better. 2017-10-30 15:28:53 -0500 marked best answer How to find a minimum number of switch presses to shut down all lamps? Is there a way to solve the following optimization problem in Sage given in https://www.ohjelmointiputka.net/post... : The following is an example case. I have $n=120$ lamps in a circle, and enumerated by $L_1,\ldots,L_{120}$. Some of them are switched on and some of them are switched off. I also have been given a positive integer $m=7.$ One every turn I choose one lamp $L_i$ and then the lamps $L_{i-m},\ldots,L_{i+m}$ will change their state, I mean if lamp $L_j$ was turned off then now it is turned on and vice versa. Indexes are modulo $n$ so the lamps $L_{118}, L_{119}, L_1,L_2$ are consecutive. What is the minimum number of turns to shut off all lamps and which switches one must press, if the initial states of the lamps are (from $L_1$ to $L_{120}$)  1010110110000100000101011001011111010111 1010011101001100000010001010011010110000 0000100110010100010010110111000000010110  where $1$ means that the corresponding lamp is on at the beginning and $0$ means that the corresponding lamp is off at the beginning. EDIT 1: It was wonderful to read the solutions given by dan_fulea and tmontell. I found that tmontell's solution works for some cases but are too brute force and too slow for harder cases, like input ='1110111111101000100110011001100110100000001010001100011110110011111100000101000010101101100111001000100110110101111000110101101000010000100110111101001001011010110100100111011000110001101011110100110011010111110101010100' m = 27 d = len(input) F = GF(2) L_init = vector(F,input) M = matrix(F,d,d) for i in range(d): for j in range(-m,m+1): M[i,(i+j) % d] = 1 I = M.solve_right(L_init) K = M.right_kernel(); m = min([len((I+k).nonzero_positions()) for k in K]) print (m)  My laptop won't solve that case. I tried the code by dan_fulea: def A( N, M ): F = GF(2) R = range(N) lists_for_M = [ [ (j+k) % N for k in range(M) ] for j in R ] return matrix( F, N, N, [ [ F(1) if k in lists_for_M[j] else F(0) for k in R ] for j in R ] ).transpose() N = 120 STR =""" 1010110110000100000101011001011111010111 1010011101001100000010001010011010110000 0000100110010100010010110111000000010110""" A0 = A( 120, 15 ) v = matrix( F, N, 1, [ F(int(s)) for s in STR if s in '01' ] ) w0 = vector( A0.solve_right( v ) ) def getString( vec, breakLength=40 ): # s = ''.join( [ str(entry) for entry in vec ] ) s = '' for count in range( len( vec ) ): s += str( vec[count] ) if (count+1) % breakLength == 0 and count < len(vec)-1 : s += '\n' return s minOperations = N+1 # default, it will become smaller soon solution = None # we change it, finally it will be the solution for u in A0.kernel(): vec = u + w0 nrOperations = len( vec.nonzero_positions() ) if nrOperations < minOperations: minOperations = nrOperations solution = vec print "New minOperations %s for\n%s\n" % ( minOperations, getString(vec) ) print "MINIMAL NUMBER OF OPERATIONS = %s" % minOperations print "SOLUTION IS:\n%s" % getString( solution ) # we can search for all solutions print "ALL SOLUTIONS:\n" for u in A0.kernel(): vec = u + w0 if minOperations == len( vec.nonzero_positions() ): print getString( vec ) print  The result was TypeError: unable to find a common ring for all elements  All cases in this problem are given as label, n.o. lamps, how many lamps original lamp states a switch affects per direction ================================================================================ B 6 1 101101 -------------------------------------------------------------------------------- C 10 2 1011010110 -------------------------------------------------------------------------------- D 20 1 11111011101010111111 -------------------------------------------------------------------------------- E 30 7 011100001010011011100001010011 -------------------------------------------------------------------------------- F 39 6 110100111111101000011000100110111100010 -------------------------------------------------------------------------------- G 53 9 0101100101111100100011100111101001001010 0010000010110 -------------------------------------------------------------------------------- H 120 7 1010110110000100000101011001011111010111 1010011101001100000010001010011010110000 0000100110010100010010110111000000010110 -------------------------------------------------------------------------------- I 220 27 1110111111101000100110011001100110100000 0010100011000111101100111111000001010000 1010110110011100100010011011010111100011 0101101000010000100110111101001001011010 1101001001110110001100011010111101001100 11010111110101010100 -------------------------------------------------------------------------------- J 500 87 1010001101101001110001101001000101010100 0001111111001101011000000011001111111011 1001110011010111111011010100010011011001 1001101110011011100001000111110101011111 1100111100001100110011101110101100001111 1100010010011010001111000000101110101101 1010100001100011111000111001000101101000 1011111111101111000000011111010001000000 1110011110111101010010011000000100010100 0011101011010011010110011110111000010010 0111100100011010010110001000011100101001 1110111010001001011001111011111011010110 10101101111011101110 -------------------------------------------------------------------------------- K 1002 83 0010100100100101000000110101111111101011 1101000101111110001110000110110110010101 1110110011011101100110111001110110010011 1101111010110011110101100001101010100011 1110001100011111110100011110100111111100 0011001011100110101100001101000001110010 0110100000100100100000011010000010111100 1110001110011110101001100111101101010000 0101010000011010011110101001001001000000 0011000100011011011001111010001101111000 0100001011010011001010111001111100110001 0011111110101101001100111101110000000000 1101100100000011000010010100010101001000 1100001000101001100110010100001000001101 1101000100001010011000101001101000100010 0011010001011101010100011101001101101100 0111110100110011001111000000001001001001 1001111001011111000010110000110010101000 1011001100111101000101000110000111010100 0010011011010111001101011001111000001011 1110101010101101111011111110100001100110 1000101100110011010000110000011011110011 0010000010000000111101101000001111101111 0100111110010101100011101001111101010000 1111100010011001110111111000101000000101 01 -------------------------------------------------------------------------------- L 2107 108 0111110100011000011111101110010101100011 1001111011101001001110111110001100011001 1001010100101011101101001000010111111111 1001101010111011110100100101000101100011 1110100010010010101110100000111100101000 0111101011111100010010110000100110100100 0100110101110010110011110010101101100111 1110010011000110110111010110010100101110 0111111101110000111001111100100010010001 1010110011000101100111111001011110101110 0111010110111110110101000101100100011000 1011000011011110001111100110100010100101 1101111100110011001110010010001010101111 1000001001000110011110010011011101110100 1011111100110010011000010110010110101010 0110101000011011110001010000010001000110 1001110101001001110110111111010011010111 1111011001000110111001000011101101110001 0000011111101000010101011111011011000011 1111000000011100010011011001011000110101 1101011111100001100010110010110011000000 0001001111100101110100100011011010011100 0000001111010101000111011000110110100001 1010110011100110111010111110110000010000 1000101001111001000110000101010000010111 1011100001000110001100010000001011101110 1001111110100010010000011000100101010101 1001001001110110101000001001001100001011 0011011100011111100111001110101101110001 0111010000010011110110011011000011101001 1111011010010000101111000010000001100110 1001011101001000010101001001011111111011 1000111000100001101100101110100011111100 1011001111101111110110101111101111011111 1001111100110101110101111110010010101101 1111111111000100100111100011101110110100 0100011011001010110100101101000000110010 0010010001001110110100011111100011111101 0100110111101101010101010100110110011011 0001111111000100000111011010101011000010 0011011110110110110100011001101111001000 1000000011110011100111100000001010010011 1000011101111100000101010101010010100101 1010001011010100011011001110110010100000 1000111101111000010111111101010110110111 0110001111100011001110000100100101001111 0000111111100010011001010000010110111000 1000110110001000001100110000001011000010 1000101101110000101100100010101111100011 1000010010111101000010000110011010000001 0010001100001000001100110111110100100111 1001100110001000100101011111001011001111 110001011111001101010101001 ================================================================================  EDIT 2: There is some approach on https://artofproblemsolving.com/commu... by the nickname TZF: Turns out this is a straight-up linear algebra problem over the field ${0,1}$. Addition in this field is equivalent to XOR. Let basis vector $i$ be the length-$n$ binary vector with elements $i-m,\ldots,i+m$ (all mod $n$) as 1's and the rest as 0's. When $(2m+1)$ is relatively prime with $n$, these vectors span the full space. The problem of finding the optimal set of switches to press is then equivalent to finding a representation of the original binary state vector in the above basis, which can be done using Gaussian elimination. I haven't explored the runtime of doing Gaussian elimination on the particular binary circulant basis in this problem (it benefits from sparsity and a clean structure), but if it's suboptimal runtime-wise, I'd imagine there might be a way to employ an FFT to speed up the solution. Would this approach be a fast enough for this problem?