[seqfan] Re: A088144 and A076409 (esp the latter)

[Richard Guy]

I sh'd've said more in the last paragraph of the
message below.  The subsequences of A076409 and
A076410  which attain to primes  p = 4k+3  merit
separate listing (and perhaps their complements,
i.e., the terms attaining to primes  4k+1,  but I
leave a decision on that to the editors):

Note that the sum of the quadratic residues of
a prime of either shape is always  (k-e)p
where  e = 0  for the  4k+1  primes, and is
also zero for those  4k+3  primes whose class
number of the quadratic field of discriminant
-p  is one.  I don't have the list of nine in
front of me, but from what follows we see that
7, 11, 19, 43, 67, 163  are included.  [Later:
I see that it's  A003173  and the other three
are  1, 2, 3.]

Suggested sequences:

sum of q.r.s of primes  4k+3  [subseq of A076409]:

1,7,22,76,92,186,430,423,767,1072,994,1343,1577,2369,
2675,3683,3930,4587,5134,6520,6012,7518,7813,8955,10761,

previous seq divided by  4k+3, i.e.,  k-e  in the formula
(k-e)(4k+3)  [subseq of A076410]:

?,1,2,4,4,6,10,9,13,16,14,17,19,23,25,29,30,33,34,40,36,
42,41,45,51,

The quantity  e  in the above (with zeroes corresponding
to Heegner numbers)  [this quantifies David Wilson's
remark under `FORMULA' in A076410]:

?,0,0,0,1,1,0,2,1,0,3,2,1,2,1,2,2,1,3,0,5,2,6,4,1,

This relates to an old problem (I first got it from
Davenport about 60 years ago) about finding an elementary
proof that, for  4k+3  primes, there are more quadratic
residues in the interval  [1,2k+1]  than there are in
[2k+2,4k+2].  These numbers also merit a place in OEIS:

Number of q.r.s in the first half:

1, 2, 4, 6, 7, 9,12,14,19,18,21,22,25,28,31,

Number of q.r.s in the last half:

0, 1, 1, 3, 4, 6, 9, 9,10,15,14,17,16,23,22,

Excess of first half over last half:

1, 1, 3, 3, 3, 3, 3, 5, 9, 3, 7, 5, 9, 5, 9,

All of these sequences, especially the last three,
should be extended by someone who knows how to use
a computer.  And my hand calculations are unlikely
to be error-free.

Further exercise for the reader:  find that
elementary proof, independent of class numbers
of imaginary quadratic fields.  Best of luck,  R.

On Wed, 23 Feb 2011, Richard Guy wrote:

> Dear JM Bergot,
>               I'm copying my reply to
> the seqfan network, as there are one or
> two things they may like to add to OEIS.
>
>               The sum of the primitive roots
> of  p  (A088144) is a multiple of  p  whenever
> p  is of shape  4k+1.  This is because the
> primitive roots come in pairs,  r  and  p-r,
> and their number is  phi(phi(p)) = phi(p-1),
> and the total is  p * phi(p-1) / 2,  though I
> didn't see that this was mentioned in  A088144.
> The sum is also a multiple of  p  for  p = 19;
> are there other examples?  Searching for the
> sequence  5, 13, 17, 19, 29, ... didn't give
> any hits.  Perhaps it would be of interest to
> list the subsequence
>
> 2 = 1*3 - 1,  8 = 1*7 + 1,  23 = 2*11 + 1, 57 = 3*19,  139 = 6*23 + 1,  123 = 
> 4*31 - 1,
> 257 = 6*43 - 1,  612 = 13*47 + 1, 886 = 15*59 + 1,
> 669 = 10*67 - 1, 1064 = 15*71 - 1, 1105 = 14*79 - 1,
> 1744 = 21*83 + 1, ...
>
> and of the coefficients
>
> 1, 1, 2, 3, 6, 4, 6, 13, 15, 10, 15, 10, 14, 21, ...
>
> and even the ``errors''
>
> -1, 1, 1, 0, 1, -1, -1, 1, 1, -1, -1, -1, 1, ...
> (are there any more zeroes? or any terms other
> than 1 & -1 ?)
>
>      In answer to your second question, the
> sum of the primitive roots is equal to the sum
> of the quadratic residues (A076409) for  p = 5
> and  p = 17  and perhaps (only?) for the Fermat
> primes.  Here it IS mentioned that the sum is
> k(4k+1)  when  p= 4k+1  and  A076410  confirms
> that the sum is always a multiple of  p, though
> it would be good to mention this at A076409.
>
>      Best,   R.
>
> On Mon, 21 Feb 2011, JM Bergot wrote:
>
>>  Do you think it is possible for:
>>  (1)The sum of the primitive roots of some 
>>       prime p is divisible by p.
>>   
>>  (2)The sum of the quadratic residues for
>>       some prime p is the same as the sum
>>       of its primitive roots, say for some p
>>      of the form 2*q+1=p for prime q.
>