Arithmetics in Prolog, represent a number using powers of 2

Question

I have two numbers, let's name them N and K, and I want to write N using K powers of 2.

For example if N = 9 and K = 4, then N could be N = 1 + 2 + 2 + 4 (2^0 + 2^1 + 2^1 + 2^2).

My program should output something like N = [1,2,2,4].

I am used to C++. I can't find a way to solve this problem in Prolog. Any help will be appreciated!

Answer 1

Here's a scheme that uses CLP(FD). In general, when reasoning in the domain of integers in Prolog, CLP(FD) is a good way to go. The idea for this particular problem is to think recursively (as in many Prolog problems) and use a "bifurcation" approach.

As David said in his answer, solutions to problems like this don't just flow out on the first attempt. There are preliminary notions, trial implementations, tests, observations, and revisions that go into coming up with the solution to a problem. Even this one could use more work. :)

:- use_module(library(clpfd)).

% Predicate that succeeds for power of 2
power_of_2(1).
power_of_2(N) :-
    N #> 1,
    NH #= N // 2,
    N #= NH * 2,
    power_of_2(NH).

% Predicate that succeeds for a list that is monotonically ascending
ascending([_]).
ascending([X1,X2|Xs]) :-
    X1 #=< X2,
    ascending([X2|Xs]).

% Predicate that succeeds if Partition is a K-part partition of N
% where the parts are powers of 2
binary_partition(N, K, Partition) :-
    binary_partition_(N, K, Partition),
    ascending(Partition).    % Only allow ascending lists as solutions

binary_partition_(N, 1, [N]) :- % base case
    power_of_2(N).
binary_partition_(N, K, P) :-
    N #> 1,                  % constraints on N, K
    K #> 1,
    length(P, K),            % constraint on P
    append(LL, LR, P),       % conditions on left/right bifurcation
    NL #> 0,
    NR #> 0,
    KL #> 0,
    KR #> 0,
    NL #=< NR,               % don't count symmetrical cases
    KL #=< KR,
    N #= NL + NR,
    K #= KL + KR,
    binary_partition_(NL, KL, LL),
    binary_partition_(NR, KR, LR).

This will provide correct results, but it also generates redundant solutions:

2 ?- binary_partition(9,4,L).
L = [1, 2, 2, 4] ;
L = [1, 2, 2, 4] ;
false.

As an exercise, you can figure out how to modify it so it only generates unique solutions. :)