Goldbach’s conjecture says that every positive even number greater than 2 is the sum of two prime numbers. Write a predicate goldbach(N, L) that returns L as a list of the two prime numbers that sum up to the given N (which must be even).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41goldbach(4, [2, 2]) :-
!.
goldbach(N, L) :-
N mod 2 =:= 0,
N > 4,
goldbach(N, L, 3).
goldbach(N, [P, Q], P) :-
Q is N - P,
is_prime(Q),
Q > P.
goldbach(N, L, P) :-
P < N,
!,
next_prime(P1, P),
goldbach(N, L, P1).
next_prime(P1, P) :-
P1 is P + 2,
is_prime(P1),
!.
next_prime(P1, P) :-
P2 is P + 2,
next_prime(P1, P2).
is_prime(2).
is_prime(3).
is_prime(P) :-
P > 3,
P mod 2 =\= 0,
\+ has_factor(P, 3).
% has_factor(N, L) :- N has an odd factor F >= L
has_factor(N, L) :-
N mod L =:= 0.
has_fator(N, L) :-
L * L < N,
L2 is L + 2,
has_factor(N, L2).
% goldbach(12, L), write(L), nl, fail; true.Eliminate consecutive duplicates of list elements. (P-99: Ninety-Nine Prolog Problems - P08)
Doubt - Does this cut work?
1
2
3
4
5
6
7compress([], []).
compress([H, H | T], Res) :-
!,
compress([H | T], Res).
compress([H | T], [H | Res]) :-
compress(T, Res).or
1
2
3
4
5
6
7
8
9
10
11
12
13
14% compress(L1,L2) :-
% (list,list) (+,?)
% the list L2 is obtained from the list L1 by
% compressing repeated occurrences of elements into a single copy
% of the element.
compress([], []).
compress([X], [X]).
compress([X, X|Xs], Zs):-
compress([X|Xs], Zs).
compress([X, Y|Xs], [X|Zs]):-
X \= Y,
compress([Y|Xs], Zs).or
1
2
3
4
5
6
7
8
9compress([],[]).
compress([H|T],[H|T2]):-
delete_all_prefix(H,T,T3),
compress(T3,T2).
delete_all_prefix(X,[X|T],T2):-
!,
delete_all_prefix(X,T,T2).
delete_all_prefix(_,L,L).Pack consecutive duplicates of list elements into sublists. (P-99: Ninety-Nine Prolog Problems - P09)
1
2
3
4
5
6
7
8
9
10
11
12
13% pack(L1,L2) :- the list L2 is obtained from the list L1 by packing
% repeated occurrences of elements into separate sublists.
% (list,list) (+,?)
pack([],[]).
pack([X|Xs],[Z|Zs]) :- transfer(X,Xs,Ys,Z), pack(Ys,Zs).
% transfer(X,Xs,Ys,Z) Ys is the list that remains from the list Xs
% when all leading copies of X are removed and transfered to Z
transfer(X,[],[],[X]).
transfer(X,[Y|Ys],[Y|Ys],[X]) :- X \= Y.
transfer(X,[X|Xs],Ys,[X|Zs]) :- transfer(X,Xs,Ys,Zs).or
1
2
3
4
5
6
7
8
9
10pack([], []).
pack([H|T], [Prefix | T2]) :-
pack_helper(H, [H|T], Prefix, Rest),
pack(Rest, T2).
% pack_helper(+E, +L, -Prefix, -Rest).
pack_helper(E, [E|T], [E|T2], R) :-
!,
pack_helper(E, T, T2, R).
pack_helper(_, L, [], L).Run-length encoding of a list.
1
encode(L, R) :-
pack(L, L2),
map1(L2, R).
map([], []).
map([[H2 | T2] | T, [(N, H2) | T3]) :-
length([H2 | T2], N),
map(T, T3).
length([], 0).
length([_ | T], N) :-
length(T, N2),
N is N2 + 1.
decode([], []).
decode([(N, H) | T], L) :-
unfold(N, H, L2),
decode(T, L3),
append(L2, L3, L).
unfold(0, _, []).
unfold(N, X, [X|T]) :-
N > 0,
N1 is N - 1,
unfold(N1, X, T).
append([], L, L).
append([H|T], L, [H, T2]):-
append(T, L, T2).
range(Min, Max, L) :-
Min >= Max,
!.
range(Min, Max, [Min|L}):-
X is Min + 1,
range(X, Max, L).
graph
:- import member/2, length/2, select/3 from basics.
adjacent(X, Y, graph(_, Es)).
% undirected graph:
degree(graph(_, Es), N, D) :-
degreeHelper(Es, N, 0, D).
degreeHelper([], _, PD, PD).
degreeHelper([X|T], N, PD, D) :-
(
X = e(N, _);
X =
)
degreeHelper()
% Alternative solution
degree2(graph(_, Es), N, D) :-
findall(Y, (member(e(N, Y), Es); member(e(Y, N), Es)), L),
length(L, D).
flatten(X, [X]):-
var(X),
!.
flatten([], []) :-
!.
flatten(X, [X]) :-
atomic(X).
flatten([H|T], L) :-
flatten(H, L2),
flatten(T, L3),
append(L2, L3, L).
Tricks
How to show the whole list when the list contains more than 9 items?
?- Solution(S); true.
S = [a, b, c, … | …] (press w here) then the full solution will show in next line.