A marked integer ruler has length $n$ and integer marks from $0$ to $n$. It can measure any integer length from $1$ to $n$. The two ends of the ruler, $0$ and $n$ are considered marks.
A sparse ruler can also measure any integer length from $1$ to $n$, but has a minimal number of marks. For example, for length $24$, the nine marks at $(0, 1, 13, 14, 16, 18, 20, 22, 24)$ suffice for measuring all distances from $1$ to $24$.
For any $n$, a sparse ruler of length $n$ can be constructed with $E+\lceil {\sqrt {3n+{\tfrac {9}{4}}}}\rfloor $ marks, $E$ being the the $0$ or $1$ excess of the ruler, with OEIS A326499 giving the best known excess values, known to be true up to 213.
In the example above, the ruler has a gap longer than a third of the length of the ruler, making it a large gap sparse ruler. Here are more examples of sparse rulers with large gaps:
The length $322$ large gap sparse ruler is currently the longest known example. $(0, 1, 2, 3, 14, 15, 16, 17, 22, 151, 165, 170, 175, 180, 189, 198, 207, 216, 225, 234, 243, 252, 261, 270, 279, 288, 297, 306, 310, 314, 318, 322)$
Can anyone find a length $n>322$ ruler with $1+\lceil {\sqrt {3n+{\tfrac {9}{4}}}}\rfloor $ marks that can measure all lengths from $1$ to $n$ and has a gap of length greater than $n/3$?
Slightly harder: Is there a longer large gap sparse ruler? More explicitly: Can anyone find a length $n>322$ ruler with $E+\lceil {\sqrt {3n+{\tfrac {9}{4}}}}\rfloor $ marks that can measure all lengths from $1$ to $n$ and at least gap of length greater than $n/3$, and $E$ being the the $0$ or $1$ excess value for $n$ listed in OEIS A326499?
The second largest of length 262 has marks at these locations: $(0, 1, 2, 3, 4, 5, 6, 7, 131, 136, 141, 146, 154, 162, 170, 178, 186, 194, 202, 210, 218, 226, 234, 242, 250, 253, 256, 259, 262)$, representable in the five part gap-repetition form $1^7 124^1 5^3 8^{13} 3^4$. This is the longest known sparse ruler with a five part gap-repetitions. The longest known with three part gap-repetitions has length 69 with $1^6 8^7 7^1$. There are infinite sparse rulers with six or more gap-repetitions, the Wichmann-like rulers.
EDIT: Re-running some code managed to improve the best known large gap sparse ruler slightly. The value $344$ is now the value to beat.
Here are the marks for the pictured sparse rulers.
{
{0,1,2,3,4,5,6,7,8,141,153,164,170,178,187,196,205,214,223,232,241,250,259,268,277,286,295,296,301,308,316,324},
{0,1,2,3,4,5,6,7,8,142,148,154,165,168,178,187,196,205,214,223,232,241,250,259,268,277,286,295,303,311,318,324},
{0,1,4,5,8,11,12,15,16,151,164,171,177,186,195,204,213,222,231,240,249,258,267,276,285,294,303,305,308,319,322,324},
{0,1,4,17,20,21,30,39,48,57,66,75,84,93,102,111,120,129,138,147,153,161,172,307,309,311,312,314,317,319,322,324},
{0,1,2,6,7,8,12,13,14,150,153,170,173,182,191,200,209,218,227,236,245,254,263,272,281,290,299,305,307,309,321,324},
{0,1,3,4,5,7,8,11,15,151,159,167,175,184,193,202,211,220,229,238,247,256,265,274,283,292,301,302,312,314,322,324},
{0,1,2,6,7,8,12,13,14,150,154,170,173,182,191,200,209,218,227,236,245,254,263,272,281,290,299,305,307,310,321,324},
{0,1,4,5,7,8,11,12,15,151,159,167,175,184,193,202,211,220,229,238,247,256,265,274,283,292,301,302,312,314,322,324},
{0,1,4,5,7,8,11,12,15,151,161,166,172,177,186,195,204,213,222,231,240,249,258,267,276,285,294,303,307,309,322,324},
{0,1,4,5,6,7,8,11,12,151,161,166,172,177,186,195,204,213,222,231,240,249,258,267,276,285,294,303,307,309,322,324},
{0,1,2,3,8,13,14,15,16,159,164,169,178,187,196,205,214,223,232,241,250,259,268,277,286,295,299,303,316,319,320,324},
{0,1,2,3,4,5,6,7,8,139,150,158,165,175,184,193,202,211,220,229,238,247,256,265,274,283,292,297,305,313,321,325},
{0,1,2,3,4,5,6,7,8,144,154,165,170,179,188,197,206,215,224,233,242,251,260,269,278,287,296,300,308,315,320,325},
{0,1,2,6,7,8,12,13,14,151,154,171,174,183,192,201,210,219,228,237,246,255,264,273,282,291,300,306,308,310,322,325},
{0,1,2,3,4,5,6,7,8,150,162,173,179,187,196,205,214,223,232,241,250,259,268,277,286,295,304,313,314,319,326,334,342},
{0,1,2,3,4,5,6,7,8,151,157,163,174,177,187,196,205,214,223,232,241,250,259,268,277,286,295,304,313,321,329,336,342},
{0,1,4,5,8,11,12,15,16,160,173,180,186,195,204,213,222,231,240,249,258,267,276,285,294,303,312,321,323,326,337,340,342},
{0,1,4,17,20,21,30,39,48,57,66,75,84,93,102,111,120,129,138,147,156,162,170,181,325,327,329,330,332,335,337,340,342},
{0,1,2,6,7,8,12,13,14,159,162,179,182,191,200,209,218,227,236,245,254,263,272,281,290,299,308,317,323,325,327,339,342},
{0,1,3,4,5,7,8,11,15,160,168,176,184,193,202,211,220,229,238,247,256,265,274,283,292,301,310,319,320,330,332,340,342},
{0,1,2,6,7,8,12,13,14,159,163,179,182,191,200,209,218,227,236,245,254,263,272,281,290,299,308,317,323,325,328,339,342},
{0,1,4,5,7,8,11,12,15,160,168,176,184,193,202,211,220,229,238,247,256,265,274,283,292,301,310,319,320,330,332,340,342},
{0,1,4,5,7,8,11,12,15,160,170,175,181,186,195,204,213,222,231,240,249,258,267,276,285,294,303,312,321,325,327,340,342},
{0,1,4,5,6,7,8,11,12,160,170,175,181,186,195,204,213,222,231,240,249,258,267,276,285,294,303,312,321,325,327,340,342},
{0,1,2,3,8,13,14,15,16,168,173,178,187,196,205,214,223,232,241,250,259,268,277,286,295,304,313,317,321,334,337,338,342},
{0,1,2,3,4,5,6,7,8,148,159,167,174,184,193,202,211,220,229,238,247,256,265,274,283,292,301,310,315,323,331,339,343},
{0,1,2,3,4,5,6,7,8,153,163,174,179,188,197,206,215,224,233,242,251,260,269,278,287,296,305,314,318,326,333,338,343},
{0,1,2,6,7,8,12,13,14,160,163,180,183,192,201,210,219,228,237,246,255,264,273,282,291,300,309,318,324,326,328,340,343},
{0,1,2,3,4,5,6,7,8,148,160,172,176,183,193,202,211,220,229,238,247,256,265,274,283,292,301,310,319,324,332,339,344},
{0,1,2,6,7,8,12,13,14,158,160,179,182,186,195,204,213,222,231,240,249,258,267,276,285,294,303,312,321,324,327,341,344},
{0,1,2,6,7,8,12,13,14,161,164,181,184,193,202,211,220,229,238,247,256,265,274,283,292,301,310,319,325,327,329,341,344},
{0,1,2,6,7,8,12,13,14,161,163,180,183,192,201,210,219,228,237,246,255,264,273,282,291,300,309,318,324,325,328,341,344}
}
Here's the Excess pattern (OEIS A326499), gray=0 and black=1. The first 1 value is at 51. NJA Sloane called this pattern "Dark Mills on a Cloudy Day". The first few "cloud" values are $474, 501, 582, 609, 669, 792, 793$.
I tried solving the "easier" problem, excess=1 longgap rulers, my program ignoring the optimal values. I managed to find some solutions for lengths $445, 471, 497, 523, 549, 575$. Note that the difference between these lengths is 26. But none is a valid sparse ruler.
Weirdly, though, I got a lot more solutions for the first three "cloud" values, 474, 501 and 582. These are all valid sparse rulers, unless an excess=0 solution exists for these lengths.
Here are the 501 sparse rulers:
I'm not sure why the cloud values are magnets for these big gap rulers. And the challenge is still open, if anyone else can find solutions. The new ruler to beat has length 582.
{{1,7,1,246,6,16,1,6,1,7,13,6,24,6},{5,2,5,1,2,1,1,1,1,1,17,2,1,2}}
And that's the latest find on sparse rulers.