Question 34
Let $n$ be a positive integer. Positive integers $1, 2, \dots, n$ are written in a row in some order. For any two neighboring numbers their GCD is written on the paper. Find the greatest possible number of distinct numbers among all $n-1$ numbers written on the paper.