cp's OEIS Frontend

See the conjecture in the comment at A145047. In addition, I conjecture that for every such s there exist infinitely many primes of the form 4k+1.

The idea of this sequence comes from the 6th problem of the 21st British Mathematical Olympiad in 1985 where it is asked to show that this equation has infinitely many solutions (see link Olympiads and reference Gardiner).

Indeed, this Diophantine equation x^2 + y^2 = z^5 + z with gcd(x, y, z) = 1 has solutions iff z is in A008784.

When z is in A008784, there exist (u, v), gcd(u, v) = 1 such that z = u^2 + v^2; then, (u*z^2-v)^2 + (u+v*z^2)^2 = z^5 + z. Hence, with x = min(u*z^2-v, u+v*z^2) and y = max(u*z^2-v, u+v*z^2), the equation x^2 + y^2 = z^5 + z is satisfied. So this equation has infinitely many solutions since it has at least one solution for each term of A008784.

For instance, for z = 10 we have:

with (u,v) = (1,3), then x = 1*10^2-3 = 97 and y = 1+3*10^2 = 301,

with (u,v) = (3,1), then x = 3+1*10^2 = 103 and y = 3*10^2-1 = 299,

so finally 97^2 + 301^2 = 103^2 + 299^2 = 10^5 + 10.

Note that some z, among them 10, have other solutions not of this form.

The orbit of i under the action of the modular group (that is, the set {(ai+b)/(ci+d): a,b,c,d in Z, ad-bc=1}) is symmetric with respect to the imaginary axis, and periodic with period 1 relative to horizontal translations. So reflecting the orbit in the strip 0<=Re(z)<=1/2 across the imaginary axis and then translating horizontally by integer amounts gives the complete orbit of i in the complex plane.

The orbit in the strip 0<=Re(z)<=1/2 is the union of finite sets, one for each term of A008784, that correspond to the levels of {a(n)}. Each finite set is made of points with rational coordinates on horizontal lines with equation Im(z)=1/N, where N is a term of A008784. Starting at the top with n=1=A008784(1), we have only k=0, or i itself, corresponding to the identity element of the modular group. Then going down one level, at n=2=A008784(2), we have only k=1, or the element 1/2+i/2 corresponding to the modular group element ((1,0),(1,1)). Then at the next level n=3, we have A008784(3)=5, and we still have only one entry k=2, giving 2/5+i/5, corresponding to the matrix ((0,-1),(1,-2)). Continuing this way we find that all levels up to n=16 have only one term of the sequence. This is because if N=A008784(n), then for 1<=n<=16 the equation x^2+y^2=N has only one solution with (x,y) relatively prime. For n=17, we have A008784(17)=65 and (1,8), (4,7) are two solutions of x^2+y^2=65. So we find two terms of the sequence, 8 and 18, at level 17, corresponding to 8/65+i/65 and 18/65+i/65 in the orbit of i, with matrices ((0,-1),(1,-8)) and ((2,1),(7,4)).

So {a(n)} lists the numerators of the real part of the elements of the orbit of i in 0<=Re(z)<=1/2, as we descend the "floors", moving from left to right.

Here is how the sequence is constructed: Each N = A008784(n) can be expressed as the sum of two relatively prime squares. If N has s prime divisors, and all of them are of form 4k+1, then there will be 2^(s-1) solutions of x^2 + y^2 = N (see the MathStackExchange post cited in the Links section).

Consider one such solution, c^2+d^2=N. Let a,b be the unique integers given by the Euclidean algorithm such that ad-bc=1 (or equivalently, the pair of integers (x,y) at minimal distance from the origin such that cx-dy=1). It can be shown that ac+bd will be in {1,2,...,N-1} and relatively prime to N. Let k=min(ac+bd, N-ac-bd). Then k is in {1,2,...,N/2}. Do this for every possible solution of x^2+y^2=N, then list the resulting numbers (all contained in {1,2,3,...,N/2}) in increasing order. These will be the numerators of the rational numbers that are the real part of the points of the orbit of i with imaginary part 1/N. Row n of the triangle is then k1,k2,...,kr and r is the row length, which will always be a power of 2.

The connection with A057756 is as follows: the terms of A057756 are found as the first term of each level of {a(n)} (because A057756 is the numerator of the first rational number on a level of the orbit of i).

Or, primes p such that x^2 - p*y^2 represents -1.

Primes which are not Gaussian primes (meaning not congruent to 3 mod 4).

Every Fibonacci prime (with the exception of F(4) = 3) is in the sequence. If p = 2n+1 is the prime index of the Fibonacci prime, then F(2n+1) = F(n)^2 + F(n+1)^2 is the unique representation of the prime as sum of two squares. - Sven Simon, Nov 30 2003

Except for 2, primes of the form x^2 + 4y^2. See A140633. - T. D. Noe, May 19 2008

Primes p such that for all p > 2, p XOR 2 = p + 2. - Brad Clardy, Oct 25 2011

Greatest prime divisor of r^2 + 1 for some r. - Michel Lagneau, Sep 30 2012

Empirical result: a(n), as a set, compose the prime factors of the family of sequences produced by A005408(j)^2 + A005408(j+k)^2 = (2j+1)^2 + (2j+2k+1)^2, for j >= 0, and a given k >= 1 for each sequence, with the addition of the prime factors of k if not already in a(n). - Richard R. Forberg, Feb 09 2015

Primes such that when r is a primitive root then p-r is also a primitive root. - Emmanuel Vantieghem, Aug 13 2015

Primes of the form (x^2 + y^2)/2. Note that (x^2 + y^2)/2 = ((x+y)/2)^2 + ((x-y)/2)^2 = a^2 + b^2 with x = a + b and y = a - b. More generally, primes of the form (x^2 + y^2) / A001481(n) for every fixed n > 1. - Thomas Ordowski, Jul 03 2016

Numbers n such that ((n-2)!!)^2 == -1 (mod n). - Thomas Ordowski, Jul 25 2016

Primes p such that (p-1)!! == (p-2)!! (mod p). - Thomas Ordowski, Jul 28 2016

The product of 2 different terms (x^2 + y^2)(z^2 + v^2) = (xz + yv)^2 + (xv - yz)^2 is sum of 2 squares (A000404) because (xv - yz)^2 > 0. If x were equal to yz/v then (x^2 + y^2)/(z^2 + v^2) would be equal to ((yz/v)^2 + y^2)/(z^2 + v^2) = y^2/v^2 which is not possible because (x^2 + y^2) and (z^2 + v^2) are prime numbers. For example, (2^2 + 5^2)(4^2 + 9^2) = (2*4 + 5*9)^2 + (2*9 - 5*4)^2. - Jerzy R Borysowicz, Mar 21 2017

Number of elliptic points of order 2 for GAMMA_0(n).

The Dirichlet inverse, 1, -1, 0, 1, -2, 0, 0, -1, 0, 2, 0, 0, -2, 0,.. seems to equal A091400, apart from signs. - R. J. Mathar, Jul 15 2010

Shadow transform of A002522. - Michel Marcus, Jun 06 2013

a(n) != 0 iff n in A008784. - Joerg Arndt, Mar 26 2014

For n > 1, number of positive solutions to n = a^2 + b^2 such that gcd(a, b) = 1. - Haehun Yang, Mar 20 2022

Numbers that are not multiples of 4 and for which all odd prime factors are congruent to +/- 1 mod 8. - Eric M. Schmidt, Apr 20 2013

Apparently the same as the list of numbers primitively represented by the indefinite quadratic form x^2 - 2y^2 (cf. A035251). - N. J. A. Sloane, Jun 11 2014

From Wolfdieter Lang, Jul 11 2025: (Start)

Also the negative sequence lists the numbers properly represented by the indefinite quadratic form x^2 - 2*y^2 of discriminant 4*2 = 8. For the proof see the W. Lang paper linked in A385449, Lemma 18, pp. 22-23.

The connection between the proper positive fundamental solutions (X, Y) of X^2 - 2*Y^2 = -a(n), given in A385449, and the solutions (x, y) of x^2 - 2*y^2 = a(n) is (x, y) = (2*Y - X, X - Y). If y becomes nonpositive a transformation with the matrix Mat([3,4], [2,3]) will give the positive proper fundamental solution. See the example section of A385449. See also the Nov 09 2009 comment in A035251 by Franklin T. Adams-Watters for this connection, and for the matrix eq. (38) p. 14 of the mentioned linked paper.

Therefore the previous statement on the representation of a(n) is true.(End)