A352903 a(n) is the minimum number of steps required to construct a segment of length sqrt(n) in compass-and-straightedge construction.

1, 5, 3, 2, 6, 5, 5, 5, 3, 5, 5, 4, 5, 5, 5, 3, 6, 5, 6, 6, 5, 6, 6, 5, 4, 6, 5, 5, 6, 6, 6, 6, 5, 6, 5, 4, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 4, 6, 6, 5, 7, 6, 6, 6, 6, 6, 7, 5, 6, 7, 6, 4, 6, 6, 6, 7, 6, 6, 7, 6, 6, 7, 6, 6, 6, 6, 6, 6, 5, 7, 7, 5, 7, 7, 7

Offset: 1

Author

Yuda Chen, Apr 07 2022

Keywords

• nonn
• hard

Comments

Compass-and-straightedge construction allows the use of only a straightedge (without scale) and a collapsing compass. A "step" consists of constructing a line or constructing a circle with a point as its center. Constructing an intersection uses 0 steps.

Given two points in the plane, separated by a unit distance, a segment of length sqrt(n) cannot be constructed in fewer than a(n) steps.

Proving that "a(2021) is not more than 10" was the 2021 Chinese Mathematical Olympiad's Problem 5. According to Y. Ai et al., it is known that a(2021) is not more than 8 and not less than 7 because the maximum k such that a(k)=6 is 1024.

The sequence greatest k such that a(k) = n begins at 1, 4, 16, 64, 256, 1024, 170569, ... - Jinyuan Wang, Jul 18 2023

Links

• Y. Ai et al., Analysis of Questions and answers about the National Senior High School's Mathematical Olympiad in 2021 (Final) (in Chinese).
• L. Jin, The generalized version of 2021 CMO Problem 5 (in Chinese).
• Jinyuan Wang, Illustration of initial terms
• Jinyuan Wang, PARI program
• Index to sequences related to Olympiads.

Extensions

a(6) corrected by and more terms from Jinyuan Wang, Jul 17 2023