login
Primes of form 8n+1, that is, primes congruent to 1 mod 8.
(Formerly M5037)
100

%I M5037 #113 Oct 09 2024 04:33:18

%S 17,41,73,89,97,113,137,193,233,241,257,281,313,337,353,401,409,433,

%T 449,457,521,569,577,593,601,617,641,673,761,769,809,857,881,929,937,

%U 953,977,1009,1033,1049,1097,1129,1153,1193,1201,1217,1249,1289,1297,1321,1361

%N Primes of form 8n+1, that is, primes congruent to 1 mod 8.

%C Discriminant is 32, class is 2. Binary quadratic forms ax^2 + bxy + cy^2 have discriminant d = b^2 - 4ac and gcd(a, b, c) = 1.

%C Integers n (n > 9) of form 4k + 1 such that binomial(n-1, (n-1)/4) == 1 (mod n) - _Benoit Cloitre_, Feb 07 2004

%C Primes of the form x^2 + 8y^2. - _T. D. Noe_, May 07 2005

%C Also primes of the form x^2 + 16y^2. See A140633. - _T. D. Noe_, May 19 2008

%C Is this the same sequence as A141174?

%C Being a subset of A001132 and also a subset of A038873, this is also a subset of the primes of the form u^2 - 2v^2. - _Tito Piezas III_, Dec 28 2008

%C These primes p are only which possess the property: for every integer m from interval [0, p) with the Hamming distance D(m, p) = 2, there exists an integer h from (m, p) with D(m, h) = 2. - _Vladimir Shevelev_, Apr 18 2012

%C Primes p such that p XOR 6 = p + 6. - _Brad Clardy_, Jul 22 2012

%C Odd primes p such that -1 is a 4th power mod p. - _Eric M. Schmidt_, Mar 27 2014

%C There are infinitely many primes of this form. See Brubaker link. - _Alonso del Arte_, Jan 12 2017

%C These primes split in Z[sqrt(2)]. For example, 17 = (-1)(1 - 3*sqrt(2))(1 + 3*sqrt(2)). This is also true of primes of the form 8n - 1. - _Alonso del Arte_, Jan 26 2017

%D Milton Abramowitz and Irene A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 870.

%D Z. I. Borevich and I. R. Shafarevich, Number Theory.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Ray Chandler, <a href="/A007519/b007519.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from T. D. Noe)

%H Milton Abramowitz and Irene A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

%H Ben Brubaker, <a href="http://math.mit.edu/~brubaker/781hw5sol.pdf">18.781, Fall 2007 Problem Set 5: Solutions to Selected Problems</a>, MIT (2007).

%H Peter Luschny, <a href="https://oeis.org/wiki/User:Peter_Luschny/BinaryQuadraticForms#Implementation">Binary Quadratic Forms</a>

%H Jorma K. Merikoski, Pentti Haukkanen, and Timo Tossavainen, <a href="https://doi.org/10.7546/nntdm.2024.30.3.516-529">The congruence x^n = -a^n (mod m): Solvability and related OEIS sequences</a>, Notes. Num. Theor. Disc. Math. (2024) Vol. 30, No. 3, 516-529. See p. 521.

%H N. J. A. Sloane et al., <a href="https://oeis.org/wiki/Binary_Quadratic_Forms_and_OEIS">Binary Quadratic Forms and OEIS</a> (Index to related sequences, programs, references)

%H D. B. Zagier, <a href="https://doi.org/10.1007/978-3-642-61829-1">Zetafunktionen und quadratische Körper</a>, Springer, 1981.

%e a(1) = 17 = 2 * 8 + 1 = (10001)_2. All numbers m from [0, 17) with the Hamming distance D(m, 17) = 2 are 0, 3, 5, 9. For m = 0, we can take h = 3, since 3 is drawn from (0, 17) and D(0, 3) = 2; for m = 3, we can take h = 5, since 5 from (3, 17) and D(3, 5) = 2; for m = 5, we can take h = 6, since 6 from (5, 17) and D(5, 6) = 2; for m = 9, we can take h = 10, since 10 is drawn from (9, 17) and D(9, 10) = 2. - _Vladimir Shevelev_, Apr 18 2012

%t Select[1 + 8 Range@ 170, PrimeQ] (* _Robert G. Wilson v_ *)

%o (PARI) forprime(p=2,1e4,if(p%8==1,print1(p", "))) \\ _Charles R Greathouse IV_, Jun 16 2011

%o (PARI) forprimestep(p=17,10^4,8, print1(p", ")) \\ _Charles R Greathouse IV_, Jul 17 2024

%o (Haskell)

%o a007519 n = a007519_list !! (n-1)

%o a007519_list = filter ((== 1) . a010051) [1,9..]

%o -- _Reinhard Zumkeller_, Mar 06 2012

%o (Magma) [p: p in PrimesUpTo(2000) | p mod 8 eq 1 ]; // _Vincenzo Librandi_, Aug 21 2012

%o (PARI) lista(nn)= my(vpr = []); for (x = 0, nn, y = 0; while ((v = x^2+6*x*y+y^2) < nn, if (isprime(v), if (! vecsearch(vpr, v), vpr = concat(vpr, v); vpr = vecsort(vpr););); y++;);); vpr; \\ _Michel Marcus_, Feb 01 2014

%o (SageMath) # uses[binaryQF]

%o # The function binaryQF is defined in the link 'Binary Quadratic Forms'.

%o Q = binaryQF([1, 4, -4])

%o print(Q.represented_positives(1361, 'prime')) # _Peter Luschny_, Jan 26 2017

%Y Subsequence of A017077 and of A038873.

%Y Cf. A139643. Complement in primes of A154264. Cf. A042987.

%Y Cf. A065091, A002144, A094407, A133870, A142925, A208177, A208178, A076339.

%Y Cf. A038872 (d = 5). A038873 (d = 8). A068228, A141123 (d = 12). A038883 (d = 13). A038889 (d = 17). A141111, A141112 (d = 65).

%Y Cf. also A242663.

%Y For a list of sequences giving numbers and/or primes represented by binary quadratic forms, see the "Binary Quadratic Forms and OEIS" link.

%K nonn,easy

%O 1,1

%A _N. J. A. Sloane_, _Robert G. Wilson v_