sequential.hpp

Go to the documentation of this file.

/* -*- coding: latin-1 -*- */
/** \file sequential/sequential/sequential.hpp (January 17, 2018)
 * \brief
 * Implementation of the sequential algorithms presented in the report.
 * (Some functions are not use in this part.
 * There are present here to be used by several parallel implementation.)
 *
 * GPLv3 --- Copyright (C) 2017, 2018 Olivier Pirson
 * http://www.opimedia.be/
 */

#ifndef PROGS_SRC_SEQUENTIAL_SEQUENTIAL_SEQUENTIAL_HPP_
#define PROGS_SRC_SEQUENTIAL_SEQUENTIAL_SEQUENTIAL_HPP_

// \cond
#include <set>
#include <vector>
// \endcond

#include "../../common/sigmaodd/helper.hpp"
#include "../../common/sigmaodd/primes.hpp"


namespace sequential {

  using nat_type = sigmaodd::nat_type;
  using prime_type = sigmaodd::prime_type;



  /* ************
   * Prototypes *
   **************/

  /** \brief
   * Check in the order all odd gentle numbers between first_n and last_n,
   * and if print_bad
   *     then print all bad numbers between first_n and last_n (included).
   * The consequence of the result is that:
   * if (all numbers < first_n respect the conjecture)
   *     and (all perfect squares < last_n respect the conjecture)
   *     and (all bad numbers < last_n respect the conjecture)
   * then all numbers < last_n respect the conjecture.
   *
   * sigmaodd::primes.cpp must be compiled without the macro PRIME16.
   *
   * @param first_n 3 <= odd <= last_n
   * @param last_n <= MAX_POSSIBLE_N
   * @param print_bad
   *
   * @return the set of all bad numbers between first_n and last_n (included)
   */
  std::set<nat_type>
  sequential_check_gentle_varsigma_odd(nat_type first_n, nat_type last_n,
                                       bool print_bad = true);


  /** \brief
   * Check in the order all odd gentle numbers between first_n and last_n,
   * and if print_bad
   *     then print all bad numbers between first_n and last_n (included).
   * The consequence of the result is that:
   * if (all numbers < first_n respect the conjecture)
   *     and (all perfect squares < last_n respect the conjecture)
   *     and (all bad numbers < last_n respect the conjecture)
   * then all numbers < last_n respect the conjecture.
   *
   * sigmaodd::primes.cpp must be compiled without the macro PRIME16.
   *
   * @param first_n 3 <= odd <= last_n
   * @param last_n <= MAX_POSSIBLE_N
   * @param bad_table must be contains all bad numbers between bad_first_n and bad_last_n (included)
   * @param bad_first_n
   * @param bad_last_n
   * @param print_bad
   *
   * @return the set of all bad numbers between first_n and last_n (included)
   */
  std::set<nat_type>
  sequential_check_gentle_varsigma_odd(nat_type first_n, nat_type last_n,
                                       const std::set<nat_type> &bad_table,
                                       nat_type bad_first_n, nat_type bad_last_n,
                                       bool print_bad = true);


  /** \brief
   * Check in the order all odd numbers between first_n and last_n.
   * The consequence of the result is that:
   * if all numbers < first_n respect the conjecture
   *   and first_iterate_varsigma_odd_until_lower()
   *       do not exits with impossible to check or cycle found,
   *   then all numbers <= last_n respect the conjecture.
   *
   * If print_bad
   * then print all bad numbers between first_n and last_n (included).
   *
   * If print_all
   * then print all odd numbers between first_n and last_n (included).
   *
   * If print_category
   * then moreover print the category of the number.
   *
   * If print_lower
   * then moreover print the lower number reached.
   *
   * If print_length
   * then moreover print the length of the partial path.
   *
   * If print_path
   * then moreover print the partial path.
   *
   * sigmaodd::primes.cpp must be compiled without the macro PRIME16.
   *
   * @param first_n 3 <= odd <= last_n
   * @param last_n <= MAX_POSSIBLE_N
   * @param print_bad
   * @param print_all
   * @param print_category
   * @param print_length
   * @param print_lower
   * @param print_path
   */
  void
  sequential_check_varsigma_odd(nat_type first_n, nat_type last_n,
                                bool print_bad = true,
                                bool print_all = false,
                                bool print_category = true,
                                bool print_lower = true,
                                bool print_length = true,
                                bool print_path = true);


  /** \brief
   * Return sequential_check_varsigma_odd(),
   * but only for n perfect square.
   *
   * sigmaodd::primes.cpp must be compiled without the macro PRIME16.
   *
   * @param n 3 <= odd <= MAX_POSSIBLE_N
   * @param print
   * @param print_length
   * @param print_lower
   * @param print_path
   */
  void
  sequential_check_varsigma_odd_perfect_square(nat_type n,
                                               bool print = true,
                                               bool print_lower = true,
                                               bool print_length = true,
                                               bool print_path = true);


  /** \brief
   * Check completely (until 1) in the order all odd numbers between first_n and last_n.
   * The consequence of the result is that:
   * all odd numbers *checked* between first_n and last_n (included) respect the conjecture.
   *
   * If check_useless
   * then check also odd numbers that verify is_first_mersenne_prime_unitary_divide(n)
   * else check only others.
   *
   * If print_bad
   * then print all bad numbers between first_n and last_n (included).
   *
   * If print_all
   * then print all odd numbers between first_n and last_n (included).
   *
   * If print_category
   * then moreover print the category of the number.
   *
   * If print_lower
   * then moreover print the lower number reached.
   *
   * If print_length
   * then moreover print the length of the partial path.
   *
   * If print_path
   * then moreover print the partial path.
   *
   * sigmaodd::primes.cpp must be compiled without the macro PRIME16.
   *
   * @param first_n 3 <= odd <= last_n
   * @param last_n <= MAX_POSSIBLE_N
   * @param check_useless
   * @param print_bad
   * @param print_all
   * @param print_category
   * @param print_length
   * @param print_lower
   * @param print_path
   */
  void
  sequential_check_varsigma_odd_complete(nat_type first_n, nat_type last_n,
                                         bool check_useless = false,
                                         bool print_bad = true,
                                         bool print_all = false,
                                         bool print_category = true,
                                         bool print_lower = true,
                                         bool print_length = true,
                                         bool print_path = true);


  /** \brief
   * Return sequential_check_varsigma_odd_complete(),
   * but only for n perfect square.
   *
   * sigmaodd::primes.cpp must be compiled without the macro PRIME16.
   *
   * @param n 3 <= odd <= MAX_POSSIBLE_N
   * @param print
   * @param print_length
   * @param print_lower
   * @param print_path
   */
  void
  sequential_check_varsigma_odd_perfect_square_complete(nat_type n,
                                                        bool print = true,
                                                        bool print_lower = true,
                                                        bool print_length = true,
                                                        bool print_path = true);


  /** \brief
   * Return true iff varsigma_odd(n) < n.
   *
   * sigmaodd::primes.cpp must be compiled without the macro PRIME16.
   *
   * @param n 3 <= odd <= MAX_POSSIBLE_N
   * @param bad_table must be contains all bad numbers between first_n (included) and n (excluded)
   * @param bad_first_n
   */
  bool
  sequential_is_varsigma_odd_lower(nat_type n,
                                   const std::set<nat_type> &bad_table,
                                   nat_type bad_first_n);


  /** \brief
   * Return true iff varsigma_odd(n) < n.
   *
   * sigmaodd::primes.cpp must be compiled without the macro PRIME16.
   *
   * @param n 3 <= odd <= MAX_POSSIBLE_N
   * @param bad_table must be contains all bad numbers between bad_first_n and bad_last_n (included)
   * @param bad_first_n
   * @param bad_last_n
   */
  bool
  sequential_is_varsigma_odd_lower(nat_type n,
                                   const std::set<nat_type> &bad_table,
                                   nat_type bad_first_n, nat_type bad_last_n);


  /** \brief
   * Iterate sequential_varsigma_odd(start_n) until to reach 1.
   * Return this complete path.
   *
   * If one iteration gives a result > MAX_POSSIBLE_N
   * then exits with an error message "! Impossible to check [...]".
   *
   * If one cycle is reached
   * then exits with an error message "! Found not trivial cycle [...]".
   *
   * sigmaodd::primes.cpp must be compiled without the macro PRIME16.
   *
   * @param start_n 3 <= odd <= MAX_POSSIBLE_N
   */
  std::vector<nat_type>
  sequential_iterate_varsigma_odd_until_1(nat_type start_n);


  /** \brief
   * Return sequential_iterate_varsigma_odd_until_1(),
   * but only for n perfect square.
   *
   * sigmaodd::primes.cpp must be compiled without the macro PRIME16.
   *
   * @param start_n 3 <= odd <= MAX_POSSIBLE_N
   */
  std::vector<nat_type>
  sequential_iterate_varsigma_odd_perfect_square_until_1(nat_type start_n);


  /** \brief
   * Iterate sequential_varsigma_odd(start_n) until to be have a result < start_n.
   * Return this partial path.
   *
   * If one iteration gives a result > MAX_POSSIBLE_N
   * then exits with an error message "! Impossible to check [...]".
   *
   * If one cycle is reached
   * then exits with an error message "! Found not trivial cycle [...]".
   *
   * sigmaodd::primes.cpp must be compiled without the macro PRIME16.
   *
   * @param start_n 3 <= odd <= MAX_POSSIBLE_N
   */
  std::vector<nat_type>
  sequential_iterate_varsigma_odd_until_lower(nat_type start_n);


  /** \brief
   * Return sequential_iterate_varsigma_odd_until_lower(),
   * but only for n perfect square.
   *
   * sigmaodd::primes.cpp must be compiled without the macro PRIME16.
   *
   * @param start_n 3 <= odd <= MAX_POSSIBLE_N
   */
  std::vector<nat_type>
  sequential_iterate_varsigma_odd_perfect_square_until_lower(nat_type start_n);


  /** \brief
   * Return the minimum of the first size values of ns.
   *
   * @param ns must be contains at least size elements
   * @param size >= 1
   */
  constexpr
  nat_type
  sequential_min_array(const nat_type ns[], size_t size);


  /** \brief
   * Print number from ns, in increasing order
   * and return a list of these number in the same order.
   */
  std::vector<nat_type>
  sequential_print_in_order(const std::set<nat_type> &ns);


  /** \brief
   * Return varsigma_odd(n),
   * i.e. the sum of all odd divisors of n,
   *      divided by 2 until to be odd.
   *
   * sigmaodd::primes.cpp must be compiled without the macro PRIME16.
   *
   * @param n 3 <= odd <= MAX_POSSIBLE_N
   */
  nat_type
  sequential_varsigma_odd(nat_type n);


  /** \brief
   * Return sequential_varsigma_odd(),
   * but only for n perfect square.
   *
   * sigmaodd::primes.cpp must be compiled without the macro PRIME16.
   *
   * @param n 3 <= (odd and perfect square) <= MAX_POSSIBLE_N
   */
  nat_type
  sequential_varsigma_odd_perfect_square(nat_type n);


  /** \brief
   * Return the set of n from ns
   * such that varsigma_odd(n) > n.
   *
   * sigmaodd::primes.cpp must be compiled without the macro PRIME16.
   *
   * @param ns list of (3 <= odd <= MAX_POSSIBLE_N)
   * @param bad_table must be contains all bad numbers between bad_first_n and bad_last_n (included)
   * @param bad_first_n
   * @param bad_last_n
   */
  std::set<nat_type>
  sequential_varsigma_odd_greater_set(const std::vector<nat_type> &ns,
                                      const std::set<nat_type> &bad_table,
                                      nat_type bad_first_n, nat_type bad_last_n);


  /** \brief
   * Return an upper bound of varsigma_odd(n).
   *
   * If n == 1 then return 1.
   * If n is identified as a gentle number then return n - 1.
   * Else return floor((n * ceil(2 * (n - 1)^{1/8} + 1)) / 2).
   *
   * @param n odd
   * @param bad_table must be contains all bad numbers between bad_first_n (included) and n (excluded)
   * @param bad_first_n
   */
  constexpr
  nat_type
  sequential_sigma_odd_upper_bound(nat_type n,
                                   const std::set<nat_type> &bad_table,
                                   nat_type bad_first_n);


  /** \brief
   * Return an upper bound of sigma_odd(n).
   *
   * If n == 1 then return 1.
   * If n is identified as a gentle number then return n - 1.
   * Else return floor((n * ceil(2 * (n - 1)^{1/8} + 1)) / 2).
   *
   * @param n odd
   * @param bad_table must be contains all bad numbers between bad_first_n and bad_last_n (included)
   * @param bad_first_n
   * @param bad_last_n
   */
  constexpr
  nat_type
  sequential_sigma_odd_upper_bound(nat_type n,
                                   const std::set<nat_type> &bad_table,
                                   nat_type bad_first_n, nat_type bad_last_n);


  /** \brief
   * Return an upper bound of varsigma_odd(n).
   *
   * If n == 1 then return 1.
   * If n is identified as a gentle number then return n - 1.
   * Else return floor((n * ceil(2 * (n - 1)^{1/8} + 1)) / 2).
   *
   * @param n odd
   * @param bad_table must be contains all bad numbers between bad_first_n (included) and n (excluded)
   * @param bad_first_n
   * @param sqrt_n must be equal floor_square_root(n)
   */
  constexpr
  nat_type
  sequential_sigma_odd_upper_bound_with_sqrt(nat_type n,
                                             const std::set<nat_type> &bad_table,
                                             nat_type bad_first_n,
                                             nat_type sqrt_n);


  /** \brief
   * Return an upper bound of sigma_odd(n).
   *
   * If n == 1 then return 1.
   * If n is identified as a gentle number then return n - 1.
   * Else return floor((n * ceil(2 * (n - 1)^{1/8} + 1)) / 2).
   *
   * @param n odd
   * @param bad_table must be contains all bad numbers between bad_first_n and bad_last_n (included)
   * @param bad_first_n
   * @param bad_last_n
   * @param sqrt_n must be equal floor_square_root(n)
   */
  constexpr
  nat_type
  sequential_sigma_odd_upper_bound_with_sqrt(nat_type n,
                                             const std::set<nat_type> &bad_table,
                                             nat_type bad_first_n, nat_type bad_last_n,
                                             nat_type sqrt_n);

}  // namespace sequential

#include "sequential__inline.hpp"

#endif  // PROGS_SRC_SEQUENTIAL_SEQUENTIAL_SEQUENTIAL_HPP_