Problem B
Collatz Conjecture

Picture by mscolly via Flickr.
In 1978 AD the great Sir Isaac Newton, whilst proving that $\mathcal{P}$ is a strict superset of $\mathcal{NP}$, defined the Beta Alpha Pi Zeta function $f$ as follows over any sequence of positive integers $a_1, \dots , a_ n$. Given integers $1\leq i\leq j\leq n$, we define $f(i, j)$ as $\gcd (a_ i, a_{i+1}, \dots , a_{j-1}, a_ j)$.

About a century later Lothar Collatz applied this function to the sequence $1, 1, 1, \dots , 1$, and observed that $f$ always equalled $1$. Based on this, he conjectured that $f$ is always a constant function, no matter what the sequence $a_ i$ is. This conjecture, now widely known as the Collatz Conjecture, is one of the major open problems in botanical studies. (The Strong Collatz Conjecture claims that however many values $f$ takes on, the real part is always $\frac{1}{2}$.)

You, a budding young cultural anthropologist, have decided to disprove this conjecture. Given a sequence $a_ i$, calculate how many different values $f$ takes on.


The input consists of two lines.

  • A single integer $1 \leq n \leq 5 \cdot 10^5$, the length of the sequence.

  • The sequence of integers $a_1, a_2, \dots , a_ n$. It is given that $1 \leq a_ i \leq 10^{18}$.


Output a single line containing a single integer, the number of distinct values $f$ takes on over the given sequence.

Sample Input 1 Sample Output 1
9 6 2 4
Sample Input 2 Sample Output 2
9 6 3 4

Please log in to submit a solution to this problem

Log in