lib_3np1_mod.hpp

Go to the documentation of this file.

/* -*- coding: latin-1 -*- */

/** \mainpage
 * Module lib_3np1_mod (February 29, 2016)
 *
 * The C++ program *prog_3np1_mod* check
 * the dynamic of
 * **3n+1 function in a modulo arithmetic**.
 *
 * Results:
 * \verbinclude exceptions_8.txt
 * \verbinclude exceptions_16.txt
 * \verbinclude exceptions_24.txt
 * \verbinclude exceptions_32.txt
 *
 * See
\htmlonly
<ul>
<li>
  Complete <strong>C++ sources</strong> on
  <strong><a href="https://bitbucket.org/OPiMedia/severalgos/src/master/3np1_mod_problem/">Bitbucket</a></strong>
</li>
<li>
  This
  <strong><a href="http://www.opimedia.be/DS/online-documentations/severalgos/3np1-mod-problem-cpp/html/">C++ HTML online documentation</a></strong>
</li>
</ul>
\endhtmlonly
 *
 * Piece of severalgos.
 * https://bitbucket.org/OPiMedia/severalgos
 *
 * GPLv3 --- Copyright (C) 2015, 2016 Olivier Pirson
 * http://www.opimedia.be/
 */

/** \file lib_3np1_mod.hpp
 * \brief Function definitions.
 */

#include <cstdint>

#include <set>
#include <vector>



#ifndef LIB_3NP1_MOD__LIB_3NP1_MOD__H_
#define LIB_3NP1_MOD__LIB_3NP1_MOD__H_

namespace lib_3np1_mod {

  /* *******
   * Types *
   *********/
  typedef uint64_t value_type;

  typedef value_type (*operation_type)(value_type);

  typedef value_type (*operation_mask_type)(value_type, value_type);



  /* *********************
   * Function prototypes *
   ***********************/
  /** \brief
   * Collatz C function.
   *
   * \f$C(n) = \frac{n}{2}\f$ if n even\n
   * \f$C(n) = 3n + 1\f$ if n odd
   *
   * http://oeis.org/A006370
   *
   * \param n <= (numeric_limits<value_type>::max() - 1)/3
   */
  inline
  value_type
  C(value_type n);


  /** \brief
   * Return
   * \f$C(n) = \frac{n}{2}\f$ if n even,\n
   * \f$C(n) = (3n + 1) \& mask\f$ if n odd
   *
   * \param n <= mask
   * \param mask
   */
  inline
  value_type
  C_mask(value_type n, value_type mask);


  /** \brief
   * \f$m_2\f$ function.
   *
   * Exponent of highest power of 2 dividing n
   * = number of beginning 0 bits of n
   * = 2-adic valuation of n.
   *
   * http://oeis.org/A007814
   *
   * \param n != 0
   */
  inline
  value_type
  m2(value_type n);


  /** \brief
   * F odd function.
   *
   * \f$F(0) = 0\f$\n
   * \f$F(n) = \frac{n}{2^k}\f$ if n even\n
   * \f$F(n) = \frac{3n + 1}{2^k}\f$ if n odd\n
   * which k as large as possible = \f$m_2(...)\f$.
   *
   * http://oeis.org/A139391
   *
   * \param n <= (numeric_limits<value_type>::max() - 1)/3
   */
  inline
  value_type
  F(value_type n);


  /** \brief
   * Return\n
   * \f$F(0) = 0\f$\n
   * \f$F(n) = \frac{n}{2^k}\f$ if n even\n
   * \f$F(n) = \frac{(3n + 1) \& mask}{2^k}\f$ if n odd\n
   * which k as large as possible = \f$m_2(...)\f$.
   *
   * \param n <= mask
   * \param mask
   */
  inline
  value_type
  F_mask(value_type n, value_type mask);


  /** \brief
   * Calculate and return
   * all null and odd exceptions
   * for the 3n + 1 problem
   * with modulo (mask + 1).
   *
   * \param mask
   */
  std::set<value_type>
  search_mask_exceptions(value_type mask);


  /** \brief
   * Calculate and return
   * all null and odd exceptions
   * for the 3n + 1 problem
   * with modulo \f$2^32\f$.
   */
  std::set<value_type>
  search_mask_exceptions_32();


  /** \brief
   * Calculate and return
   * all null and odd exceptions
   * for the 3n + 1 problem
   * with modulo \f$2^32\f$.
   */
  std::set<value_type>
  search_mask_exceptions_64();


  /** \brief
   * Given operation,
   * return the start of path
   * from n to the first value < n or to the first repeated value.
   *
   * \param n <= mask
   * \param operation_mask must be C_mask, F_mask or T_mask
   * \param mask
   */
  std::vector<value_type>
  start_path_mask(value_type n,
                  operation_mask_type operation_mask, value_type mask);


  /** \brief
   * Terras T function.
   *
   * \f$T(n) = \frac{n}{2}\f$ if n even\n
   * \f$T(n) = \frac{3n + 1}{2}\f$ if n odd
   *
   * http://oeis.org/A014682
   *
   * \param n <= (numeric_limits<value_type>::max() - 1)/3
   */
  inline
  value_type
  T(value_type n);


  /** \brief
   * Return\n
   * \f$T(n) = \frac{n}{2}\f$ if n even\n
   * \f$T(n) = \frac{(3n + 1) \& mask}{2}\f$ if n odd
   *
   * \param n <= mask
   * \param mask
   */
  inline
  value_type
  T_mask(value_type n, value_type mask);

}  // namespace lib_3np1_mod


#include "lib_3np1_mod__inline.hpp"

#endif  // LIB_3NP1_MOD__LIB_3NP1_MOD_H_