Sum of a series in Prolog

Question

I want to find sum of a series using Prolog program . For this purpose , I have written the following program :

pow(N,1,R):- R is N.
pow(N,M,R):- X is M-1,pow(N,X,R1),R is R1*N.

sum(N,1,R) :- R is N+1 . 
sum(N,M,R) :- X is M-1, X>1,sum(N,X,R1),pow(N,M,R2), R is (R1+R2).

I want to find the sum of following series :

1+n+n^2+n^3+..................+n^m

My believe is the above code is right . But when I run the program , it shows output "No" . Why ? I have tried a lot , but could not get expected output .

Answer 1

you miss the else branch of X>1, and if you remove it, you get a result:

...
sum(N,M,R) :- X is M-1, sum(N,X,R1), pow(N,X,R2), R is (R1+R2).
...
?- sum(2,3,X).
X = 15 ;
^C

but the program doesn't terminate (^C used to interrupt the loop).

I would rewrite using an accumulator, to get the better efficiency allowed by LCO (Last Call Optimization) and the built in pow:

sum(N,M,R) :- sum(N,M,0,R).

sum(N,M,A,R) :-
    (   M > 0
    ->  A1 is A + N^M, %% N**M,
        M1 is M-1,
        sum(N,M1,A1,R)
    ;   R is A + 1
    ).

edit SWI-Prolog documentation about operator (**)/2 is incorrect: better to use (^)/2, as remarked by @false