Firstly note there are a number of solutions to this problem, but we'll tackle the dp solution.
lemma 1 the most unique gcds occur when the number of prime factors of the first number in the permutation is maximum.
This is easy to see as when choosing an additional number for the permutation we must either reduce the gcd or keep it the same, it cannot increase. We can then notice that the only way to achieve unique gcds is reducing the original gcd, and furthermore it must be reduced by a factor of the gcd. Hence the most unique gcds occur when the number of reductions is maximum, which is possible when the number of prime factors is maximum (note: not unique prime factors).
lemma 2 the first number of the permutation must be made up of some \(2^j \cdot 3^k\)
This is also easy to see as \(2^2 < 5\) thus there would be at least 2 factors of 2 for every factor of \(5\), the only factors that may be present are that which \(2^2 \leq p\) which only occurs for \(p=3\) and \(p=2\)
lemma 3 the first number of the permutation must be made up of some \(2^j \cdot 3^k\) where \(k\) is either \(0\) or \(1\)
Using the same principle as above \(2^3 < 3^2\) hence where \(y > 1\) there exists a number in the permutation with more prime factors. Thus no more than 1 factor of 3 can exist in this first number

Using these lemmas we can construct our dp where we define some recursive function \(f\) such that \(f(i,j,k)\) gives the resultant number of permutations possible after selecting \(i\) numbers of our permutation and ending with a prefix gcd of \(2^j \cdot 3^k\). We need to traverse the 3 possible dependencies of \(f(i+1, j, k)\), \(f(i+1, j-1, k)\), and \(f(i+1, j, k-1)\). In other words the next count if the gcd does not decrease, decreases by a factor of 2, or decreases by a factor of 3. In each case there are \(\lfloor\frac{n}{2^j \cdot 3^k - i}\rfloor\) factors possible at the current position. In order to not count invalid prefixes, when decreasing by a factor of 2 or 3, numbers that would result in the same gcd, must be excluded. Hence the number of factors for this point of a path would be inclusive of all numbers chosen so far and can be represented as \(\lfloor\frac{n}{2^{j-1} \cdot 3^k}\rfloor - \lfloor\frac{n}{2^{j} \cdot 3^k}\rfloor\) when decreasing by a factor of 2, and a similar case with \(k-1\) for decreasing by a factor of 3.

run the dp and your result will be \(f(0, log_{2}{n}, 0) + f(0, (log_{2}{n}) - 1, 1)\) when \(log_{2}{n}\cdot 3 \leq n\) and just \(f(0, log_{2}{n}, 0)\) when this is not the case.

It's easy to see that both the time and space complexity of this are \(O(n \cdot log(n))\) as each point in our dp is \(O(1)\) to compute, and stores \(n\cdot log_{2}{n} \cdot 2\) points

Be sure to use memory efficiently and not do too many modulo operations as the bounds are quite tight

challenge There exists an \(O(log(n))\) solution. Can you find it?