/*
Chinese Remainder problem in Picat.
http://en.wikipedia.org/wiki/Chinese_remainder_theorem
"""
In its basic form, the Chinese remainder theorem will determine a
number n that when divided by some given divisors leaves given
remainders. For example, what is the lowest number n that when
divided by 3 leaves a remainder of 2, when divided by 5 leaves a
remainder of 3, and when divided by 7 leaves a remainder of 2?
"""
This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
import cp.
main => go.
go =>
Divs = [3,5,7],
Rems = [2,3,2],
X :: 1..10000,
crt(Divs,Rems,X),
solve([X]),
println(X),
nl.
go2 =>
Max = 30,
Primes = primes(Max),
println(primes=Primes),
Len = Primes.length,
Divs = [Primes[1+random2() mod Len] : _I in 1..Len].sort_remove_dups(),
Rems = [1+random2() mod (Divs[I]-1) : I in 1..Divs.length],
println(divs=Divs),
println(rems=Rems),
% X :: 0..10000000,
crt(Divs,Rems,X),
solve([ff,split],[X]),
println(X),
nl.
% https://groups.google.com/forum/#!topic/rec.puzzles/bK6Gxz1H8LI
% """
% What is smallest possible number which when divided by 2,3,5,7,9 and 11
% leaves remainder 1,2,3,4,5 & 6 respectively.
% Here method to find the answer is more important than answer.
% """
go3 =>
Divs = [2,3,5,7,9,11],
Rems = [1,2,3,4,5,6],
crt(Divs,Rems,X),
solve([X]),
println(X),
nl.
crt(Divs,Rems, X) =>
X #>= 0,
foreach({D,R} in zip(Divs,Rems))
X mod D #= R
end.