even Q(n)

[Dean Hickerson]

Christian G. Bower wrote:

> The 1's had not been tallied yet, so I entered them as A114913.
> Interesting thing is that the sequence is very similar to A111174
> 
> A114913  Values such that A114912(a(n))=1. Values such that
> A000009(a(n))==2 (mod 4).

That last line should be:  A000009(n)==2 (mod 4).

> 3, 4, 8, 10, 13, 14, 17, 18, 19, 24, 25, 28, 32, 39, 42, 43, 47, 48, 50, 52,
> 54, 55, 62, 67, 69, 73, 74, 75, 76, 78, 83, 84, 87, 88, 89, 90, 95, 99, 101,
> 103, 105, 108, 109, 112, 113, 118, 119, 123, 125, 127, 130, 132, 134, 138,
> 140, 143, 144, 147, 149, 153, 154, 157
>
> A111174 Numbers n such that 24*n + 1 is prime.
>
> 3, 4, 8, 10, 13, 14, 17, 18, 19, 24, 25, 28, 32, 39, 42, 43, 47, 48, 50, 52,
> 54, 55, 62, 67, 69, 73, 74, 75, 78, 83, 84, 87, 88, 89, 90, 95, 99, 103, 105,
> 108, 109, 112, 113, 118, 119, 123, 125, 127, 130, 132, 134, 138, 140, 143,
> 144, 147, 153, 154, 157, 158, 162 (list)
>
> matching in the first 28 terms.  A little more searching and it appears
> that every number in A111174 is in A114913, but there are probably
> infinitely many numbers in the latter not in the former.

Yes, for example if 24*n+1 = 25p for some prime p, then n will be in
A114913 but not in A111174; see below.

> I looked a little at Dean Hickerson's 8/4/2005 posting about q(n) mod 64.
>
> I didn't fully understand it, but it does not appear to have an obvious
> connection to prime number theory.

Here's what I wrote about Q(n) mod 64:

> I looked at Q(n) mod small powers of 2 a few years ago.  I found that the
> value of Q(n) mod 64 is determined by representations of 24n+1 by the binary
> quadratic form x^2 + 24 y^2.  Specifically:
>
> Let f(x,y) be determined by the values of x mod 192 and y mod 2:
>
>   x mod 192    1   5   7  11  13  17  19  23  25  29  31  35  37  41  43  47
>   f(x,even)    1  51  55  29   5  15  27  25  41  11  31  53  45  39   3  49
>   f(x,odd)     7   5   1  11   3   9  29  15  31  13  25  19  27  17  21  23
>
>   x mod 192   49  53  55  59  61  65  67  71  73  77  79  83  85  89  91  95
>   f(x,even)   17  35   7  13  21  63  43   9  57  59  47  37  61  23  19  33
>   f(x,odd)    23  21  17  27  19  25  13  31  15  29   9   3  11   1   5   7
>
>   x mod 192   97 101 103 107 109 113 115 119 121 125 127 131 133 137 139 143
>   f(x,even)   33  19  23  61  37  47  59  57   9  43  63  21  13   7  35  17
>   f(x,odd)     7   5   1  11   3   9  29  15  31  13  25  19  27  17  21  23
>
>   x mod 192  145 149 151 155 157 161 163 167 169 173 175 179 181 185 187 191
>   f(x,even)   49   3  39  45  53  31  11  41  25  27  15   5  29  55  51   1
>   f(x,odd)    23  21  17  27  19  25  13  31  15  29   9   3  11   1   5   7
>
> Let b(n) be the sum of f(x,y) over all solutions of
>
>     24n+1 = x^2 + 24 y^2,  x>0.                                         (0)
>
> Then
>
>     Q(n) == b(n) (mod 64).                                              (1)

If we're only interested in Q(n) mod 4, we can simplify this to:

Let c(n) be the number of solutions of (0).

If  24n+1  is not a square or if  sqrt(24n+1) == 1 or 11 (mod 12),  then

    Q(n) == c(n) (mod 4).  

If  sqrt(24n+1) == 5 or 7 (mod 12)  then

    Q(n) == c(n) + 2 (mod 4).

For example, if n=51, then the solutions of (0) are

    (x,y) = (7,#7), (19,#6), (25,#5), (29,#4), (35,0)

(where "#" means plus or minus), so  c(51)=9.  Since
sqrt(24n+1) = 35 == 11 (mod 12),  we should have Q(51) == c(51) == 1 (mod 4).
And in fact Q(51) = 4097 == 1 (mod 4).

What follows is implied by the arithmetic of Q(sqrt(-6)); I'll skip the
details.

If 24n+1 is prime, then there's exactly one solution of (0), so
Q(n) == 2 (mod 4).

More generally, we can determine c(n) from the prime factorization of 24n+1:

Let

    24n+1 = p_1^e_1 * ... * p_r^e_r * q_1^f_1 * ... * q_s^f_s,

where the p_i's are distinct primes == 1, 5, 7, or 11 (mod 24) and the q_i's
are distinct primes == 13, 17, 19, or 23 (mod 24).  If some f_i is odd, then
c(n) = 0.  Otherwise,

    c(n) = (e_1 + 1) * ... * (e_r + 1).

So  c(n) == 2 (mod 4)  iff all of the f_i's are even and all but one of the
e_i's are even and the one e_i which is odd is == 1 (mod 4).

Since Q(n) and c(n) are both odd if 24n+1 is a square, we can replace c by Q
in this:

Q(n) == 2 (mod 4)  iff all of the f_i's are even and all but one of the
e_i's are even and the one e_i which is odd is == 1 (mod 4).

In particular, if 24n+1 = 25p for some prime p, then c(n) == 2 (mod 4),
so there are infinitely many n in A114913 but not in A111174.

Dean Hickerson
dean at math.ucdavis.edu