A006278 -id:A006278 - cp's OEIS frontend

A341678 Irregular triangle read by rows: row n consists of all numbers x such that x^2 + y^2 = A006278(n), with 0 < x < y.

1, 1, 4, 4, 9, 12, 23, 2, 19, 46, 67, 74, 86, 109, 122, 64, 103, 167, 191, 236, 281, 292, 359, 449, 512, 568, 601, 607, 664, 673, 743, 59, 132, 531, 581, 627, 876, 1008, 1284, 1588, 1659, 1723, 2092, 2136, 2317, 2373, 2736, 2757, 2803, 3072, 3164, 3333, 3469, 3704, 3821, 4028, 4077, 4136, 4371, 4596, 4668, 4712, 4851

Offset: 1

Richard Peterson, Feb 17 2021

The n-th row of the triangle is of length 2^(n-1), since a product of n distinct primes congruent to 1 (mod 4) has 2^(n-1) solutions to being the sum of two squares.

			Triangle starts:
1,
1, 4,
4, 9, 12, 23,
2, 19, 46, 67, 74, 86, 109, 122,
64, 103, 167, 191, 236, 281, 292, 359, 449, 512, 568, 601, 607, 664, 673, 743,
...
In the second row, calculations are as follows. 5*13 is the product of the first two primes congruent to 1 (mod 4), and 65 = 1^2 + 8^2 = 4^2 + 7^2, so the second row is 1, 4.

Andrew Howroyd, Table of n, a(n) for n = 1..1023 (rows 1..10)
Eric Weisstein's World of Mathematics, Sum of Squares Function

Cf. A006278, A230710.

Cf. A236381 (1st column).

row(n) = {my(t=1, q=3, v=vector(2^n/2)); for(k=1, n, until(q%4==1, q=nextprime(q+1)); t*=q); q=0; for(k=1, #v, until(issquare(t-q^2), q++); v[k]=q); v; } \\ Jinyuan Wang, Mar 03 2021

A008784 Numbers k such that sqrt(-1) mod k exists; or, numbers that are primitively represented by x^2 + y^2.

Original entry on oeis.org

1, 2, 5, 10, 13, 17, 25, 26, 29, 34, 37, 41, 50, 53, 58, 61, 65, 73, 74, 82, 85, 89, 97, 101, 106, 109, 113, 122, 125, 130, 137, 145, 146, 149, 157, 169, 170, 173, 178, 181, 185, 193, 194, 197, 202, 205, 218, 221, 226, 229, 233, 241, 250, 257, 265, 269, 274, 277, 281, 289

Offset: 1

N. J. A. Sloane, Olivier Gérard

nonn

Numbers whose prime divisors are all congruent to 1 mod 4, with the exception of at most a single factor of 2. - Franklin T. Adams-Watters, Sep 07 2008
In appears that {a(n)} is the set of proper divisors of numbers of the form m^2+1. - Kaloyan Todorov (kaloyan.todorov(AT)gmail.com), Mar 25 2009 [This conjecture is correct. - Franklin T. Adams-Watters, Oct 07 2009]
If a(n) is a term of this sequence, then so too are all of its divisors (Euler). - Ant King, Oct 11 2010
From Richard R. Forberg, Mar 21 2016: (Start)
For a given a(n) > 2, there are 2^k solutions to sqrt(-1) mod n (for some k >= 1), and 2^(k-1) solutions primitively representing a(n) by x^2 + y^2.
Record setting values for the number of solutions (i.e., the next higher k values), occur at values for a(n) given by A006278.
A224450 and A224770 give a(n) values with exactly one and exactly two solutions, respectively, primitively representing integers as x^2 + y^2.
The 2^k different solutions for sqrt(-1) mod n can written as values for j, with j <= n, such that integers r = sqrt(n*j-1). However, the set of j values (listed from smallest to largest) transform into themselves symmetrically (i.e., largest to smallest) when the solutions are written as n-r. When the same 2^k solutions are written as r-j, it is clear that only 2^(k-1) distinct and independent solutions exist. (End)
Lucas uses the fact that there are no multiples of 3 in this sequence to prove that one cannot have an equilateral triangle on the points of a square lattice. - Michel Marcus, Apr 27 2020
For n > 1, terms are precisely the numbers such that there is at least one pair (m,k) where m + k = a(n), and m*k == 1 (mod a(n)), m > 0 and m <= k. - Torlach Rush, Oct 18 2020
A pair (s,t) such that s+t = a(n) and s*t == +1 (mod a(n)) as above is obtained from a square root of -1 (mod a(n)) for s and t = a(n)-s. - Joerg Arndt, Oct 24 2020
The Diophantine equation x^2 + y^2 = z^5 + z with gcd(x, y, z) = 1 has solutions iff z is a term of this sequence. See Gardiner reference, Olympiad links and A340129. - Bernard Schott, Jan 17 2021
Except for 1, numbers of the form a + b + 2*sqrt(a*b - 1) for positive integers a,b such that a*b-1 is a square. - Davide Rotondo, Nov 10 2024

B. C. Berndt & R. A. Rankin, Ramanujan: Letters and Commentary, see p. 176; AMS Providence RI 1995.
J. W. S. Cassels, Rational Quadratic Forms, Cambridge, 1978.
Leonard Eugene Dickson, History of the Theory Of Numbers, Volume II: Diophantine Analysis, Chelsea Publishing Company, 1992, pp.230-242.
A. Gardiner, The Mathematical Olympiad Handbook: An Introduction to Problem Solving, Oxford University Press, 1997, reprinted 2011, Problem 6 pp. 63 and 167-168 (1985).
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, Ch. 20.2-3.

T. D. Noe, Table of n, a(n) for n = 1..1000
J.-P. Allouche and F. M. Dekking, Generalized Beatty sequences and complementary triples, arXiv:1809.03424 [math.NT], 2018.
British Mathematical Olympiad, 1985 - Problem 6.
Édouard Lucas, Théorème sur la géométrie des quinconces, Nouvelles annales de mathématiques : journal des candidats aux écoles polytechnique et normale, Série 2, Tome 17 (1878), p. 129-130.
P. Cho-Ho Lam, Representation of integers using a^2+b^2-dc^2, J. Int. Seq. 18 (2015) 15.8.6, Theorems 2 and 3.
Richard J. Mathar, Construction of Bhaskara pairs, arXiv:1703.01677 [math.NT], 2017.
N. J. A. Sloane et al., Binary Quadratic Forms and OEIS (Index to related sequences, programs, references).
Index to sequences related to Olympiads.

Apart from the first term, a subsequence of A000404.

Cf. A001481, A022544, A020893, A037942, A034023, A057756, A076948, A045673, A004613, A340129, A192450 (complement).

import Data.List.Ordered (union)
a008784 n = a008784_list !! (n-1)
a008784_list = 1 : 2 : union a004613_list (map (* 2) a004613_list)
-- Reinhard Zumkeller, Oct 25 2015

with(numtheory); [seq(mroot(-1,2,p),p=1..300)];

data=Flatten[FindInstance[x^2+y^2==# && 0<=x<=# && 0<=y<=# && GCD[x,y]==1,{x,y},Integers]&/@Range[289],1]; x^2+y^2/.data//Union (* Ant King, Oct 11 2010 *)
Select[Range[289], And @@ (Mod[#, 4] == 1 & ) /@ (fi = FactorInteger[#]; If[fi[[1]] == {2, 1}, Rest[fi[[All, 1]]], fi[[All, 1]]])&] (* Jean-François Alcover, Jul 02 2012, after Franklin T. Adams-Watters *)

is(n)=if(n%2==0,if(n%4,n/=2,return(0)));n==1||vecmax(factor(n)[,1]%4)==1 \\ Charles R Greathouse IV, May 10 2012

list(lim)=my(v=List([1,2]),t); lim\=1; for(x=2,sqrtint(lim-1), t=x^2; for(y=0,min(x-1,sqrtint(lim-t)), if(gcd(x,y)==1, listput(v,t+y^2)))); Set(v) \\ Charles R Greathouse IV, Sep 06 2016

for(n=1,300,if(issquare(Mod(-1, n)),print1(n,", "))); \\ Joerg Arndt, Apr 27 2020

Checked by T. D. Noe, Apr 19 2007

A000089 Number of solutions to x^2 + 1 == 0 (mod n).

Original entry on oeis.org

1, 1, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 2, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 4, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0

Offset: 1

N. J. A. Sloane

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

			G.f. = x + x^2 + 2*x^5 + 2*x^10 + 2*x^13 + 2*x^17 + 2*x^25 + 2*x^26 + 2*x^29 + ...

Michael Baake, "Solution of the coincidence problem in dimensions d <= 4", in R. V. Moody, ed., Mathematics of Long-Range Aperiodic Order, Kluwer, 1997, pp. 9-44.
Goro Shimura, Introduction to the Arithmetic Theory of Automorphic Functions, Princeton, 1971, see p. 25, Eq. (2).

Seiichi Manyama, Table of n, a(n) for n = 1..10000 (terms 1..2000 from T. D. Noe)
Michael Baake, Solution of the coincidence problem in dimensions d <= 4, arxiv:math/0605222 [math.MG] (2006).
Michael Baake and Uwe Grimm, Quasicrystalline combinatorics, 2002.
Harriet Fell, Morris Newman, and Edward Ordman, Tables of genera of groups of linear fractional transformations, J. Res. Nat. Bur. Standards Sect. B 67B 1963 61-68.
Steven R. Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.
John S. Rutherford, Sublattice enumeration. IV. Equivalence classes of plane sublattices by parent Patterson symmetry and colour lattice group type, Acta Cryst. (2009). A65, 156-163. [See Table 4].
N. J. A. Sloane, Transforms
László Tóth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014), Article 14.11.6.

Cf. A031358, A027748, A124010, A000095, A006278 (positions of records), A002654, A093582.

a000089 n = product $ zipWith f (a027748_row n) (a124010_row n) where
   f 2 e = if e == 1 then 1 else 0
   f p _ = if p `mod` 4 == 1 then 2 else 0
-- Reinhard Zumkeller, Mar 24 2012

with(numtheory); A000089 := proc (n) local i, s; if modp(n,4) = 0 then RETURN(0) fi; s := 1; for i in divisors(n) do if isprime(i) and i > 2 then s := s*(1+eval(legendre(-1,i))) fi od; s end: # Gene Ward Smith, May 22 2006

Array[ Function[ n, If[ EvenQ[ n ] || Mod[ n, 3 ]==2, 0, Count[ Array[ Mod[ #^2+1, n ]&, n, 0 ], 0 ] ] ], 84 ]
a[ n_] := If[ n < 1, 0, Length @ Select[ (#^2 + 1)/n & /@ Range[n], IntegerQ]]; (* Michael Somos, Aug 15 2015 *)
a[n_] := a[n] = Product[{p, e} = pe; Which[p<3 && e==1, 1, p==2 && e>1, 0, Mod[p, 4]==1, 2, Mod[p, 4]==3, 0, True, a[p^e]], {pe, FactorInteger[n]}]; Array[a, 105] (* Jean-François Alcover, Oct 18 2018, after David W. Wilson *)

{a(n) = if( n<1, 0, sum( x=0, n-1, (x^2 + 1)%n==0))}; \\ Michael Somos, Mar 24 2012

a(n)=my(o=valuation(n,2),f);if(o>1,0,n>>=o;f=factor(n)[,1]; prod(i=1,#f,kronecker(-1,f[i])+1)) \\ Charles R Greathouse IV, Jul 08 2013

from math import prod
from sympy import primefactors
def A000089(n): return prod(1 if p==2 else 2 if p&3==1 else 0 for p in primefactors(n)) if n&3 else 0 # Chai Wah Wu, Oct 13 2024

a(n) = 0 if 4|n, else a(n) = Product_{ p | N } (1 + Legendre(-1, p) ), where we use the definition that Legendre(-1, 2) = 0, Legendre(-1, p) = 1 if p == 1 mod 4, = -1 if p == 3 mod 4. This is Shimura's definition, which is different from Maple's.
Dirichlet g.f.: (1+2^(-s))*Product (1+p^(-s))/(1-p^(-s)) (p=1 mod 4).
Multiplicative with a(p^e) = 1 if p = 2 and e = 1; 0 if p = 2 and e > 1; 2 if p == 1 (mod 4); 0 if p == 3 (mod 4). - David W. Wilson, Aug 01 2001
a(3*n) = a(4*n) = a(4*n + 3) = 0. a(4*n + 1) = A031358(n). - Michael Somos, Mar 24 2012
Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 3/(2*Pi) = 0.477464... (A093582). - Amiram Eldar, Oct 11 2022

A054994 Numbers of the form q1^b1 * q2^b2 * q3^b3 * q4^b4 * q5^b5 * ... where q1=5, q2=13, q3=17, q4=29, q5=37, ... (A002144) and b1 >= b2 >= b3 >= b4 >= b5 >= ....

Original entry on oeis.org

1, 5, 25, 65, 125, 325, 625, 1105, 1625, 3125, 4225, 5525, 8125, 15625, 21125, 27625, 32045, 40625, 71825, 78125, 105625, 138125, 160225, 203125, 274625, 359125, 390625, 528125, 690625, 801125, 1015625, 1185665, 1221025, 1373125, 1795625

Offset: 1

Bernard Altschuler (Altschuler_B(AT)bls.gov), May 30 2000

This sequence is related to Pythagorean triples regarding the number of hypotenuses which are in a particular number of total Pythagorean triples and a particular number of primitive Pythagorean triples.
Least integer "mod 4 prime signature" values that are the hypotenuse of at least one primitive Pythagorean triple. - Ray Chandler, Aug 26 2004
See A097751 for definition of "mod 4 prime signature"; terms of A097752 with all prime factors of form 4*k+1.
Sequence A006339 (Least hypotenuse of n distinct Pythagorean triangles) is a subset of this sequence. - Ruediger Jehn, Jan 13 2022

			1=5^0, 5=5^1, 25=5^2, 65=5*13, 125=5^3, 325=5^2*13, 625=5^4, etc.

Ray Chandler, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Pythagorean Triple

Subsequence of A097752.

Cf. A002144, A006278, A006339, A071383, A097751, A097752, A097753, A097754, A097755, A097756.

maxTerm = 10^15;(* this limit gives ~ 500 terms *) maxNumberOfExponents = 9;(* this limit has to be increased until the number of reaped terms no longer changes *) bmax = Ceiling[ Log[ maxTerm]/Log[q]]; q = Reap[For[k = 0 ; cnt = 0, cnt <= maxNumberOfExponents, k++, If[PrimeQ[4*k + 1], Sow[4*k + 1]; cnt++]]][[2, 1]]; Clear[b]; b[maxNumberOfExponents + 1] = 0; iter = Sequence @@ Table[{b[k], b[k + 1], bmax[[k]]}, {k, maxNumberOfExponents, 1, -1}]; Reap[ Do[an = Product[q[[k]]^b[k], {k, 1, maxNumberOfExponents}]; If[an <= maxTerm, Print[an]; Sow[an]], Evaluate[iter]]][[2, 1]] // Flatten // Union (* Jean-François Alcover, Jan 18 2013 *)

list(lim)=
{
  my(u=[1], v=List(), w=v, pr, t=1);
  forprime(p=5,,
    if(p%4>1, next);
    t*=p;
    if(t>lim, break);
    listput(w,t)
  );
  for(i=1,#w,
    pr=1;
    for(e=1,logint(lim\=1,w[i]),
      pr*=w[i];
      for(j=1,#u,
        t=pr*u[j];
        if(t>lim, break);
        listput(v,t)
      )
    );
    if(w[i]^2Charles R Greathouse IV, Dec 11 2016

def generate_A054994():
    """generate arbitrarily many elements of the sequence.
    TO_DO is a list of pairs (radius, exponents) where
    "exponents" is a weakly decreasing sequence, and
    radius == prod(prime_4k_plus_1(i)**j for i,j in enumerate(exponents))
    An example entry is (5525, (2, 1, 1)) because 5525 = 5**2 * 13 * 17.
    """
    TO_DO = {(1,())}
    while True:
        radius, exponents = min(TO_DO)
        yield radius #, exponents
        TO_DO.remove((radius, exponents))
        TO_DO.update(successors(radius,exponents))
def successors(radius,exponents):
    # try to increase each exponent by 1 if possible
    for i,e in enumerate(exponents):
        if i==0 or exponents[i-1]>e:
            # can add 1 in position i without violating monotonicity
            yield (radius*prime_4k_plus_1(i), exponents[:i]+(e+1,)+exponents[i+1:])
    if exponents==() or exponents[-1]>0: # add new exponent 1 at the end:
        yield (radius*prime_4k_plus_1(len(exponents)), exponents+(1,))
from sympy import isprime
primes_congruent_1_mod_4 = [5] # will be filled with 5,13,17,29,37,...
def prime_4k_plus_1(i): # the i-th prime that is congruent to 1 mod 4
    while i>=len(primes_congruent_1_mod_4): # generate primes on demand
        n = primes_congruent_1_mod_4[-1]+4
        while not isprime(n): n += 4
        primes_congruent_1_mod_4.append(n)
    return primes_congruent_1_mod_4[i]
for n,radius in enumerate(generate_A054994()):
    if n==34:
        print(radius)
        break # print the first 35 elements
    print(radius, end=", ")
# Günter Rote, Sep 12 2023

Sum_{n>=1} 1/a(n) = Product_{n>=1} 1/(1 - 1/A006278(n)) = 1.2707219403... - Amiram Eldar, Oct 20 2020

More terms from Henry Bottomley, Mar 14 2001

A121940 Product of the first n primes of the form 6k+1.

Original entry on oeis.org

7, 91, 1729, 53599, 1983163, 85276009, 5201836549, 348523048783, 25442182561159, 2009932422331561, 194963444966161417, 20081234831514625951, 2188854596635094228659, 277984533772656967039693, 38639850194399318418517327, 5834617379354297081196116377

Offset: 1

Jonathan Vos Post, Sep 03 2006

For n>1, a(n) is the least positive integer that can be primitively represented as m^2+mn+n^2 with 0<=m<=n and gcd(m,n)=1 in exactly 2^(n-1) ways. - Ray Chandler, Oct 01 2007
From Bernard Schott, Mar 30 2021: (Start)
Also, for n >= 1, a(n) is the smallest positive integer m such that m^2 can be primitively represented as k^2-k*q+q^2 with 1 <= k < q and gcd(k,q)= 1 in exactly 2^n ways. For example (a(1))^2 = 7^2 = 3^2 - 3*8 + 8^2 = 5^2 - 5*8 + 8^2.
It follows that a(n) is the smallest middle side b that appears exactly 2^n times consecutively in the data of A335895, for integer-sided triangles whose angles A < B < C are in arithmetic progression. (End)
Also, a(n) is the smallest largest side c that appears exactly 2^(n-1) times consecutively in the data of A357277 for integer-sided triangles with angles A < B < C = 2*Pi/3 = 120 degrees. - Bernard Schott, Oct 21 2022

			a(4) = 53599 = 7 * 13 * 19 * 31.

Ray Chandler, Table of n, a(n) for n=1..100

Cf. A002476, A002110, A006278, A078586, A335895.

Greedy inverse of A005088.

Rest@FoldList[Times, 1, Select[6 Range[100] + 1, PrimeQ]] (* Ray Chandler, Oct 01 2007 *)

lista(nn) = {my(pr=1, list=List()); forprime(p=1, nn, if ((p%3) == 1, listput(list,pr *= p));); Vec(list);} \\ Michel Marcus, Jul 17 2020

a(n) = Product_{i=1..n} A002476(i).

Extended by Ray Chandler, Oct 01 2007

A102476 Least modulus with 2^n square roots of 1.

Original entry on oeis.org

1, 3, 8, 24, 120, 840, 9240, 120120, 2042040, 38798760, 892371480, 25878772920, 802241960520, 29682952539240, 1217001054108840, 52331045326680120, 2459559130353965640, 130356633908760178920, 7691041400616850556280

Offset: 0

David W. Wilson, Jan 10 2005

The number of square roots of 1 in any modulus is a power of 2.
Another way of expressing the same:  These are also the record setting values of m for the number of solutions to "m*k+1 is a square", for some k, 0<=k<=m. There is 1 solution for a(0)=m=1, and for m = a(n), n>0, there is the first occurrence of 2^n solutions. Compare with A006278.  - Richard R. Forberg, Mar 18 2016
Also a(n) is the least k such that the proportion of squares in a reduced residue system modulo n is 1/2^n, i.e. A046073(k)/A000010(k) = 1/2^n. - Jianing Song, Nov 12 2019
From Jianing Song, Oct 18 2021: (Start)
a(n) is the smallest k such that rank((Z/kZ)*) = n. The rank of a finitely generated group rank(G) is defined to be the size of the minimal generating sets of G. In particular, rank((Z/kZ)*) = 0 if k <= 2 and A046072(k) otherwise.
The number of coprime squares modulo a(n) is given by A046073(a(n)) = A323739(n-1) for n >= 2. (End)

			a(3) = 24 because 24 is the least modulus with 2^3 square roots of 1, namely 1,5,7,11,13,17,19,23.

Harvey P. Dale, Table of n, a(n) for n = 0..351

Cf. A060594, A002110, A006278, A046072, A046073, A272590, A323739.

{1, 3}~Join~Table[4 Product[Prime[k], {k, n}], {n, 17}] (* Michael De Vlieger, Mar 27 2016 *)
nxt[{a_, p_}] := {a*NextPrime[p], NextPrime[p]}; Join[{1,3},NestList[nxt,{8,2},20][[All,1]]] (* or *) Join[{1,3},4*FoldList[ Times, Prime[ Range[ 21]]]](* Harvey P. Dale, Dec 18 2016 *)

a(n) = if(n<=1, [1,3][n+1], 4*factorback(primes(n-1))) \\ Jianing Song, Oct 19 2021, following David A. Corneth's program for A002110

a(n) = 4(prime(n-1))# = 4*A002110(n-1) for n >= 2. Least k with A060594(k) = 2^n.

A078586 a(n) is the product of the first n primes of the form 4k+3.

Original entry on oeis.org

3, 21, 231, 4389, 100947, 3129357, 134562351, 6324430497, 373141399323, 25000473754641, 1775033636579511, 140227657289781369, 11638895555051853627, 1198806242170340923581, 128272267912226478823167, 16290578024852762810542209, 2134065721255711928181029379

Offset: 1

T. D. Noe, Dec 01 2002

a(n)+2 is a prime for n=1,2,3,4,8,10,12,17,19,22,23,53.

Product of first n primes that are also Gaussian primes; product of first n primes that are not of the form x^2+y^2.

T. D. Noe, Table of n, a(n) for n = 1..100

Cf. A002110, A006278, A038347.

Partial products of A002145.

maxN=15; pLst={}; k=0; While[Length[pLst]

a(n)=my(t=1); forprime(p=2,,if(p%4==3, t*=p; if(n--<1,return(t)))) \\ Charles R Greathouse IV, Mar 09 2014

A236381 Smallest value of x such that x^2 + y^2 = P, where P is the product of the first n primes of the form 4k + 1, and 0 < x < y.

Original entry on oeis.org

1, 1, 4, 2, 64, 59, 1342, 1076, 4268, 10739, 64387, 818998, 3226976, 26444853, 53155423, 1175849126, 13396689992, 2368807981, 907313696551, 483703442648, 2835669288809, 98713800566163, 24423236756993, 6054940274199961, 17628259859562384, 128658404383205917, 3865377837569367511

Offset: 1

Colin Barker, Jan 24 2014

nonn

			a(3) = 4 because the solutions to x^2 + y^2 = 5*13*17 are (x,y) = (23,24), (9,32), (4,33), (12,31) of which the smallest value of x is 4.

Cf. A002144, A006278, A236382, A341678.

prd(n) = my(q=3, t=1); for(k=1, n, until(q%4==1, q=nextprime(q+1)); t*=q); t; \\ A006278
a(n) = {my(t=prd(n), q=0); until(issquare(t-q^2), q++); q; } \\ Michel Marcus, Mar 05 2021

a(23)-a(27) from Jinyuan Wang, Apr 30 2025

A185952 Partial products of A002313, the primes that are 1 or 2 (mod 4).

Original entry on oeis.org

2, 10, 130, 2210, 64090, 2371330, 97224530, 5152900090, 314326905490, 22945864100770, 2042181904968530, 198091644781947410, 20007256122976688410, 2180790917404459036690, 246429373666703871145970

Offset: 1

Jonathan Vos Post, Feb 07 2011

Product of the first n primes which are natural primes which are not Gaussian primes. Product of the first n primes congruent to 1 or 2 modulo 4. Product of the first n primes of form x^2+y^2. Product of the first n primes p such that -1 is a square mod p. Factors of primorials (A002110) not divisible by natural primes which are also Gaussian primes.

Essentially twice A006278.

			a(10) = 2 * 5 * 13 * 17 * 29 * 37 * 41 * 53 * 61 * 73 = 22945864100770.

G. C. Greubel, Table of n, a(n) for n = 1..300

Cf. A000040, A002110, A002313, A042963, A103222.

Rest@ FoldList[#1*#2 &, 1, Select[ Prime@ Range@ 30, Mod[#, 4] != 3 &]] (* Robert G. Wilson v *)

pp(v)=my(t=1); vector(#v,i,t*=v[i])
pp(select(n->n%4<3, primes(20))) \\ Charles R Greathouse IV, Apr 21 2015

a(n) = Product_{i=1..n} A002313(i) = 2 * Product_{i=1..n} {p in A000040 but p not in A002145} = Product_{i=1..n} {A000040 intersection A042963}.

Terms corrected by Robert G. Wilson v, Feb 11 2011

A295819 Number of nonnegative solutions to (x,y) = 1 and x^2 + y^2 = n.

Original entry on oeis.org

0, 2, 1, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 2, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 4, 0, 0

Offset: 0

Seiichi Manyama, Nov 28 2017

nonn

			a(1) = 2;
(1,0) = 1 and 1^2 + 0^2 =  1.
(0,1) = 1 and 0^2 + 1^2 =  1.
a(2) = 1;
(1,1) = 1 and 1^2 + 1^2 =  2. ->  1^2 +  1^2 == 1^2 + 1 == 0 mod  2.
a(5) = 2;
(2,1) = 1 and 2^2 + 1^2 =  5. ->  2^2 +  1^2 == 2^2 + 1 == 0 mod  5.
(1,2) = 1 and 1^2 + 2^2 =  5. ->  3^2 +  6^2 == 3^2 + 1 == 0 mod  5.
a(10) = 2;
(3,1) = 1 and 3^2 + 1^2 = 10. ->  3^2 +  1^2 == 3^2 + 1 == 0 mod 10.
(1,3) = 1 and 1^2 + 3^2 = 10. ->  7^2 + 21^2 == 7^2 + 1 == 0 mod 10.
a(13) = 2;
(3,2) = 1 and 3^2 + 2^2 = 13. -> 21^2 + 14^2 == 8^2 + 1 == 0 mod 13.
(2,3) = 1 and 2^2 + 3^2 = 13. -> 18^2 + 27^2 == 5^2 + 1 == 0 mod 13.

Seiichi Manyama, Table of n, a(n) for n = 0..1000

Cf. A006278.
Similar sequences: A000010, A000925, A295820, A295848, A295976.
A000089 is essentially the same sequence.

a[n_] := Sum[j = Sqrt[n - i^2] // Floor; Boole[GCD[i, j] == 1 && i^2 + j^2 == n], {i, 0, Sqrt[n]}];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jul 05 2018, after Andrew Howroyd *)

a(n) = {sum(i=0, sqrtint(n), my(j=sqrtint(n-i^2)); gcd(i,j)==1 && i^2+j^2==n)} \\ Andrew Howroyd, Dec 12 2017

a(n) = A000089(n) for n >= 2.

a(A006278(n)) = 2^n for n >= 1.

cp's OEIS Frontend

A341678 Irregular triangle read by rows: row n consists of all numbers x such that x^2 + y^2 = A006278(n), with 0 < x < y.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A008784 Numbers k such that sqrt(-1) mod k exists; or, numbers that are primitively represented by x^2 + y^2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Extensions

A000089 Number of solutions to x^2 + 1 == 0 (mod n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

A054994 Numbers of the form q1^b1 * q2^b2 * q3^b3 * q4^b4 * q5^b5 * ... where q1=5, q2=13, q3=17, q4=29, q5=37, ... (A002144) and b1 >= b2 >= b3 >= b4 >= b5 >= ....

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A121940 Product of the first n primes of the form 6k+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A102476 Least modulus with 2^n square roots of 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs