sigmaodd.hpp

Go to the documentation of this file.

/* -*- coding: latin-1 -*- */
/** \file common/sigmaodd/sigmaodd.hpp (January 18, 2018)
 * \brief
 * Main functions to deal the sigma_odd problem.
 *
 * GPLv3 --- Copyright (C) 2017, 2018 Olivier Pirson
 * http://www.opimedia.be/
 */

#ifndef PROGS_SRC_COMMON_SIGMAODD_SIGMAODD_HPP_
#define PROGS_SRC_COMMON_SIGMAODD_SIGMAODD_HPP_

// \cond
#include <map>
#include <ostream>
#include <set>
#include <string>
#include <utility>
#include <vector>
// \endcond

#include "divisors.hpp"


namespace sigmaodd {

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

  /** \brief
   * Iterate from first to last (included)
   * and for each odd n such that is_little_mersenne_prime_unitary_divide(n) is false,
   * iterate var_sum() until the result is <= n.
   *
   * If need more that one iteration
   * then print n and the number of iterations.
   *
   * @param first_n odd >= 3
   * @param last_n
   */
  void
  check_varsigma_odd(nat_type first_n, nat_type last_n);


  /**
   * Return a string representation of the path.
   * All numbers are separated by the corresponding <, = or > symbol.
   */
  std::string
  path_to_string(const std::vector<nat_type> &path);


  /** \brief
   * Iterate from first to last (included)
   * and for each odd n *not* square such that is_little_mersenne_prime_unitary_divide(n) is false,
   * if varsum_odd(n) > n then print n and varsum_odd(n).
   *
   * If varsum_odd(n) is not divisible by 3, 5, 7 or 9
   * then after n print '!' follow by this number.
   *
   * If varsum_odd(n) is a perfect square
   * then after varsum_odd(n) print '#'.
   *
   * @param first odd >= 3
   * @param last
   * @param print_path
   */
  void
  print_long(nat_type first, nat_type last, bool print_path);


  /** \brief
   * Send to the stream a string representation of the path.
   * All numbers are separated by the corresponding <, = or > symbol.
   *
   * @param path must be a correct complete path from a number n to the number 1
   * @param out
   */
  void
  print_path(const std::vector<nat_type> &path, std::ostream &out = std::cout);


  /** \brief
   * Send to the stream a string representation of the path,
   * from path_begin to path_end (included).
   * All numbers are separated by the corresponding <, = or > symbol.
   *
   * @param path_begin with path_end must be a correct piece of a correct path
   * @param path_end
   * @param out
   */
  void
  print_path(const std::vector<nat_type>::const_iterator &path_begin,
             const std::vector<nat_type>::const_iterator &path_end,
             std::ostream &out = std::cout);

  /** \brief
   * Send (if the below condition is true) to the stream a string representation of the path
   * with some information depending of the boolean parameters.
   *
   * Print only if print_all
   *         or if print_bad
   *               and the path start from a bad number (i.e. odd
   *                                                          and *not* perfect square
   *                                                          and partial length > 1).
   *
   * List of information (maybe) printed, separated by tabulations:
   * * n
   * * Category of n ('E': even, 'F': fixed point, 'S': odd perfect square,
   *                  'B': bad number  or 'G': gentle number)
   * * First number < n
   * * Length of the partial path
   * * Partial path (beginning of the path, until the first number < n, included)
   * * Length of the path
   * * Path
   *
   * If n is a bad number but is *not* divisible by 9
   * then print " *" after n.
   *
   * If length > n
   * then print a " *" after the partial length.
   *
   * If the partial path is the complete path
   * then do not repeat the length and the path.
   *
   * @param path must be a correct complete path from a number n to the number 1 or a correct partial path from a number to the first number < n
   * @param print_bad
   * @param print_all
   * @param print_category
   * @param print_lower
   * @param print_length
   * @param print_path
   * @param out
   */
  void
  print_path_infos(const std::vector<nat_type> &path,
                   bool print_bad = true,
                   bool print_all = false,
                   bool print_category = true,
                   bool print_lower = true,
                   bool print_length = true,
                   bool print_path = true,
                   std::ostream &out = std::cout);


  /** \brief
   * Iterate from first to last (included)
   * and print result of the sum_odd_divisors_divided_until_odd_iterate_until_lower__factorize(n)
   * with some informations.
   *
   * If print_only_longer
   * then for each n print only the longer found.
   *
   * If print_path
   * then for each n print also the complete path
   * (recalculate by iteration of sum_odd_divisors_divided_until_odd__factorize(n)).
   *
   * @param first odd >= 3
   * @param last
   * @param print_only_longer
   * @param print_path
   */
  void
  print_sigmaodd__factorize(nat_type first, nat_type last,
                            bool print_only_longer, bool print_path);


  /** \brief
   * Iterate from first to last (included)
   * and print result of the sum_odd_divisors_divided_until_odd_iterate_until_lower__factorize_bound(n)
   * with some informations.
   *
   * If print_only_longer
   * then for each n print only the longer found.
   *
   * If print_path
   * then for each n print also the complete path
   * (recalculate by iteration of sum_odd_divisors_divided_until_odd__factorize(n)).
   *
   * @param first odd >= 3
   * @param last
   * @param print_only_longer
   * @param print_path
   */
  void
  print_sigmaodd__factorize_bound(nat_type first, nat_type last,
                                  bool print_only_longer, bool print_path);


  /** \brief
   * Iterate from first to last (included)
   * and print result of the sum_odd_divisors_divided_until_odd_iterate_until_lower__naive(n)
   * with some informations.
   *
   * If print_only_longer
   * then for each n print only the longer found.
   *
   * If print_path
   * then for each n print also the complete path
   * (recalculate by iteration of sum_odd_divisors_divided_until_odd__factorize(n)).
   *
   * @param first odd >= 3
   * @param last
   * @param print_only_longer
   * @param print_path
   */
  void
  print_sigmaodd__naive(nat_type first, nat_type last,
                        bool print_only_longer, bool print_path);


  void
  print_square(nat_type first, nat_type last, bool print_path);


  /** \brief
   * Calculates the sum of all odd divisors of n by the Euler formula method,
   * divides the results by 2 until becomes odd,
   * and returns it.
   *
   * @param n != 0
   *
   * @return the sum of all odd divisors of n
   */
  nat_type
  sum_odd_divisors_divided_until_odd__euler(nat_type n);


  /** \brief
   * Calculates the sum of all odd divisors of n by the factorization method,
   * divides the results by 2 until becomes odd,
   * and returns it.
   *
   * If skip_primes_table
   * then n must not be divisible by prime number in the primes precalculated table.
   *
   * @param n != 0
   * @param skip_primes_table
   *
   * @return the sum of all odd divisors of n
   */
  nat_type
  sum_odd_divisors_divided_until_odd__factorize(nat_type n, bool skip_primes_table = false);


  /** \brief
   * Calculates the sum of all odd divisors of n by the factorization method,
   * divides the results by 2 until becomes odd,
   * and returns it.
   * ??? with bound
   *
   * @param n != 0
   * @param start_n
   *
   * @return the sum of all odd divisors of n
   */
  nat_type
  sum_odd_divisors_divided_until_odd__factorize_bound(nat_type n, nat_type start_n);


  /** \brief
   * Calculates the sum of all odd divisors of n by the naive method,
   * divides the results by 2 until becomes odd,
   * and returns it.
   *
   * @param n != 0
   *
   * @return the sum of all odd divisors of n
   */
  nat_type
  sum_odd_divisors_divided_until_odd__naive(nat_type n);


  /** \brief
   * Iterates the sum_odd_divisors_divided_until_odd__euler() function
   * from n until have a result lower than n.
   *
   * @param n > 1
   */
  std::pair<nat_type, unsigned int>
  sum_odd_divisors_divided_until_odd_iterate_until_lower__euler(nat_type n);


  /** \brief
   * Iterates the sum_odd_divisors_divided_until_odd__factorize() function
   * from n until have a result lower than n.
   *
   * @param n > 1
   */
  std::pair<nat_type, unsigned int>
  sum_odd_divisors_divided_until_odd_iterate_until_lower__factorize(nat_type n);


  /** \brief
   * Iterates the sum_odd_divisors_divided_until_odd__factorize() function
   * from n until have a result lower than n.
   * ??? with bound
   *
   * @param n > 1
   */
  std::pair<nat_type, unsigned int>
  sum_odd_divisors_divided_until_odd_iterate_until_lower__factorize_bound(nat_type n);


  /** \brief
   * Iterates the sum_odd_divisors_divided_until_odd__naive() function
   * from n until have a result lower than n.
   *
   * @param n > 1
   */
  std::pair<nat_type, unsigned int>
  sum_odd_divisors_divided_until_odd_iterate_until_lower__naive(nat_type n);


  /** \brief
   * Calculates the sum of all odd divisors of n by the factorization method,
   * divides the results by 2 until becomes odd,
   * and returns it. ???
   *
   * @param n odd
   *
   * @return the sum of all odd divisors of n
   */
  nat_type
  varsum_odd(nat_type n);


  /** \brief
   * Calculates the sum of all odd divisors of n by the factorization method,
   * divides the results by 2 until becomes odd,
   * and returns it. ???
   *
   * @param n odd >= potential_prime_offsets_table_modulo()
   * @param sqrt_n ???
   *
   * @return the sum of all odd divisors of n
   */
  nat_type
  varsum_odd_big(nat_type n, nat_type sqrt_n);

}  // namespace sigmaodd

#endif  // PROGS_SRC_COMMON_SIGMAODD_SIGMAODD_HPP_