A clockmaker mounts a single starter gear with n teeth inside an empty case. Whenever a gear with x teeth is turning inside the case, the vibration can seat a new compatible gear with y teeth alongside it for any y satisfying 1 < y < x and x mod y == 1 (the teeth mesh with exactly one tooth of slack). Once a gear is seated it keeps turning forever, and every gear currently turning keeps triggering new compatible gears by the same rule, over and over, until no gear rule can seat anything new.
Given the starter gear's tooth count, determine how many distinct tooth counts are ever turning in the case once the cascade settles.
A single line containing one integer n, the starter gear's tooth count.
A single integer: the number of distinct tooth counts that end up turning in the case.
Example 1
Input
5
Expected
4
Explanation
Start with gear 5. It seats gears 4 and 2 (5 mod 4 = 1, 5 mod 2 = 1). Gear 4 then seats gear 3 (4 mod 3 = 1). Gear 3 would seat gear 2, but it is already present. No further gears can be seated, so the final set is {2, 3, 4, 5}, giving 4 distinct tooth counts.
Example 2
Input
1
Expected
1
Explanation
The only gear is 1 tooth. There is no y with 1 < y < 1, so no new gear can ever be seated. The final set is {1}, giving 1 distinct tooth count.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →