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,2

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

Table of n, a(n) for n=1..87.

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.

Crossrefs

Sequence in context: A009661 A023576 A271523 * A125844 A171025 A222362

Adjacent sequences: A352900 A352901 A352902 * A352904 A352905 A352906

Keyword

nonn,hard

Author

Yuda Chen, Apr 07 2022

Extensions

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

Status

approved