CODEWITHSUNDEEP
prologprimes
tjg92
tjg92

Reputation: 197

Prolog Loops until True

I'm pretty new to Prolog but I'm trying to get this program to give me the first set of twin primes that appears either at or above N.

twins(M) :- 
            M2 is M + 2,
            twin_prime(M, M2),
            write(M),
            write(' '),
            write(M2).
            M3 is M + 1,
            twins(M3).

However, I'm not completely sure how to go about getting it to loop and repeat until it's true. I've tried using the repeat/0 predicate but I just get stuck in an infinite loop. Does anyone have any tips I could try? I'm pretty new to Prolog.

Upvotes: 1

Views: 1746

Answers (2)

Shon
Shon

Reputation: 4098

You're on the right track using tail recursion and @Jake Mitchell's solution works swell. But here are some tips that might help clarify a few basic concepts in Prolog:

First, it seems like your predicate twins/1 is actually defining a relationship between 2 numbers, namely, the two twin primes. Since Prolog is great for writing very clear, declarative, relational programs, you might make the predicate more precise and explicit by making it twin_primes/2. (That this should be a binary predicate is also pretty clear from your name for the predicate, since one thing cannot be twins...)

One nice bonus of explicitly working with a binary predicate when describing binary relations is that we no longer have to fuss with IO operations to display our results. We'll simply be able to query twin_primes(X,Y) and have the results returned as Prolog reports back on viable values of X and Y.

Second, and more importantly, your current definition of twins/1 wants to describe a disjunction: "twins(M) is true if M and M + 2 are both prime or if M3 is M + 3 and twins(M3) is true". The basic way of expressing disjunctions like this is by writing multiple clauses. A single clause of the form <Head> :- <Body> declares that the Head is true if all the statements composing the Body are true. Several clauses with the same head, like <Head> :- <Body1>. <Head> :- <Body2>. ..., declare that Head is true if Body1 is true or if Body2 is true. (Note that a series of clauses defining rules for a predicate are evaluated sequentially, from top to bottom. This is pretty important, since it introduces non-declarative elements into the foundations of our programs, and it can be exploited to achieve certain results.)

In fact, you are only a small step from declaring a second rule for twins/1. You just tried putting both clause-bodies under the same head instance. Prolog requires the redundant measure of declaring two different rules in cases like this. Your code should be fine (assuming your definition of twin_prime/2 works), if you just change it like so:

twins(M)    :-  
            M2 is M + 2,
            twin_prime(M, M2),
            write(M),
            write(' '),
            write(M2).
twins(M)  :-
            \+twin_prime(M, M2),     %% `\+` means "not"
            M3 is M + 1,
            twins(M3).

Note that if you take advantage of Prolog's back-tracking, you often don't actually need to effect loops through tail recursion. For example, here's an alternative approach, taking into account some of what I advised previously and using a quick (but not as in "efficient" or "fast") and dirty predicate for generating primes:

prime(2).
prime(P) :-
    between(2,inf,P),
    N is (P // 2 + 1),
    forall(between(2,N,Divisor), \+(0 is P mod Divisor)).

twin_primes(P1, P2) :-
    prime(P1),
    P2 is P1 + 2,
    prime(P2).

twin_primes/2 gets a prime number from prime/1, then calculates P2 and checks if it is prime. Since prime/1 will generate an infinite number of primes on backtracking, twin_primes/2 will just keep asking it for numbers until it finds a satisfactory solution. Note that, if called with two free variables, this twin_primes/2 will generate twin primes:

?- twin_primes(P1, P2).
P1 = 3,
P2 = 5 ;
P1 = 5,
P2 = 7 ;
P1 = 11,
P2 = 13 ;
P1 = 17,
P2 = 19 ;
P1 = 29,
P2 = 31 ;

But it will also verify if two numbers are twin primes if queried with specific values, or give you the twin of a prime, if it exists, if you give a value for P1 but leave P2 free:

?- twin_primes(3,Y). Y = 5.

Upvotes: 4

Sage Mitchell
Sage Mitchell

Reputation: 1583

There's a handy if-then-else operator that works well for this.

twin_prime(3,5).
twin_prime(5,7).
twin_prime(11,13).

next_twin(N) :-
    A is N+1,
    B is N+2,
    (twin_prime(N,B) ->
     write(N),
     write(' '),
     write(B)
    ;
     next_twin(A)).

And a quick test:

?- next_twin(5).
5 7
true.

?- next_twin(6).
11 13
true.

Upvotes: 1

Related Questions