A071383

[John Conway]

> A071383 says :
>         
> 1,5,25,65,325,1105,4225,5525,27625,71825,138125,160225,801125,2082925,
> 4005625,5928325,29461625,77068225,148208125,243061325
> 
> %N A071383 Squared radius of first circle around (0,0) with more points of
> the square lattice on its circumference than on any smaller circle around
> (0,0).

   [By rights, this should start with a  0, corresponding to the point 
circle.]  

   But let me think about this sequence  f(n).  It's clear that the 
squared radius is a product of primes of the form  4n+1,  and that 
one-quarter of the number of points is the product of a factor for each 
exact prime power divisor  P = p^k  of  N = f(n).

    What is this factor?  Well, for 

    P prime, say 5,  it's  2  (1 from  2+i,  1 from  2-i)

    P = p^2, say 25, it's  3  (from  (2+i)^2, (2+i).(2-i), (2-i)^2)

and so on,  making it obvious that the factor is just  k+1.  This
evaluates the numbers of points corresponding to the first terms thus:

      N               # of points
   
    1 = 1             1
    5 = 5             2
   25 = 5^2           3
   65 = 5x13          2x2
  325 = 5^2x13        3x2
 1105 = 5x13x17       2x2x2
 4225 = 5^2x13^2      3x3
 5525 = 5^2x13x17     3x2x2

   It's clear that the optimal  N  have the form  5^a.13^b.17^c...
with  a >= b >= c >= ... .  So we have to increase

       log #  =  log(a+1) + log(b+1) + log(c+1) + ...

while keeping

       log N  =   a.log5  +  b.log13 +  c.log17 + ...

as small as possible.

   Let's look at "derivatives".  Increasing the exponent, say d,  of  p
by  1  increases  log(#)  by  log(1 + 1/d) ~ 1/d,  but  log(N)  by  
log(p), for a "derivative" of 

             log(1 + 1/d)/log(p)  ~  1/(p^d).

So the optimal  N  will be those for which all the  p^d  are 
roughly the same size  P,  so that  N  will be roughly  P^K, where
K  is their number.  

    In particular, the largest prime involved is now seen to be
roughly  P,  and so the number  K  must be the number of primes
less than  P,  or about  P/logP.   This gives us the desired
relation between  P  and  N :

             N = P^(P/logP),  logN = logP x P/logP = P.

   From this it's easy to deduce your conjecture that

        log(next N) - log(N)  --> 1.

   John Conway