helper.hpp

Go to the documentation of this file.

/* -*- coding: latin-1 -*- */
/** \file common/sigmaodd/helper.hpp (January 6, 2018)
 * \brief
 * Define type and some generic functions.
 *
 * GPLv3 --- Copyright (C) 2017, 2018 Olivier Pirson
 * http://www.opimedia.be/
 */

#ifndef PROGS_SRC_COMMON_SIGMAODD_HELPER_HPP_
#define PROGS_SRC_COMMON_SIGMAODD_HELPER_HPP_

// \cond
#include <cstdint>

#include <string>
#include <vector>
// \endcond


/** \brief
 * A lot of functions and stuffs to deal the sigma_odd problem and related stuffs.
 */
namespace sigmaodd {

  /* *******
   * Types *
   *********/

  /** \brief
   * Type for natural number used in all code, on 64 bits.
   */
  typedef uint64_t nat_type;


  /** \brief
   * Type double size for some temporary calculation.
   */

#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wpedantic"
  typedef unsigned __int128 tmp_uint128_type;
#pragma GCC diagnostic pop



  /* **********
   * Constant *
   ************/
  /** \brief
   * Lower bound of the bigger number
   * such that it is possible to compute the result of the sigma function.
   */
  constexpr nat_type MAX_POSSIBLE_N = (static_cast<nat_type>(1) << 56) - 1;



  /* ************
   * Prototypes *
   **************/
  /** \brief
   * Return the eighth root of n rounded to above.
   */
  inline
  nat_type
  ceil_eighth_root(nat_type n);


  /** \brief
   * Return the fourth root of n rounded to above.
   */
  nat_type
  ceilx_fourth_root(nat_type n);


  /** \brief
   * Return the square root of n rounded to above.
   */
  inline
  nat_type
  ceil_square_root(nat_type n);


  /** \brief
   * Return the eighth root of n rounded to below.
   */
  nat_type
  floor_eighth_root(nat_type n);


  /** \brief
   * Return the fourth root of n rounded to below.
   */
  nat_type
  floor_fourth_root(nat_type n);


  /** \brief
   * Return the square root of n rounded to below.
   */
  nat_type
  floor_square_root(nat_type n);


  /** \brief
   * Return true iff n is even.
   */
  constexpr
  bool
  is_even(nat_type n);


  /** \brief
   * Return true iff n is odd.
   */
  constexpr
  bool
  is_odd(nat_type n);


  /** \brief
   * Read a file that contains list of bad numbers,
   * add after bad_table,
   * and return the result.
   */
  std::vector<nat_type>
  load_bad_table(const std::string &filename,
                 const std::vector<nat_type> &bad_table = std::vector<nat_type>());


  /** \brief
   * Read the file
   * and extract each natural number begining a line.
   * Return the list of these numbers.
   */
  std::vector<nat_type>
  load_numbers(const std::string &filename);


  /** \brief
   * Return x^k, x power k.
   */
  constexpr
  nat_type
  pow_nat(nat_type n, unsigned int k);


  /** \brief
   * Return x*x.
   */
  constexpr
  double
  square(double x);


  /** \brief
   * Return n*n.
   */
  constexpr
  nat_type
  square(nat_type n);


  /** \brief
   * Return 2 + 4 + 6 + 8 + ... + (n or n-1) = k(k + 1) with k = floor(n/2).
   *
   * https://oeis.org/A110660
   *
   * @return 2 + 4 + 6 + 8 + ... + (n or n-1)
   */
  constexpr
  nat_type
  sum_even(nat_type n);


  /** \brief
   * Return the sum of the (k + 1) terms
   * of the geometric progression of the common ratio r.
   *
   * If r is prime
   * then the result is equal to the sum of the divisors of r.
   *
   * In fact calculates (r^k - 1) / (r - 1) + r^k to avoid some overflow.
   *
   * @return 1 + r + r^2 + r^3 + ... + r^k = (r^(k + 1) - 1) / (r - 1)
   */
  constexpr
  nat_type
  sum_geometric_progression(nat_type r, unsigned int k);


  /** \brief
   * Return sum_geometric_progression(r, k)
   * but only for r > 1.
   *
   * In fact calculates (r^k - 1) / (r - 1) + r^k to avoid some overflow.
   *
   * @param r > 1
   * @param k
   *
   * @return 1 + r + r^2 + r^3 + ... + r^k = (r^(k + 1) - 1) / (r - 1)
   */
  constexpr
  nat_type
  sum_geometric_progression_strict(nat_type r, unsigned int k);


  /** \brief
   * Return 1 + 2 + 3 + 4 + ... + n = n(n + 1)/2.
   *
   * https://oeis.org/A000217
   *
   * @return 1 + 2 + 3 + 4 + ... + n
   */
  constexpr
  nat_type
  sum_natural(nat_type n);


  /** \brief
   * Return 1 + 3 + 5 + 7 + ... + (n or n-1) = k^2 with k floor((n+1)/2).
   *
   * sum_odd(n - 1) = https://oeis.org/A008794
   *
   * @return 1 + 3 + 5 + 7 + ... + (n or n-1)
   */
  constexpr
  nat_type
  sum_odd(nat_type n);

}  // namespace sigmaodd

#include "helper__inline.hpp"

#endif  // PROGS_SRC_COMMON_SIGMAODD_HELPER_HPP_