How to resolve the algorithm Sum multiples of 3 and 5 step by step in the Prolog programming language

Published on 12 May 2024 09:40 PM
#Prolog

How to resolve the algorithm Sum multiples of 3 and 5 step by step in the Prolog programming language

Table of Contents

Problem Statement

The objective is to write a function that finds the sum of all positive multiples of 3 or 5 below n. Show output for n = 1000. This is is the same as Project Euler problem 1. Extra credit: do this efficiently for n = 1e20 or higher.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sum multiples of 3 and 5 step by step in the Prolog programming language

Source code in the prolog programming language

sum_of_multiples_of_3_and_5_slow(N, TT) :-
	sum_of_multiples_of_3_and_5(N, 1, 0, TT).

sum_of_multiples_of_3_and_5(N, K, S, S) :-
	3 * K >= N.

sum_of_multiples_of_3_and_5(N, K, C, S) :-
	T3 is 3 * K, T3 < N,
	C3 is C + T3,
	T5 is 5 * K,
	(   (T5 < N, K mod 3 =\= 0)
	->  C5 is C3 + T5
	;   C5 = C3),
	K1 is K+1,
	sum_of_multiples_of_3_and_5(N, K1, C5, S).

sum_of_multiples_of_3_and_5_fast(N, TT):-
	maplist(compute_sum(N), [3,5,15], [TT3, TT5, TT15]),
	TT is TT3 + TT5 - TT15.

compute_sum(N, N1, Sum) :-
	(   N mod N1 =:= 0
	->  N2 is N div N1 - 1
	;   N2 is N div N1),
	Sum is N1 * N2 * (N2 + 1) / 2.

You may also check:How to resolve the algorithm 100 prisoners step by step in the Maple programming language
You may also check:How to resolve the algorithm Catmull–Clark subdivision surface step by step in the C programming language
You may also check:How to resolve the algorithm Sieve of Eratosthenes step by step in the Crystal programming language
You may also check:How to resolve the algorithm Department numbers step by step in the Clojure programming language
You may also check:How to resolve the algorithm Least common multiple step by step in the PARI/GP programming language