Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Collatz conjecture
Summary
The Collatz conjecture is one of the most famous unsolved problems in mathematics. The conjecture asks whether repeating two simple arithmetic operations will eventually transform every positive integer into 1. It concerns sequences of integers in which each term is obtained from the previous term as follows: if the previous term is even, the next term is one half of the previous term. If the previous term is odd, the next term is 3 times the previous term plus 1. The conjecture is that these sequences always reach 1, no matter which positive integer is chosen to start the sequence.
It is named after the mathematician Lothar Collatz, who introduced the idea in 1937, two years after receiving his doctorate. It is also known as the 3n + 1 problem (or conjecture), the 3x + 1 problem (or conjecture), the Ulam conjecture (after Stanisław Ulam), Kakutani's problem (after Shizuo Kakutani), the Thwaites conjecture (after Sir Bryan Thwaites), Hasse's algorithm (after Helmut Hasse), or the Syracuse problem.
The sequence of numbers involved is sometimes referred to as the hailstone sequence, hailstone numbers or hailstone numerals (because the values are usually subject to multiple descents and ascents like hailstones in a cloud), or as wondrous numbers.
Paul Erdős said about the Collatz conjecture: "Mathematics may not be ready for such problems." Jeffrey Lagarias stated in 2010 that the Collatz conjecture "is an extraordinarily difficult problem, completely out of reach of present day mathematics".
Consider the following operation on an arbitrary positive integer:
If the number is even, divide it by two.
If the number is odd, triple it and add one.
In modular arithmetic notation, define the function f as follows:
Now form a sequence by performing this operation repeatedly, beginning with any positive integer, and taking the result at each step as the input at the next.
In notation:
(that is: ai is the value of f applied to n recursively i times; ai = f^i(n)).
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related courses (3)
CS-308: Introduction to quantum computation
The course introduces the paradigm of quantum computation in an axiomatic way. We introduce the notion of quantum bit, gates, circuits and we treat the most important quantum algorithms. We also touch
CS-101: Advanced information, computation, communication I
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
COM-300: Stochastic models in communication
L'objectif de ce cours est la maitrise des outils des processus stochastiques utiles pour un ingénieur travaillant dans les domaines des systèmes de communication, de la science des données et de l'i
Related lectures (32)
Quantum Measurement Analysis
Explores quantum measurement analysis, including the Simon problem and geometric analogies.
Proofs: Logic, Mathematics & Algorithms
Explores proof concepts, techniques, and applications in logic, mathematics, and algorithms.
Simon Problem: Quantum Algorithm and Hilbert Space
Covers Simon's quantum algorithm, unitary operations, and the Simon problem.
Related publications (4)
Sparse Dictionaries for Continuous-Domain Inverse Problems
Michaël Unser, Shayan Aziznejad, Thomas Jean Debarre
We study 1D continuous-domain inverse problems for multicomponent signals. The prior assumption on these signals is that each component is sparse in a different dictionary specified by a regularization operators. We introduce a hybrid regularization functi ...
2019Secure numerical and logical multi party operations
We derive algorithms for efficient secure numerical and logical operations in the semi-honest model ensuring statistical or perfect security for secure multi-party computation (MPC). To derive our algorithms for trigonometric functions, we use basic mathem ...
Elsevier Science Bv2017Bounds for Pach's Selection Theorem and for the Minimum Solid Angle in a Simplex
We estimate the selection constant in the following geometric selection theorem by Pach: For every positive integer d, there is a constant such that whenever are n-element subsets of , we can find a point and subsets for every , each of size at least , suc ...
Springer2015