CODEWITHSUNDEEP
prolog
Kalev Kärpuk
Kalev Kärpuk

Reputation: 41

Prolog program finding sum of multiple numbers' power of 4

I am trying to study for me exams and have the following problem:

"Write a Prolog program that finds numbers a1,....a14 so that a1^4+....+a14^4=2013

?-solve([A1,A2,...A13]).

Its not just a "random homework task I need someone to solve it for me". Rather an assignement given to learn for the exams

How would you solve this problem?

Upvotes: 0

Views: 540

Answers (4)

mat
mat

Reputation: 40768

If all numbers must be integer, consider using finite domain constraints. For example, with SWI-Prolog:

:- use_module(library(clpfd)).

solution(Vs) :-
        length(Vs, 14),
        Vs ins 0..sup,
        chain(Vs, #=<),
        maplist(pow4, Vs, Ps),
        sum(Ps, #=, 2013).

pow4(X, Y) :- Y #= X^4.

It turns out that the solution is unique up to ordering:

?- solution(Vs), label(Vs).
Vs = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 5, 6] ;
false.

Upvotes: 1

CapelliC
CapelliC

Reputation: 60034

Your problem leave some freedom degree about interpretation.

Let's say that you can restrict your set of numbers with an upper bound.

Then a naive 'generate and test' is easy to write, but hopeless inefficient.

find_4th_power_sum(CountNumbers, Target, Numbers) :-
    U is floor(Target^(1/4)), % upper bound
    length(Numbers, CountNumbers),
    maplist(gen_4th_power(U), Numbers, Powers),
    sum_list(Powers, Target).

gen_4th_power(U, N, Pow4th) :-
    between(0, U, N),
    Pow4th is N^4.

alas, even if floor(Target^(1/4)) is just 6, the full search space is

?- X is 7^13.
X = 96889010407.

The problem is redundancy: any permutation of a solution will be a solution itself.

I would stick to a less Prolog-ish way: do a cycle subtracting from Target the floor(Target^(1/4)), and make that the new target, until Target is 1. Keep the numbers list on the way.

Of course, this is how I would approach the problem in any imperative program...

Here is the code:

list_4th_power_sum(CountNumbers, Target, [N|Numbers]) :-
    (   Target > 1
    ->  N is floor(Target^(1/4)),
        Target1 is Target-N^4,
        CountNumbers1 is CountNumbers-1,
        list_4th_power_sum(CountNumbers1, Target1, Numbers)
    ;   N = 1,
        findall(0, between(1,CountNumbers,_), Numbers)
    ).

To my surprise, the filling by 0, i.e. findall(0, between(1,CountNumbers,_), Numbers) turns out to be useless...

Upvotes: 0

Ian Dickinson
Ian Dickinson

Reputation: 13315

In general, this pattern is a "generate and test" problem. You need to break it down into manageable pieces:

  • generate a list of N numbers (e.g. N = 14 in your case)
  • test that the sum of the fourth-powers of those numbers sums to target M (in your case, this is 2013)
  • use backtracking to find all solutions

For the generate case, since you're raising to the fourth power you know that all of the terms will be positive, so there's no point generating a number A such that A^4 > 2013. So each of the As will be between zero and the floor of the fourth root of 2013.

For the test case, I would break that down into two steps: write a map predicate to map the list of As to a list of A^4, then a predicate to sum the list and test whether it's the target value.

Upvotes: 0

User
User

Reputation: 14883

I would take the sentence and transform it until prolog comes out:

Write a Prolog program that finds numbers a1,....a14 so that a1^4+....+a14^4=2013

=

finds numbers a1,....a14 all >= 0 and < 2013
so that a1^4+....+a14^4=2013

= 

between(0, 2013, A1), and so on
 A1^4+....+A14^4 = 2013

something like this.

Upvotes: 0

Related Questions