Odd numbers below 2e9 and close primes in Hamming distance (Updated)

Given an odd number N with k bits where k>=2, we can ask for the nearest k-bit prime p in Hamming distance, that is the number of bit positions where p and N in base 2 differ. Up to 2×10^9, I get distances of 2 or less. Therefore, among the set P_N = { primes p, p has k bits and Hamming_distance(p, N) <=2}, one can look for the p in P_N such that bitxor(N,P) is the least . Suppose N=9 which is 1001. The 4-bit primes are 11 and 13, and bitxor(9,11) = 2 while bitxor(9, 13) = 4. So for p in P_9, the least value of bitxor(9, p) is 2. 

For odd N < 2×10^9, I find that P_N is non-empty, and we can define delta(N) = min_{p in P_N} (bitxor(p,N)). For example, delta(9)=2. For a k-bit prime p< 2×10^9, delta(p) = 0. For composite odd N < 2×10^9, delta(N) >=1, so we can define the quality q(N) := log(delta(N))/log(N). The quality of N is a measure of how far one must go from N in Euclidean distance to find a prime p with distance_Hamming(p, N)<=2. For the odd N < 2×10^9, I find a maximum q(N) = 0.839711, for N= 77059925. The N < 2e+9 with q(N)> 0.7 are copied below. This is from running my C program Hammingtoprimes750a.c. For the number 45,812,984,491 or in base 2: 101010101010101010101010101010101011 (36 bits), I find that 36-bit numbers that differ by two bits or less are all composite. So 45,812,984,491 is 3 bits away from the nearest 36-bit prime number.

 N       q(N)
17083 0.794432
1561685 0.729189
1561943 0.826253
1561949 0.729316
1924421 0.722718
2347349 0.708802
5279395 0.717464
7952213 0.741861
15947093 0.710504
26127019 0.730605
29381957 0.725560
33204907 0.760460
36001109 0.796764
40807087 0.711961
40807147 0.711964
40811179 0.711957
40872619 0.711923
50506411 0.742589
51401813 0.702760
51467477 0.702655
54875477 0.777918
77059925 0.839711
103110485 0.751326
103112021 0.751325
105556651 0.712854
110448983 0.711110
138237269 0.702597
146973355 0.700307
146975401 0.700309
156620117 0.771415
161830229 0.733435
170044075 0.716313
185685317 0.728113
188383915 0.727587
190352107 0.763535
191173973 0.727001
191186261 0.727023
191190359 0.727405
191190869 0.726998
219867835 0.721708
225094315 0.792908
285561173 0.712029
303387989 0.780803
312125611 0.708779
326456663 0.707156
326458709 0.707155
331921963 0.741885
343649899 0.705315
353020579 0.742642
353020843 0.739562
370715179 0.702624
376665173 0.737134
393906859 0.700446
413837995 0.733638
449074517 0.835007
463121059 0.705946
487937333 0.762245
491424427 0.727338
491432611 0.727338
596290219 0.720424
630543701 0.752600
636835157 0.718039
652913323 0.751307
693983189 0.783103
710235461 0.748205
734699179 0.713034
737061547 0.718667
878007581 0.807818
878134613 0.774154
881153393 0.706719
982182571 0.703013
991288661 0.736162
1006682625 0.702178
1014842741 0.701904
1051372219 0.700709
1382722219 0.724522
1382723503 0.724522
1395305131 0.757129
1423267157 0.756416
1431441735 0.756210
1494570053 0.721854
1571465899 0.785611
1588247467 0.785229
1655368363 0.816363
1705683115 0.717367
1730849419 0.749458
1760209579 0.716307
1785375403 0.715829
1951744853 0.777652
1989498197 0.712222

Hammingtoprimes750a.c listing
#include <stdio.h>
#include <math.h>


long primes[100000];
long tab[1000000][2];

int isprime(long n);
int weight(long n);

int main(void)
{

   long n;
   long j;
   long count=0;
   int pr;
   int test_is_prime;
   int cache_hit;
   long index;
   long parameter;
   long odd;
   long test_number;
   double q;


   for(n=0; n<1000000; n++)
   {
      tab[n][0] = -1;
   }

   for(n=2;n<1000000;n++)
   {
      pr = 1;
      j=2;
      while(j*j <= n)
      {
         if(0== (n%j))
         {
           pr = 0;
           break;
         }
         j++;
      }
      if(pr == 1)
      {
         primes[count] = n;
         count++;
      }
   }

   printf("prime count is %ld\n", count);

   for(parameter  = 1; parameter < 1000000000; parameter++)
   {
      odd = 2*parameter+1;
      for(j=0; j<odd; j++)
      {
          if(weight(j)<3)
          {
             test_number = odd^j;

             index = test_number%1000000;
             if(tab[index][0] == test_number)
             {
                cache_hit = 1;
                test_is_prime = tab[index][1];

             }
             else
             {
               cache_hit = 0;
               test_is_prime = isprime(test_number);
               tab[index][0] = test_number;
               tab[index][1] = test_is_prime;
             }


             if(test_is_prime)
             {
                q =0.0;
                if(j>0)
                {
                    q = log( (double)j)/log((double)odd);
                }
                if(q > 0.7)
                {
                    printf("%ld %.6lf\n", odd, q);
                }
                break;
             }
          }

          if(j == (odd-1) )
          {
              printf("j has reached %ld\n", j);
          }
      }
   }

   return 0;



}

int isprime(long n)
{
    long j=0;
    int t = 1;
    while(primes[j]*primes[j] <=n)
    {
       if(0==(n%primes[j]))
       {
          t = 0;
          break;
       }
       j++;
    }

    return t;
}

int weight(long n) {
   int w = 0;
   while (n) {
      w += n & 1;
      n >>= 1;
   }
   return w;
}