Ninety-Nine Picat Problems


Determine whether a given integer number is prime.

% isPrime(K) => prime(K).

prime(2) => true.
prime(3) => true.
prime(N),N > 3 =>
    foreach (I in 3..2..sqrt(N))
       N mod I != 0


Determine the prime factors of a given positive integer.
Construct a flat list containing the prime factors in
ascending order.

primeFactors(N) = primeFactorsAux(N,2).

primeFactorsAux(N,F) = Res, F*F > N => Res = [N].
primeFactorsAux(N,F) = Res,
    N mod F == 0
    Res = [F|primeFactorsAux(N div F,F)].
primeFactorsAux(N,F) = primeFactorsAux(N,F+1).


Determine the prime factors of a given positive integer.

prime_factors_mult(N) = Res =>
    Pairs = primeFactors(N).encode(),         % see P1_10
    Res = [(I,Count) : (Count,I) in Pairs].


A list of prime numbers.

Given a range of integers by its lower and upper limit,
construct a list of all prime numbers in that range.

primesR(A,B) = [P : P in primes(B), P >= A].


Goldbach's conjecture.
Goldbach's conjecture says that every positive even number
greater than 2 is the sum of two prime numbers.
Example: 28 = 5 + 23.

goldbach(N) = first([(X,Y) : X in primesR(2, N-2), Y = N-X, prime(Y)]).


A list of Goldbach compositions.

a) Given a range of integers by its lower and upper limit,
print a list of all even numbers and their Goldbach

b) In most cases, if an even number is written as the sum
of two prime numbers, one of them is very small. Very rarely,
the primes are both bigger than say 50. Try to find out how
many such cases there are in the range 2..3000.

goldbach_list(From,To) =>
    foreach(N in max(4,From)..To, even(N))
        (P1,P2) = goldbach(N),
        printf("%w = %w + %w\n",N,P1,P2)

goldbach_list_2(From,To,M) =>
    foreach(N in max(4,From)..To, even(N), (P1,P2) = goldbach(N), P1 >= M, P2 >= M)
        printf("%w = %w + %w\n",N,P1,P2)


Determine the greatest common divisor of two positive
integer numbers. Use Euclid's algorithm.

myGCD(A,0) = abs(A).
myGCD(A,B) = myGCD(B, A mod B).


Determine whether two positive integer numbers are coprime.
Two numbers are coprime if their greatest common divisor
equals 1.

coprime(A,B) => gcd(A,B) == 1.


Calculate Euler's totient function phi(m).
Euler's so-called totient function phi(m) is defined as the
number of positive integers r (1 <= r < m) that are coprime
to m.

totient(N) = length([X : X in 1..N, coprime(X,N)]).


Calculate Euler's totient function phi(m) (improved).

totient2(M) = prod([(P - 1) * P ** (C - 1) : (P, C) in prime_factors_mult(M)]).


Compare the two methods of calculating Euler's totient

% no code