CJam (2182 2780 3034 sequences)
{:ZA3#:Cb(40-z_!!:B-\+CbB)/)_mqmo:M+:NK{)[N0{N1$_*-@/M@+1$md@M@-}K*]<W%B{X0@{2$*+\}%}*ZB&=}%\C)<f*} This gives correct answers for the inclusive ranges
[A040000, A040003],[A040005, A040008],[A040011, A040013],A040015,[A040019, A040022],A040024,[A040029, A040033],A040035,A040037,[A040041, A040043],A040048,A040052,[A040055, A040057],A040059,A040063,[A040071, A040074],A040077,A040080,[A040090, A040091],[A040093, A040094],A040097,A040099,[A040109, A040111],A040118,A040120,[A040131, A040135],A040137,A040139,[A040142, A040143],A040151,[A040155, A040157],A040166,A040168,[A040181, A040183],[A040185, A040968][A041006, A041011],[A041014, A042937]A006983,[A011734, A011745],[A023975, A023976],[A025438, A025439],[A025443, A025444],A025466,A025469,[A034422, A034423],A034427,A034429,A034432,A034435,[A034437, A034439],A034441,A034443,A034445,A034447,[A034449, A034459],[A034461, A034462],[A034464, A034469],A034471,A034473,[A034475, A034477],[A034479, A034487],[A034489, A034490],[A034492, A034493],A034495,[A034497, A034512],[A034514, A034516],[A034518, A034523],[A034525, A034582],A036861,A047752,A052375,A055967,A061858,A065687,A066035,A067159,A067168,A070097,A070202,A070204,[A070205, A070206],A072325,A072769,A076142,A082998,A083344,A085974,A085982,A086007,A086015,A089458,A093392,A094382,A105517,A108322,A111855,A111859,[A111898, A111899],A112802,A122180,A129947,A137579,A159708,[A161277, A161280],A165766,A167263,A178780,A178798,A180472,A180601,A181340,A181735,A184946,A185037,A185203,[A185237, A185238],[A185245, A185246],A185255,A185264,A185284,A191928,A192541,A197629,A198255,A200214,A206499,A210632,A212619,[A217148, A217149],A217151,[A217155, A217156],A228953,A230533,A230686,A235044,A235358,A236265,A236417,A236460,A238403,[A243831, A243836],A248805,A250002,A256974,A260502,A264668,A276183,A277165,A280492,A280815
The A040??? sequences correspond to the continued fractions of non-rational square roots from sqrt(2) to sqrt(1000) (with the gaps corresponding to ones which appear earlier in OEIS, but conveniently filled with random sequences). The A041??? sequences correspond to the numerators and denominators of the continued fraction convergents for non-rational square roots from sqrt(6) to sqrt(1000) (with the gap corresponding to sqrt(10), at A005667 and A005668). The other assorted sequences have zeroes for their first twenty values.
The answer ports elements of two earlier answers of mine in GolfScript:
Many thanks to xnor for the short closed form x -> x + round(sqrt(x)) mapping sequence offsets to the value to sqrt. The savings over my previous calculation (generating the list of non-squares and selecting by index) provided enough to have an all-zero fallback for most out-of-range indices.
