How to resolve the algorithm Amicable pairs step by step in the Picat programming language

Published on 12 May 2024 09:40 PM
#Picat

How to resolve the algorithm Amicable pairs step by step in the Picat programming language

Table of Contents

Problem Statement

Two integers

N

{\displaystyle N}

and

M

{\displaystyle M}

are said to be amicable pairs if

N ≠ M

{\displaystyle N\neq M}

and the sum of the proper divisors of

N

{\displaystyle N}

(

s u m

(

p r o p D i v s

( N ) )

{\displaystyle \mathrm {sum} (\mathrm {propDivs} (N))}

)

= M

{\displaystyle =M}

as well as

s u m

(

p r o p D i v s

( M ) )

N

{\displaystyle \mathrm {sum} (\mathrm {propDivs} (M))=N}

.

1184 and 1210 are an amicable pair, with proper divisors:

Calculate and show here the Amicable pairs below 20,000; (there are eight).

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Amicable pairs step by step in the Picat programming language

Source code in the picat programming language

go =>
  N = 20000,

  println(amicable1),
  time(amicable1(N)),

  % initialize_table is needed to clear the table cache
  % of sum_divisors/1 between each run.
  initialize_table,
  println(amicable2),
  time(amicable2(N)),

  initialize_table,
  println(amicable3),
  time(amicable3(N)),

  initialize_table,
  println(amicable4),
  time(amicable4(N)),
  
  nl.


% Foreach loop and a map (hash table)
amicable1(N) => 
  Pairs = new_map(),
  foreach(A in 1..N) 
     B = sum_divisors(A),
     C = sum_divisors(B),
     if A != B, A == C then
        Pairs.put([A,B].sort(),1)
     end
  end,
  println(Pairs.keys().sort()).


% List comprehension
amicable2(N) => 
  println([[A,B].sort() : A in 1..N, 
           B = sum_divisors(A), 
           C = sum_divisors(B),
           A != B, A == C].remove_dups()).


% While loop
amicable3(N) => 
  A = 1,
  while(A <= N)
     B = sum_divisors(A),
     if A < B, A == sum_divisors(B) then
       print([A,B]), print(" ")
     end,
     A := A + 1
  end,
  nl.

% Foreach loop, everything in the condition
amicable4(N) => 
  foreach(A in 1..N, B = sum_divisors(A), A < B, A == sum_divisors(B))
     print([A,B]), print(" ")
  end,
  nl.

%
% Sum of divisors of N
%
table
sum_divisors(N) = Sum =>
  sum_divisors(2,N,1,Sum).

% Base case: exceeding the limit
sum_divisors(I,N,Sum0,Sum), I > floor(sqrt(N)) =>
   Sum = Sum0.

% I is a divisor of N
sum_divisors(I,N,Sum0,Sum), N mod I == 0 =>
  Sum1 = Sum0 + I,
  (I != N div I -> 
    Sum2 = Sum1 + N div I 
    ; 
    Sum2 = Sum1
  ),
  sum_divisors(I+1,N,Sum2,Sum).

% I is not a divisor of N.
sum_divisors(I,N,Sum0,Sum) =>
  sum_divisors(I+1,N,Sum0,Sum).

You may also check:How to resolve the algorithm Read entire file step by step in the UNIX Shell programming language
You may also check:How to resolve the algorithm FizzBuzz step by step in the RapidQ programming language
You may also check:How to resolve the algorithm Queue/Usage step by step in the Lambdatalk programming language
You may also check:How to resolve the algorithm Go Fish step by step in the Perl programming language
You may also check:How to resolve the algorithm Pell numbers step by step in the Julia programming language