Jawaian Weapon Set
Time limit3sMemory limit256 MB
Find the k-th triple of primes (d1<=d2<=d3) in lexicographic order satisfying three divisibility conditions involving squares minus one.
- Level
Hard9 of 10
- Topics
- Number theory, Math, Brute force, Sorting
- Solved
- No attempts yet
Problem
Since ancient times, every Jawain has owned a set of three weapons: a laser sword, a laser saber, and a laser knife for spreading butter on bread (in case the Jawain gets hungry).
But these are Jawaian weapons, not ordinary ones, so the lengths of the items in the set had the following restrictions:
- The length of the knife d1, the length of the saber d2, and the length of the sword d3 must all be prime numbers.
- d1 ≤ d2 ≤ d3
- (d1 + d2)2 − 1 is divisible by d3.
- (d2 + d3)2 − 1 is divisible by d1.
- (d3 + d1)2 − 1 is divisible by d2.
The company "Dart Generics Industries" sells every Jawaian weapon set by its number in lexicographic order. More precisely, sort all Jawaian sets by nondecreasing d1, then by nondecreasing d2 when d1 is equal, and then by increasing d3 when d1 and d2 are equal, and number them from 1 to infinity in that order. Then for a given k you can buy the k-th set in this order.
The Jawain Anykey wants to buy the k-th set. Tell him the sizes of his weapons.
Input
The first line contains a single integer k (1 ≤ k ≤ 60000).
Output
Print the three sizes of the weapons in the k-th set in nondecreasing order.