euler_tools_1.3.0_e7bbfe0b/src/euler_package.ads

--  ---------------------------------------------------------------------------
--
--  Copyright (c) 2023 Francesc Rocher <francesc.rocher@gnail.com>
--  SPDX-License-Identifier: MIT
--
--  ---------------------------------------------------------------------------
--   _____      _             _____           _
--  | ____|   _| | ___ _ __  |_   _|__   ___ | |___   Mathematical functions
--  |  _|| | | | |/ _ \ '__|   | |/ _ \ / _ \| / __|  and tools to solve
--  | |__| |_| | |  __/ |      | | (_) | (_) | \__ \  Project Euler problems
--  |_____\__,_|_|\___|_|      |_|\___/ \___/|_|___/  https://projecteuler.net
--
-- ----------------------------------------------------------------------------

with Ada.Containers.Doubly_Linked_Lists;
with Ada.Containers.Ordered_Sets;
with Ada.Containers.Vectors;

with Euler_Tools_Config;

generic
   type Int_Type is range <>;

package Euler_Package is

   subtype Integer_Type is Int_Type;

   package List_Package is new Ada.Containers.Doubly_Linked_Lists (Int_Type);
   subtype List_Type is List_Package.List;
   use List_Package;

   package Set_Package is new Ada.Containers.Ordered_Sets (Int_Type);
   subtype Set_Type is Set_Package.Set;
   use Set_Package;

   subtype Numeral_Type is Natural range 0 .. 9;

   package Numeral_Package is new Ada.Containers.Vectors
     (Index_Type => Positive, Element_Type => Numeral_Type);

   subtype Crumbled_Natural is Numeral_Package.Vector;
   --  Crumbled_Natural type is a representation or an arbitrary long Natural
   --  type, regardless of the particular type instantiated in the generic
   --  package.

   CN_Empty : constant Crumbled_Natural := Numeral_Package.Empty_Vector;
   CN_Zero  : constant Crumbled_Natural := [0];

   type Decimal_Division_Type is record
      Dividend   : Int_Type;
      Divisor    : Int_Type;
      Quotient   : Int_Type;
      Decimals   : Crumbled_Natural;
      Cycle      : Natural;
      Remainders : List_Type;
   end record;

   type Prime_Cursor_Type is private;
   --  The prime numbers generator requires private data to avoid interfering
   --  with other functions.

   function Library_Name return String is (Euler_Tools_Config.Crate_Name);
   function Library_Version return String is
     (Euler_Tools_Config.Crate_Version);
   --  Basic information.

   function All_Divisors (Number : Int_Type) return Set_Type;
   --  Returns the set of all divisors of Number, including 1 and Number.

   function Are_Amicable (A, B : Int_Type) return Boolean with
     Pre => A > 0 and then B > 0;
   --  Return True is A and B are an amicable pair: A and B are amicable if
   --  Sum (Proper_Divisors (A)) = B  and  Sum (Proper_Divisors (B)) = A.

   procedure CN_Assign (Left : in out Crumbled_Natural; Right : Int_Type);
   --  Assigns the value of Right number to the Crumbled_Naturals of the
   --  Left.

   procedure CN_Assign (Left : in out Int_Type; Right : Crumbled_Natural);
   --  Assigns the value of the Crumbled_Natural in the Right to the Left
   --  number.

   procedure CN_Assign
     (Left                   : in out Int_Type; Right : Crumbled_Natural;
      Digit_Start, Digit_End :        Positive) with
     Pre => Digit_Start <= Digit_End and then Digit_End <= Length (Right);
   --  Assigns the value of the Crumbled_Natural in the Right to the Left
   --  number using digits from Digit_Start to Digit_End.

   function Collatz_Next (Number : Int_Type) return Int_Type with
     Pre => Number > 1;
   --  Returns the next number in the Collatz sequence, defined by:
   --  Collatz_Next = N/2 if N is even, and Collatz_Next = 3*N+1 if N is odd,
   --  where N is the previous number in the Collatz sequence.

   function Combination (N, K : Int_Type) return Int_Type with
     Pre => 0 <= N and then 0 <= K and then K <= N;
   --  Returns the combinatorial number of N over K.

   function Concat (Left, Right : Int_Type) return Int_Type with
     Pre => Right >= 0;
   --  Returns the number obtained by concatenating Left and Right numbers.

   function Decimal_Division
     (Dividend, Divisor : Int_Type; Decimals : Natural)
      return Decimal_Division_Type with
     Pre => Divisor /= 0;
   --  Returns the division of Dividend / Divisor with a maximum
   --  number of Decimals in the Quotient. It mimics the manual operation of
   --  dividing both numbers up to a certain number of decimals.

   procedure Decimal_Division_Increase
     (DDiv : in out Decimal_Division_Type; Decimals : Natural) with
     Pre => Decimals > Length (DDiv.Decimals);
   --  Returns the division of Dividend / Divisor with a maximum
   --  number of Decimals in the Quotient. It mimics the manual operation of
   --  dividing both numbers up to a certain number of decimals.

   function Element_First (Set : Set_Type) return Int_Type with
     Pre => not Set.Is_Empty;
   --  Returns the first element of the ordered, non-empty Set.

   function Element_Nth (Set : Set_Type; Nth : Natural) return Int_Type with
     Pre => not Set.Is_Empty;
   --  Return the Nth element of the ordered, non-empty Set.

   function Equals (List : List_Type) return Boolean with
     Pre => not List.Is_Empty;
   --  Returns True if all element of the list are equal.

   function Factorial (Number : Int_Type) return Int_Type with
     Pre => Number >= 0;
   --  Return the factorial of Number: 1* 2 * 3 * .. * Number.

   function Fibonacci_Start return Int_Type;
   --  Returns the first generated Fibonacci number from the initial terms 1
   --  and 1, which happens to be equal to 2, and resets the sequence
   --  generator.

   function Fibonacci_Start (A, B : Int_Type) return Int_Type;
   --  Resets the Fibonacci sequence generator to start with the numbers A
   --  and B, and return the first generated Fibonacci number (A + B).

   function Fibonacci_Next return Int_Type;
   --  Returns the next Fibonacci number.

   function Greatest_Common_Divisor (A, B : Int_Type) return Int_Type;
   --  Returns the greatest common divisor of A, B, also known as Gcd (A, B).

   function Greatest_Common_Divisor (List : List_Type) return Int_Type with
     Pre => not List.Is_Empty;
   --  Returns the Gcd of all numbers in the list using the formula
   --     Gcd ({Ai}) = Gcd (A1, Gcd (A2, Gcd ( ... ))).

   function Hundreds (Number : Int_Type) return Int_Type;
   --  Returns the hundreds of Number.

   function Is_Abundant (Number : Int_Type) return Boolean;
   --  Returns True if the sum of the proper divisors of Number is greater
   --  than itself: Sum (Proper_Divisors (Number)) > Number

   function Is_Deficient (Number : Int_Type) return Boolean;
   --  Returns True if the sum of the proper divisors of Number is lesser
   --  than itself: Sum (Proper_Divisors (Number)) < Number

   function Is_Divisor (Number, Divisor : Int_Type) return Boolean with
     Pre => Divisor /= 0;
   --  Returns True is Number can by evenly divided by Divisor.

   function Is_Even (Number : Int_Type) return Boolean;
   --  Returns True is Number is even.

   function Is_Odd (Number : Int_Type) return Boolean;
   --  Returns True is Number is odd.

   function Is_Palindrome (Number : Int_Type) return Boolean;
   --  Returns True if Number is the same read from left to right and right
   --  to left.

   function Is_Perfect (Number : Int_Type) return Boolean;
   --  Returns True if the sum of the proper divisors of Number is equal to
   --  itself: Sum (Proper_Divisors (Number)) = Number

   function Is_Prime (Number : Int_Type) return Boolean;
   --  Returns True if Number is prime.

   function Least_Common_Multiple (A, B : Int_Type) return Int_Type;
   --  Returns the least common multiple computed with the formula
   --     Lcm (A, B) = Min (A, B) * (Max (A, B) / Gcd(A, B))

   function Least_Common_Multiple (List : List_Type) return Int_Type with
     Pre => not List.Is_Empty;
   --  Returns the leas common multiple of all numbers in the list using the
   --  formula  Lcm ({Ai}}) = Lcm (A1, Lcm (A2, Lcm ( ... ))).

   function Left (Number : Int_Type; Positions : Positive) return Int_Type;
   --  Returns the number formed by the leftmost digit Positions of Number.

   function Length (Number : Crumbled_Natural) return Natural;
   --  Returns the Length of the Crumbled_Natural Number;

   function Length (Number : Integer_Type) return Natural;
   --  Returns the total number of digits in Number.

   function Length (List : List_Type) return Natural;
   --  Returns the number of elements in the List.

   function Length (Set : Set_Type) return Natural;
   --  Returns the number of elements in Set.

   function Prime_Factors (Number : Int_Type) return List_Type;
   --  Returns the list of prime factors of Number.

   function Prime_First (Cursor : in out Prime_Cursor_Type) return Int_Type;
   --  Returns the first prime number (2) and resets the prime number
   --  generator Cursor.

   function Prime_Next
     (Cursor : in out Prime_Cursor_Type; Nth : Int_Type := 1) return Int_Type;
   --  Returns the next prime number. Optionally, Nth parameter can be
   --  specified to jump N numbers. That is, Prime_Next (C, 10) is equivalent
   --  to call Prime_Next (C) 10 times

   function Prime_Nth (Nth : Int_Type) return Int_Type;
   --  Returns the Nth prime number.

   function Product (List : List_Type) return Int_Type with
     Pre => not List.Is_Empty;
   --  Returns the product of all numbers in List.

   function Proper_Divisors (Number : Int_Type) return Set_Type;
   --  Returns the set of proper divisors of Number (that is, excluding
   --  Number). If Number is equal to 1, then returns the empty set.

   function Right (Number : Int_Type; Positions : Positive) return Int_Type;
   --  Return the number formed by the rightmost digit Positions of Number.

   procedure Sort (List : in out List_Type);
   --  Sorts the List of numbers in place.

   function Square_Root (Number : Int_Type) return Int_Type with
     Pre => Number >= 0;
   --  Return the truncated square root of Number if Number > 0, 0 otherwise.

   function Sub_Number
     (Number : Int_Type; Start, Length : Positive) return Int_Type;
   --  Return the number formed with the digits of Number from Start position
   --  up to the specified Length (mimics the Sub_String function). Returns 0
   --  if Start is greater than the Number length. Returns less that Length
   --  digits if there are no enough digits in Number from the Start.

   function Sum (List : List_Type) return Int_Type with
     Pre => not List.Is_Empty;
   --  Returns the sum of all number of the List.

   function Sum (Set : Set_Type) return Int_Type;
   --  Return the sum of all numbers of the set.

   function Sum_Multiples
     (Number : Int_Type; Upper_Bound : Int_Type) return Int_Type with
     Pre => Number > 0 and then Number <= Upper_Bound;
   --  Returns the sum of all numbers multiples of Number less or equal than
   --  Upper_Bound. e.g. Sum_Multiples (3, 100) = 3 + 6 + 9 + .. + 99.

   function Sum_Sequence (Number : Int_Type) return Int_Type;
   --  Returns the sum of all numbers from 1 to Number.

   function Sum_Squares (Number : Int_Type) return Int_Type;
   --  Returns the sum of the squares of all numbers from 1 to Number.

   function Tens (Number : Int_Type) return Int_Type;
   --  Returns the tens of Number.

   function Thousands (Number : Int_Type) return Int_Type;
   --  Returns the thousands of Number.

   function To_Number (Chr : Character) return Int_Type with
     Pre => (Chr in '0' .. '9');
   --  Returns the value of Chr converted to typ T if Chr in '0' .. '9', 0
   --  otherwise.

   function To_Number (Str : String) return Int_Type with
     Pre => (for all S of Str => S in '0' .. '9');
   --  Returns the value of Str converted to Integer_Type.

   function To_String (Number : Int_Type) return String;
   --  Returns a String with the value of Number. Removes leading whitespace.

   function Units (Number : Int_Type) return Int_Type;
   --  Returns the last digit (units) of Number.

private

   type Δ_Prime_Type is mod 4;
   type Prime_Cursor_Type is record
      Number   : Int_Type     := 2;
      Δ_Number : Δ_Prime_Type := 2;
   end record;

end Euler_Package;