Let $N$ be a positive integer. There are $N$ tasks, numbered $1, 2, 3, \ldots, N$, to be completed. Each task takes one minute to complete and the tasks must be completed subjected to the following conditions: Any number of tasks can be performed at the same time. For any positive integer $k$, task $k$ begins immediately after all tasks whose numbers are divisors of $k$, not including $k$ itself, are completed. Task 1 is the first task to begin, and it begins by itself. Suppose $N = 2017$. How many minutes does it take for all of the tasks to complete? Which tasks are the last ones to complete?
Problem
Source: Canada Repêchage 2017/6
Tags: number theory
Not_a_Username
13.04.2017 16:11
After each minute, a task with a higher number of prime factors can occur. So after task one, prime tasks can start, and then ones with 2 prime factors(not necessarily distinct), etc. The last tasks will be the ones with the most number of prime factors (not necessarily distinct). Since $2^{11}>2017$, this means the maximum is ten prime factors, which would mean the process finishes after 11 minutes. The ways to get 10 factors are $2^{10}, 2^9\cdot 3$, so these are the last tasks to finish.
rafayaashary1
13.04.2017 16:13
Define the height of an integer $n$ (write $h(n)$) as the sum of the exponents in its prime factorization. By doing tasks with height $0$, then those with height $1$, etc... we can finish in $1+\max_{1\leq i\leq 2017}\bigg(h(i)\bigg)$ minutes. Also it is easy to find which tasks are completed last; those with maximal height. Now suppose that $n=\prod p_i^{e_i}$ has $h(n)$ maximal. Then tasks $1,p_1,p_1^2,\dots,p_1^{e_1},p_1^{e_1}p_2,\dots \prod p_i^{e_i}$ must occur at different times, so this construction is, in fact, optimal. Finding the time and extremal cases explicitly is bashy tho