Ｃでも書いてみた。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
long *TBL;
int MAX_INDEX;
int b_search(long n){
  int m, l = 0, r = 3162;
  while(r - l > 1){
    m = (l + r) / 2;
    if(*(TBL + m) == n) return 1;
    if(*(TBL + m) > n) r = m; else l = m;
  }
  return 0;
}
int main(){
  long i, j, k, n;
  MAX_INDEX = sqrt(9999000);
  TBL = malloc(MAX_INDEX * sizeof(long));
  for(i = 0; i * i <= 9999000; i++) *(TBL + i) = i * i;
  for(k = 999; k <= 999000; k += 999){
    for(j = 1; j <= 9; j++){
      n = k + j * 1000000;
      if(b_search(n))  printf("%ld\n", n);
    }
  }
  free(TBL);
  return 0;
}