OFFSET
1,2
COMMENTS
The companion sequence is A212354.
There are at most two incongruent solutions of this congruence due to the degree. The fact that there are precisely two such solutions for each prime of the form 4*k+1 (see A002144) is due to the reduction of this problem to one of quadratic residues, namely to X^2 == -1 (mod 2p), with p a prime (see the Nagell reference, given in A210848, pp. 132-3, especially theorem 77), adapted to the quadratic form f(x) = 2*x^2 + 2*x + 1, with discriminant D=-4. This congruence with composite modulus has exactly two incongruent solutions because X^2 == -1 (mod 2) has only the solution +1 modulo 2 (odd numbers), and X^2 == -1 (mod p) has (at least one) solution if the Legendre symbol (-1/p) = +1 (i.e., if -1 is a quadratic residue modulo p). Now (-1/p) = (-1)^(p-1)/2 (see, e.g., the Niven-Zuckerman-Montgomery reference given in A001844, Theorem 3.2 (1), p. 132). Hence there is a solution modulo p iff p == 1 (mod 4). Call the smallest positive one X0, with 0 < X0 < p-1. Then one also has the incongruent solution X1 := p-X0. This implies that there are precisely two incongruent solution of the original congruence modulo 2*p for each 1 (mod 4) prime (see, e.g., Nagell's book, pp. 83-4, Theorem 46). If u is a solution for p = A002144(n) (the existence of u has just been proved) then also the companion v := p-1-u satisfies this congruence, and v is incongruent to u modulo p.
Note that x^2 + (x+1)^2 = 4*T(x) + 1, with the triangular numbers A000217.
The primes with x^2 +(x+1)^2 = prime (necessarily from A002144) are found under A027862. The corresponding x values are found under A027861. These x values explain the positions n' where a(n') is smaller than a(n'-1) (for n'>=6): determine k with x=A027861(k), and then n' from A027862(k) = A002144(n'). Note that a(n') = x for such values n'. E.g., n'=6 with a(6)=4: x=4=A027861(3), p=41=A027862(3) = A002144(6). These values n' are n' = 1, 2, 6, 8, 14, 19, 30, ...
All positive solutions of this congruence are provided by the two sequences with entries u(n,k) = a(n) + k*A002144(n) and v(n,k) = A212354(n) + k*A002144(n), n >= 1, k >= 0. For the cases p = 5, 13 and 17 see A047219, A212160 and A212161, respectively, where the even-indexed numbers are the u(n,k) and the odd-indexed ones the v(n,k) (bisection).
FORMULA
a(n) is the smaller of the two smallest positive incongruent solutions of the congruence x^2 + (x+1)^2 = 2*x^2 + 2*x + 1 == 0 (mod A002144(n)), where A002144 lists the primes
1 modulo 4 (primes of the form 4*k+1). For the proof of the existence of a(n) see a comment above. The next larger incongruent companion solution is A212354(n), n >= 1.
EXAMPLE
CROSSREFS
KEYWORD
nonn
AUTHOR
Wolfdieter Lang, May 10 2012
STATUS
approved