On solving project Euler #303 in with Prolog / clpfd

Question

Here comes Project Euler Problem 303, "Multiples with small digits".

For a positive integer n, define f(n) as the least positive multiple of n that, written in base 10, uses only digits ≤ 2.

Thus f(2)=2, f(3)=12, f(7)=21, f(42)=210, f(89)=1121222.

Also, .

Find .

This is the code I have already written / that I want to improve:

:- use_module(library(clpfd)).

n_fn(N,FN) :- 
   F  #> 0,
   FN #= F*N,
   length(Ds, _),
   digits_number(Ds, FN),
   Ds ins 0..2,
   labeling([min(FN)], Ds).

That code already works for solving a small number of small problem instances:

?- n_fn(2,X).
X = 2

?- n_fn(3,X).
X = 12 

?- n_fn(7,X).
X = 21 

?- n_fn(42,X).
X = 210 

?- n_fn(89,X).
X = 1121222

What can I do to tackle above challenge "find: sum(n=1 to 10000)(f(n)/n)"?

How can I solve more and bigger instances in reasonable time?

Please share your ideas with me! Thank you in advance!

score 2 · Answer 1 · answered Dec 06 '15 at 22:39

2

It is slow on 9's and there is a pattern.. so..

n_fn(9,12222):-!.
n_fn(99,1122222222):-!.
n_fn(999,111222222222222):-!.
n_fn(9999,11112222222222222222):-!.

But i'm sure it would be nicer to have the prolog find this patten and adapt the search.. not sure how you would do that though!

In general it must be recalculating a lot of results..

answered Dec 06 '15 at 22:39

user27815

4,767
14
28

Ok. But why is it slow in these cases... because f(n) has a lot of digits? – repeat Dec 07 '15 at 07:57
Btw. Preserve steadfastness when using [tag:prolog-cut]! As a general rule of thumb, do "input unifications" and tests *before* the cut and "output unifications" only afterwards. – repeat Dec 07 '15 at 08:03
1

do you mean.. n_fn(9,X):- !,X=12222. etc is better? – user27815 Dec 07 '15 at 13:38
Exactly! `n_fn(9,1231)` should fail ASAP. With `n_fn(9,12222):-!.` that doesn't happen. In this case, only some CPU cycles are wasted. In general (with red cuts), program correctness is at stake! – repeat Dec 07 '15 at 13:56

CapelliC · Answer 2 · 2015-12-07T19:56:29.143

I cannot spot a recurrence relation for this problem. So, initially I was thinking that memoizing could speed it up. Not really...

This code, clp(fd) based, is marginally faster than your...

n_fn_d(N,FN) :- 
        F  #> 0,
        FN #= F*N,
        digits_number_d([D|Ds], Ts),
        D in 1..2,
        Ds ins 0..2,
        scalar_product(Ts, [D|Ds], #=, FN),
        labeling([min(FN)], [D|Ds]).

digits_number_d([_], [1]).
digits_number_d([_|Ds], [T,H|Ts]) :-
        digits_number_d(Ds, [H|Ts]), T #= H*10.

When I used clp(fd) to solve problems from Euler, I stumbled in poor performance... sometime the simpler 'generate and test' paired with native arithmetic make a difference.

This simpler one, 'native' based:

n_fn_e(N,FN) :- 
    digits_e(FN),
    0 =:= FN mod N.

digits_e(N) :-
    length([X|Xs], _),
    maplist(code_e, [X|Xs]), X \= 0'0,
    number_codes(N, [X|Xs]).
code_e(0'0).
code_e(0'1).
code_e(0'2).

it's way faster:

test(N) :-
    time(n_fn(N,A)),
    time(n_fn_d(N,B)),
    time(n_fn_e(N,C)),
    writeln([A,B,C]).

?- test(999).
% 473,671,146 inferences, 175.006 CPU in 182.242 seconds (96% CPU, 2706593 Lips)
% 473,405,175 inferences, 173.842 CPU in 178.071 seconds (98% CPU, 2723188 Lips)
% 58,724,230 inferences, 25.749 CPU in 26.039 seconds (99% CPU, 2280636 Lips)
[111222222222222,111222222222222,111222222222222]
true

On solving project Euler #303 in with Prolog / clpfd

2 Answers2