[math-fun] A046693 and sparse rulers. Simple proof that smallest covering subset of {0, ..., n} has a size less than sqrt(3 n)+4
A Wichmann ruler has the form 1^r, r+1, (2r+1)^r, (4r+3)^s, (2r+2)^(r+1), 1^r. I find it more convenient to code this as {{1,1+r,1+2 r,3+4 r,2+2 r,1},{r,1,r,s,1+r,r}} This ruler can be extended with a mark at the end. 1^r, r+1, (2r+1)^r, (4r+3)^s, (2r+2)^(r+1), 1^r, (r+1)^1. The last mark could be of size less than r+1. The ruler could also be extended multiple times. The following Mathematica code gives complete rulers of length 123 to 1256, each having less than sqrt(3 n)+4 marks. I arbitrarily cut this off at r=9, but a much larger r could be used to extend the complete rulers to infinity. xx=9;upto9=Flatten[Table[Transpose[Select[Transpose[Flatten/@{{1,1+r,1+2 r,3+4 r,2+2 r,1,If[t<r+1,{t},{r+1,Last[IntegerDigits[t, r+1]]}]},{r,1,r,s,1+r,r,If[t<r+1,{1},{First[IntegerDigits[t, r+1]],1}]}}], First[#]>0&]],{r,3,xx},{s,2 r-2,2r+3},{t,0,4 r+2}],2]; I think sqrt(3 n)+4 is a better upper bound than the John Leech bound of sqrt(3.348 n), and it builds the subset. What do people think of this demonstrative proof? --Ed Pegg Jr
participants (1)
-
ed pegg