/* Number Chain in Picat. From Chris Smith Math Newsletter #515 """ I think I had something about this in the newsletter, inspired by Matt Parker (yes, him again!), a while back but saw an animated version of this on Twitter and thought it was worth sharing even if it’s a repeat! Thanks to @rainmaker1973... see the post here: https://t.co/8KR0dSsANQ [...] This chain contains every integer from 1 to 35...the sum of any pair of consecutive integers is a square number. It’s conjectured that you’ll be able to create a chain like this for all integers greater than 24. """ This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import cp,util. main => go. % % all 342 solutions for circular number chains for N=35 with symmetry breaking. % go ?=> N = 35, Circular = true, Symmetry = true, number_chain(N, X, Circular,Symmetry), println(x=X), fail, nl. go => true. /* Checks for which n there are (and are not) solutions. Test non circular number chains: Non circular without symmetry breaking: 1 = [1] 2 = no_solution 3 = no_solution 4 = no_solution 5 = no_solution 6 = no_solution 7 = no_solution 8 = no_solution 9 = no_solution 10 = no_solution 11 = no_solution 12 = no_solution 13 = no_solution 14 = no_solution 15 = [8,1,15,10,6,3,13,12,4,5,11,14,2,7,9] 16 = [8,1,15,10,6,3,13,12,4,5,11,14,2,7,9,16] 17 = [16,9,7,2,14,11,5,4,12,13,3,6,10,15,1,8,17] 18 = no_solution 19 = no_solution 20 = no_solution 21 = no_solution 22 = no_solution 23 = [2,23,13,12,4,21,15,10,6,19,17,8,1,3,22,14,11,5,20,16,9,7,18] 24 = no_solution 25 = [2,23,13,12,24,25,11,14,22,3,1,8,17,19,6,10,15,21,4,5,20,16,9,7,18] 26 = [2,14,22,3,13,23,26,10,6,19,17,8,1,15,21,4,12,24,25,11,5,20,16,9,7,18] 27 = [1,8,17,19,6,3,13,12,24,25,11,14,22,27,9,16,20,5,4,21,15,10,26,23,2,7,18] 28 = [1,15,10,26,23,13,3,6,19,17,8,28,21,4,12,24,25,11,5,20,16,9,27,22,14,2,7,18] 29 = [1,24,25,11,5,4,12,13,3,6,19,17,8,28,21,15,10,26,23,2,14,22,27,9,16,20,29,7,18] 30 = [1,24,25,11,5,4,12,13,3,6,30,19,17,8,28,21,15,10,26,23,2,14,22,27,9,16,20,29,7,18] 31 = [1,15,10,6,30,19,17,8,28,21,4,5,31,18,7,29,20,16,9,27,22,3,13,12,24,25,11,14,2,23,26] 32 = [1,8,28,21,4,32,17,19,30,6,3,13,12,24,25,11,5,31,18,7,29,20,16,9,27,22,14,2,23,26,10,15] 33 = [1,8,28,21,4,32,17,19,30,6,3,13,12,24,25,11,5,20,29,7,18,31,33,16,9,27,22,14,2,23,26,10,15] 34 = [1,3,6,19,30,34,2,7,18,31,33,16,9,27,22,14,11,25,24,12,13,23,26,10,15,21,28,8,17,32,4,5,20,29] 35 = [1,3,6,19,30,34,2,7,18,31,33,16,9,27,22,14,11,25,24,12,13,23,26,10,15,21,28,8,17,32,4,5,20,29,35] Non circular with symmetry breaking: 1 = [1] 2 = no_solution 3 = no_solution 4 = no_solution 5 = no_solution 6 = no_solution 7 = no_solution 8 = no_solution 9 = no_solution 10 = no_solution 11 = no_solution 12 = no_solution 13 = no_solution 14 = no_solution 15 = no_solution 16 = no_solution 17 = no_solution 18 = no_solution 19 = no_solution 20 = no_solution 21 = no_solution 22 = no_solution 23 = [2,23,13,12,4,21,15,10,6,19,17,8,1,3,22,14,11,5,20,16,9,7,18] 24 = no_solution 25 = [2,23,13,12,24,25,11,14,22,3,1,8,17,19,6,10,15,21,4,5,20,16,9,7,18] 26 = [2,14,22,3,13,23,26,10,6,19,17,8,1,15,21,4,12,24,25,11,5,20,16,9,7,18] 27 = [1,8,17,19,6,3,13,12,24,25,11,14,22,27,9,16,20,5,4,21,15,10,26,23,2,7,18] 28 = [1,15,10,26,23,13,3,6,19,17,8,28,21,4,12,24,25,11,5,20,16,9,27,22,14,2,7,18] 29 = [1,24,25,11,5,4,12,13,3,6,19,17,8,28,21,15,10,26,23,2,14,22,27,9,16,20,29,7,18] 30 = [1,24,25,11,5,4,12,13,3,6,30,19,17,8,28,21,15,10,26,23,2,14,22,27,9,16,20,29,7,18] 31 = [1,15,10,6,30,19,17,8,28,21,4,5,31,18,7,29,20,16,9,27,22,3,13,12,24,25,11,14,2,23,26] 32 = [1,8,28,21,4,32,17,19,30,6,3,13,12,24,25,11,5,31,18,7,29,20,16,9,27,22,14,2,23,26,10,15] 33 = [1,8,28,21,4,32,17,19,30,6,3,13,12,24,25,11,5,20,29,7,18,31,33,16,9,27,22,14,2,23,26,10,15] 34 = [1,3,6,19,30,34,2,7,18,31,33,16,9,27,22,14,11,25,24,12,13,23,26,10,15,21,28,8,17,32,4,5,20,29] 35 = [1,3,6,19,30,34,2,7,18,31,33,16,9,27,22,14,11,25,24,12,13,23,26,10,15,21,28,8,17,32,4,5,20,29,35] */ go2 => nolog, Circular = false, Symmetry = false, println([circular=Circular,symmetry=Symmetry]), N = 135, foreach(I in 1..N) if number_chain(I,X,Circular,Symmetry) then println(I=X) else println(I=no_solution) end end, nl. % Non circular with symmetry go3 => nolog, Circular = false, Symmetry = true, println([circular=Circular,symmetry=Symmetry]), N = 135, foreach(I in 1..N) if number_chain(I,X,Circular,Symmetry) then println(I=X) else println(I=no_solution) end end, nl. % Circular with symmetry go4 => nolog, Circular = true, Symmetry = true, println([circular=Circular,symmetry=Symmetry]), N = 135, foreach(I in 1..N) if number_chain(I,X,Circular,Symmetry) then println(I=X) else println(I=no_solution) end end, nl. % circular without symmetry go5 => nolog, Circular = true, Symmetry = true, println([circular=Circular,symmetry=Symmetry]), N = 135, foreach(I in 1..N) if number_chain(I,X,Circular,Symmetry) then println(I=X) else println(I=no_solution) end end, nl. % % Number of solutions of N=1..35 % % Circular, symmetry breaking % [circular = false,symmetry = false] % [1,0,0,0,0,0,0,0,0,0,0,0,0,0,2,2,2,0,0,0,0,0,6,0,20,24,70,104,38,40,698,784,1338,8082,34350] % % [circular = false,symmetry = true] % [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,2,1,6,6,2,2,101,89,121,643,2430] % % [circular = true,symmetry = false] % [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,64,66,748,3990] % % [circular = true,symmetry = true] % [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,6,6,66,342] % go6 => foreach(Circular in [false,true]) foreach(Symmetry in [false,true]) Counts = [], foreach(N in 1..35) Count = count_all(number_chain(N,_,Circular,Symmetry)), Counts := Counts ++ [Count] end, println([circular=Circular,symmetry=Symmetry]), println(Counts), nl end end, nl. % count the "square neighbours" for numbers 1..N % For N=10 test_square_neighbours => N = 135, Squares = [I*I : I in 1..N], M = new_array(N,N), bind_vars(M,0), foreach(I in 1..N) S = [J : J in 1..N, member(I+J,Squares)], IsSquare = cond(member(I,Squares),true,false), println(I=S.len=IsSquare), foreach(J in S) M[I,J] := 1 end end, nl. number_chain(N, X) => number_chain(N, X, true,true). number_chain(N, X, Circular,Symmetry) => Squares = [I*I : I in 1..N], X = new_list(N), X :: 1..N, all_different(X), Ss = [], foreach(I in 2..N) S :: Squares, X[I-1] + X[I] #= S, Ss := Ss ++ [S] end, % around the corner if Circular then S :: Squares, X[1] + X[N] #= S, Ss := Ss ++ [S] end, % symmetry breaking % There are most candidates for 1..3 (see experiments in test_square_neighbours/0). if Symmetry then X[1] :: 1..3 % X[1] #< X[N] end, Vars = X ++ Ss, solve($[ff,split],Vars).