Prolog power of 2 recursion

Question

Need help creating a recursive clause is a rule: X is a power of 2 only if there is a Y such that when adding Y to Y the result is X, and Y is a power of 2. in prolog

We are going to define this predicate recursively. The followings are the fact and rule for detecting whether a numeral is a power of 2 or not:

• The base clause is a fact: 1 is a power of 2 (because 1=20);
• The recursive clause is a rule: X is a power of 2 only if there is a Y such that when adding Y to Y the result is X, and Y is a power of 2.

For example, the following shows how the queries should be performed:

| ?- powerOf2(succ(succ(succ(succ(0))))). true ?
yes

| ?- powerOf2(succ(succ(succ(0)))). no

The first query shows that 4 is a power of 2; while the second shows that 3 is not.

• can not use the built-in is/2 predicate to perform arithmetic

Answer 1

Need help creating a recursive clause

The recursive clause will be:

power_of_two(1).
power_of_two(X) :-
    X > 1,
    Y is X / 2,
    power_of_two(Y).

A base case which handles 1 being a power of two. And a case which handles when X is greater than one, Y is half X and recursively checks that Y is a power of two.

can not use the built-in is/2 predicate to perform arithmetic

You can't, but I can for the sake of illustrating the recursive clause you asked about. I'm assuming that since it tells you to use "succ(succ(succ(succ(0))))" you already have met that and have some code for adding/subtracting/dividing which you can reuse to replace Y is X / 2.

Answer 2

To make it easier to represent natural numbers in Peano notation, you can use the following predicate:

nat(0, 0).
nat(N, s(P)) :-
    succ(M, N),
    nat(M, P).

Examples:

?- nat(3, P).
P = s(s(s(0))) ;
false.

?- nat(5, P).
P = s(s(s(s(s(0))))) ;
false.

To get the double of a Peano number, use the predicate:

double(0, 0).
double(s(A), s(s(B))) :-
    double(A, B).

Examples:

?- nat(1, P), double(P, D).
P = s(0),
D = s(s(0)) ;
false.

?- nat(3, P), double(P, D).
P = s(s(s(0))),
D = s(s(s(s(s(s(0)))))) ;
false.

To check whether a Peano number is a power of two, use the predicate:

power_of_two(s(0)).
power_of_two(s(s(N))) :-
    double(M, s(s(N))),
    power_of_two(M).

Example:

?- between(1,9,N), nat(N,P), power_of_two(P).
N = 1,
P = s(0) ;
N = 2,
P = s(s(0)) ;
N = 4,
P = s(s(s(s(0)))) ;
N = 8,
P = s(s(s(s(s(s(s(s(0)))))))) ;
false.