/* Euler #43 in Picat. """ The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property. Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following: * d2d3d4=406 is divisible by 2 * d3d4d5=063 is divisible by 3 * d4d5d6=635 is divisible by 5 * d5d6d7=357 is divisible by 7 * d6d7d8=572 is divisible by 11 * d7d8d9=728 is divisible by 13 * d8d9d10=289 is divisible by 17 Find the sum of all 0 to 9 pandigital numbers with this property. """ This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import util. import cp. main => go. go => time(euler43). % , time(euler43b). % using CP is fast: 0.05s euler43 => Primes = [2,3,5,7,11,13,17], X = new_list(10), X :: 0..9, all_different(X), foreach({I,P} in zip(2..8, Primes)) (100*X[I]+10*X[I+1]+X[I+2]) mod P #= 0 end, All=solve_all(X), Sum = 0, foreach(A in All) to_num(A, 10, Num), % writeln(A), Sum := Sum + Num end, writeln(sum=Sum), nl. to_num(List, Base, Num) => Len = length(List), Num = sum([List[I]*Base**(Len-I) : I in 1..Len]). % Here is Neng-Fa's simplification of euler43/0: euler43b => Primes = [2,3,5,7,11,13,17], X = new_list(10), X :: 0..9, all_different(X), foreach({I,P} in zip(2..8, Primes)) (100*X[I]+10*X[I+1]+X[I+2]) mod P #= 0 end, All=solve_all(X), writeln(sum([to_num2(A) : A in All])), nl. to_num2(List) = Num => Str = [Char : D in List, D.to_string()=[Char]], Num = Str.to_integer(). /* % Notes: % % - got this error/warning ** Error : assignment_in_condition:while % - it eats a lot of memory % - it's very slow % % 34.7s euler43c => PP = [2, 3, 5, 7, 11, 13, 17], % skipping all permutations that starts with [0,..] S = [1, 0, 2, 3, 4, 5, 6, 7, 8, 9], Sum = 0, Sdown = S.sort_down(), while (S != Sdown) S2 = S.to_string(), I = 1, % it's here the "assignment_in_condition:while" error come while (I =< 7, [S[J].to_string() : J in 1+I..I+3].flatten().to_integer() mod PP[I] == 0) I := I + 1 end, if I == 8 then println(s2=S2), Sum := Sum + [S[J].to_string() : J in 1..S.length].flatten().to_integer() end, S := next_permutation(S) end, println(Sum). next_permutation(P) = Perm => Perm1 = P, N = Perm1.length, K = N - 1, while (Perm1[K] > Perm1[K+1], K >= 0) K := K - 1 end, % if K == 0 then Perm1 := [] end, % return if K > 0 then J = N, while (Perm1[K] > Perm1[J]) J := J - 1 end, Tmp := Perm1[K], Perm1[K] := Perm1[J], Perm1[J] := Tmp, R = N, S = K + 1, while (R > S) Tmp := Perm1[R], Perm1[R] := Perm1[S], Perm1[S] := Tmp, R := R - 1, S := S + 1 end end, Perm = Perm1. */