Problem Statement
You are working in the Huge Software Company. The company is so huge that it has an infinite number of employees. Employee number 1 is reserved for the Big Boss and Legendary Founder of the company, Mr. Z. Ordinary employees are numbered using positive integers, starting from 2.
At the beginning of the day each employee is assigned a task they should accomplish: for each x from 2 to infinity, employee number x is assigned task number x. During the day some pairs of employees will swap the tasks they were assigned. The swapping follows a precise schedule that is described below.
The working day in the Huge Software Company has infinitely many hours. The hours are numbered using positive integers, starting from 1. During hour 1 there are no swaps at all. During each of the following hours there are infinitely many swaps. These look as follows:
- During hour 2 we have the following swaps: workers 4 and 5 swap their tasks, workers 6 and 7 swap their tasks, workers 8 and 9 swap their tasks, and so on.
- During hour 3 we have the following swaps: workers 6 and 7 swap their tasks, workers 9 and 10 swap their tasks, workers 12 and 13 swap their tasks, and so on.
- ...
- Formally, for each h greater than or equal to 2, during hour h we look at all workers that have numbers divisible by h and strictly greater than h. Each of these workers will swap the task they currently have with the worker with a number one larger than their own.
It can be shown that for each employee there is a finite number of hours after which the employee will never swap their current task with anyone. It can also be shown that for each task there is a finite number of hours after which the task will remain with the current employee forever.
You are given a
Definition
- Class:
- Procrastination
- Method:
- findFinalAssignee
- Parameters:
- long
- Returns:
- long
- Method signature:
- long findFinalAssignee(long n)
- (be sure your method is public)
Constraints
- n will be between 2 and 10^10, inclusive.
Examples
3
Returns: 3
Employee 3 is never involved in any swaps: neither with employee 2, nor with employee 4.
8
Returns: 11
Task 8 starts assigned to employee 8. During hour 2 this employee swaps it for another task with employee 9. During hour 3 employee 9 gives this task to employee 10. Finally, during hour 5 employee 10 gives this task to employee 11 where it will stay forever.
20
Returns: 20
Task 20 goes from employee 20 to employee 21 (during hour 2), then to employee 22 (during hour 3), then back to employee 21 (during hour 7), and finally back to employee 20 (during hour 10). This is where it then remains forever.
196248
Returns: 196259
5587021440
Returns: 5587021440
10000000000
Returns: 10000000003
999999542
Returns: 999999542
999999999
Returns: 999999999
9998242
Returns: 9998244
9998244
Returns: 9998242
9991925
Returns: 9991918
9991918
Returns: 9991925
9928807
Returns: 9928798
99999999
Returns: 100000001
100000001
Returns: 99999999
42424242
Returns: 42424242
99979999
Returns: 99980000
99980000
Returns: 99979999
99960004
Returns: 99960005
299982400
Returns: 299982398
299982398
Returns: 299982400
2500000001
Returns: 2499999998
2499999998
Returns: 2500000001
2499997503
Returns: 2499997503
9997400374
Returns: 9997400374
9997400171
Returns: 9997400168
9997400168
Returns: 9997400171
9997399441
Returns: 9997399441
6983776805
Returns: 6983776805
9999799998
Returns: 9999800001
2
Returns: 2
4
Returns: 5
5
Returns: 4
6
Returns: 6
7
Returns: 7
17
Returns: 17
9
Returns: 9
10
Returns: 10
11
Returns: 8
12
Returns: 12
13
Returns: 13
14
Returns: 16
15
Returns: 15
16
Returns: 14
9999999999
Returns: 9999999999
3141592653
Returns: 3141592653
4302407380
Returns: 4302407380
4561509945
Returns: 4561509945
3837921797
Returns: 3837921797
95769099
Returns: 95769099
2000000015
Returns: 2000000015
1479336262
Returns: 1479336262
1000000000
Returns: 1000000000
9999999998
Returns: 9999999998
9999993440
Returns: 9999993440