Displaying 1-10 of 47 results found.
Number of 8k+3 primes ( A007520) in range [2^n,2^(n+1)].
+20
3
1, 0, 1, 1, 2, 3, 7, 10, 20, 35, 66, 113, 218, 412, 746, 1460, 2672, 5104, 9651, 18375, 35105, 67165, 128410, 246453, 473535, 911489, 1756670, 3390856, 6552449, 12673142, 24546849, 47583904, 92330578, 179317889, 348548185, 678029708, 1319939685, 2571409639
Let p = n-th prime == 3 mod 8 ( A007520); a(n) = smallest prime q such that p is not a square mod q.
+20
3
3, 3, 7, 5, 3, 5, 3, 3, 3, 7, 5, 3, 11, 3, 3, 5, 5, 13, 3, 13, 3, 3, 3, 3, 13, 5, 5, 3, 11, 3, 7, 5, 3, 3, 7, 11, 5, 7, 3, 7, 5, 5, 3, 3, 3, 11, 3, 5, 3, 19, 3, 3, 3, 7, 3, 3, 3, 7, 5, 3, 3, 7, 3, 11, 3, 5, 3, 7, 5, 5, 3, 3, 5, 3, 3, 3, 5, 3, 17, 3, 5, 3, 7, 13, 5, 3, 11, 3, 3, 5, 7, 3, 3, 5, 3, 7, 3, 7, 5, 3
MATHEMATICA
f[n_] := Block[{k = 2}, While[ JacobiSymbol[n, Prime[k]] == 1, k++ ]; Prime[k]]; f /@ Select[ Prime[ Range[435]], Mod[ #, 8] == 3 &]
Smallest prime p == 3 mod 8 ( A007520) and p > prime(n+2) such that p is a quadratic residue mod the first n odd primes 3, 5, 7, 11, ..., prime(n+1), and p is a quadratic non-residue mod prime(n+2).
+20
2
11, 43, 19, 211, 331, 2011, 1171, 7459, 10651, 18379, 90931, 257371, 399499, 1234531, 6938779, 3574411, 14669251, 39803611, 102808099, 288710899, 322503091, 465390979, 1582819291, 2410622971, 505313251
COMMENTS
Same as smallest prime p == 3 mod 8 with the property that the Legendre symbol (p|q) = 1 for the first n odd primes q = prime(k+1), k = 1, 2, ..., n, and (p|q) = -1 for q = prime(n+2).
MATHEMATICA
f[n_] := Block[{k = 2}, While[ JacobiSymbol[n, Prime[k]] == 1, k++ ]; Prime[k]]; t = Table[0, {50}]; Do[p = Prime[n]; If[Mod[p, 8] == 3, a = f[p]; If[ t[[ PrimePi[a]]] == 0, t[[ PrimePi[a]]] = p; Print[ PrimePi[a], " = ", p]]], {n, 10^9}]; t
1, 5, 9, 21, 29, 33, 41, 53, 65, 69, 81, 89, 105, 113, 125, 141, 153, 165, 173, 189, 209, 221, 233, 245, 249, 261, 273, 281, 285, 293, 309, 321, 329, 341, 345, 369, 393, 405, 413, 429, 441, 453, 473, 485, 509, 525, 545, 561, 581, 585, 593
17, 3, 5, 7, 41, 11, 13, 23, 73, 19, 29, 31, 89, 43, 37, 47, 97, 59, 53, 71, 113, 67, 61, 79, 137, 83, 101, 103, 193, 107, 109, 127, 233, 131, 149, 151, 241, 139, 157, 167, 257, 163, 173, 191, 281, 179, 181, 199, 313, 211, 197, 223, 337, 227, 229, 239, 353, 251, 269
COMMENTS
Or, read the following table by columns:
17,41,73,89,97,113,137,193,233,241,257,281,313,337,353,401,409,... (primes = = 1 mod 8)
3,11,19,43,59,67,83,107,131,139,163,179,211,227,251,283,307,331,... (primes == 3 mod 8)
5,13,29,37,53,61,101,109,149,157,173,181,197,229,269,277,293,317,... (primes == 5 mod 8)
7,23,31,47,71,79,103,127,151,167,191,199,223,239,263,271,311,359,... (primes == 7 mod 8)
EXAMPLE
The first four primes congruent to (1,3,5,7) mod 8 are 17,3,5,7, hence a(1..4)=17,3,5,7;
The next four primes congruent to (1,3,5,7) mod 8 are 41,11,13,23, hence a(5..8)=41,11,13,23, etc.
MATHEMATICA
s[i_]:=(c=0; a=2*i-1; Reap[Do[If[PrimeQ[a], c++; Sow[a]]; If[c>99, Break[], a = a+8], {10^8}]][[2, 1]]); Flatten[Transpose[Table[s[i], {i, 4}]]]; (* Zak Seidov, Jan 16 2013 *)
2, 6, 10, 22, 30, 34, 42, 54, 66, 70, 82, 90, 106, 114, 126, 142, 154, 166, 174, 190, 210, 222, 234, 246, 250, 262, 274, 282, 286, 294, 310, 322, 330, 342, 346, 370, 394, 406, 414, 430, 442, 454, 474, 486, 510, 526, 546, 562, 582, 586, 594
1, 9, 17, 41, 57, 65, 81, 105, 129, 137, 161, 177, 209, 225, 249, 281, 305, 329, 345, 377, 417, 441, 465, 489, 497, 521, 545, 561, 569, 585, 617, 641, 657, 681, 689, 737, 785, 809, 825, 857, 881, 905, 945, 969, 1017, 1049, 1089, 1121, 1161, 1169, 1185
PROG
(PARI) isok(n) = isprime(n+2) && (n % 8 == 1) \\ Michel Marcus, Jul 16 2013
Primes of the form x^2 + xy + 2y^2, with x and y nonnegative.
+10
575
2, 11, 23, 37, 43, 53, 71, 79, 107, 109, 127, 137, 149, 151, 163, 193, 197, 211, 233, 239, 263, 281, 317, 331, 337, 373, 389, 401, 421, 431, 443, 463, 487, 491, 499, 541, 547, 557, 569, 599, 613, 617, 641, 653, 659, 673, 683, 739, 743, 751, 757, 809, 821
COMMENTS
Discriminant=-7. Binary quadratic forms ax^2 + bxy + cy^2 have discriminant d = b^2 - 4ac.
Consider sequences of primes produced by forms with -100<d<0, abs(b)<=a<=c and gcd(a,b,c)=1. When b is not zero, then there are two cases to consider: (1) nonnegative x and y, and (2) x and y any integers. These restrictions yield 203 sequences of prime numbers, which are organized by discriminant below.
The Mathematica function QuadPrimes2 is useful for finding the primes less than "lim" represented by the positive definite quadratic form ax^2 + bxy + cy^2 for any a, b and c satisfying a>0, c>0, and discriminant d<0. It does this by examining all x>=0 and y>=0 in the ellipse ax^2 + bxy + cy^2 <= lim. To find the primes generated by positive and negative x and y, compute the union of QuadPrimes2[a,b,c,lim] and QuadPrimes2[a,-b,c,lim]. - T. D. Noe, Sep 01 2009 For other programs see the "Binary Quadratic Forms and OEIS" link.
REFERENCES
David A. Cox, Primes of the Form x^2 + n y^2, Wiley, 1989.
L. E. Dickson, History of the Theory of Numbers, Vol. 3, Chelsea, 1923.
MATHEMATICA
QuadPrimes2[a_, b_, c_, lmt_] := Module[{p, d, lst = {}, xMax, yMax}, d = b^2 - 4a*c; If[a > 0 && c > 0 && d < 0, xMax = Sqrt[lmt/a]*(1+Abs[b]/Floor[Sqrt[-d]])]; Do[ If[ 4c*lmt + d*x^2 >= 0, yMax = ((-b)*x + Sqrt[4c*lmt + d*x^2])/(2c), yMax = 0 ]; Do[p = a*x^2 + b*x*y + c*y^2; If[ PrimeQ[ p] && p <= lmt && !MemberQ[ lst, p], AppendTo[ lst, p]], {y, 0, yMax}], {x, 0, xMax}]; Sort[ lst]];
QuadPrimes2[1, 1, 2, 1000]
(This is a corrected version of the old, incorrect, program QuadPrimes. - N. J. A. Sloane, Jun 15 2014) max = 1000; Table[yy = {y, 1, Floor[Sqrt[8 max - 7 x^2]/4 - x/4]}; Table[ x^2 + x y + 2 y^2, yy // Evaluate], {x, 0, Floor[Sqrt[max]]}] // Flatten // Union // Select[#, PrimeQ]& (* Jean-François Alcover, Oct 04 2018 *)
PROG
(PARI) list(lim)=my(q=Qfb(1, 1, 2), v=List([2])); forprime(p=2, lim, if(vecmin(qfbsolve(q, p))>0, listput(v, p))); Vec(v) \\ Charles R Greathouse IV, Aug 05 2016
CROSSREFS
Discriminants in the range -3 to -100: A007645 (d=-3), A002313 (d=-4), A045373, A106856 (d=-7), A033203 (d=-8), A056874, A106857 (d=-11), A002476 (d=-12), A033212, A106858- A106861 (d=-15), A002144, A002313 (d=-16), A106862- A106863 (d=-19), A033205, A106864- A106865 (d=-20), A106866- A106869 (d=-23), A033199, A084865 (d=-24), A002476, A106870 (d=-27), A033207 (d=-28), A033221, A106871- A106874 (d=-31), A007519, A007520, A106875- A106876 (d=-32), A106877- A106881 (d=-35), A040117, A068228, A106882 (d=-36), A033227, A106883- A106888 (d=-39), A033201, A106889 (d=-40), A106890- A106891 (d=-43), A033209, A106282, A106892- A106893 (d=-44), A033232, A106894- A106900 (d=-47), A068229 (d=-48), A106901- A106904 (d=-51), A033210, A106905- A106906 (d=-52), A033235, A106907- A106913 (d=-55), A033211, A106914- A106917 (d=-56), A106918- A106922 (d=-59), A033212, A106859 (d=-60), A106923- A106930 (d=-63), A007521, A106931 (d=-64), A106932- A106933 (d=-67), A033213, A106934- A106938 (d=-68), A033246, A106939- A106948 (d=-71), A106949- A106950 (d=-72), A033212, A106951- A106952 (d=-75), A033214, A106953- A106955 (d=-76), A033251, A106956- A106962 (d=-79), A047650, A106963- A106965 (d=-80), A106966- A106970 (d=-83), A033215, A102271, A102273, A106971- A106974 (d=-84), A033256, A106975- A106983 (d=-87), A033216, A106984 (d=-88), A106985- A106989 (d=-91), A033217 (d=-92), A033206, A106990- A107001 (d=-95), A107002- A107008 (d=-96), A107009- A107013 (d=-99). For a more comprehensive list of sequences giving numbers and/or primes represented by binary quadratic forms, see the "Binary Quadratic Forms and OEIS" link.
EXTENSIONS
Removed old Mathematica programs - T. D. Noe, Sep 09 2009 Edited (pointed out error in QuadPrimes, added new version of program, checked and extended b-file). - N. J. A. Sloane, Jun 06 2014
Primes of the form 6k-1.
(Formerly M3809)
+10
128
5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, 101, 107, 113, 131, 137, 149, 167, 173, 179, 191, 197, 227, 233, 239, 251, 257, 263, 269, 281, 293, 311, 317, 347, 353, 359, 383, 389, 401, 419, 431, 443, 449, 461, 467, 479, 491, 503, 509, 521, 557, 563, 569, 587
COMMENTS
Also primes p such that p^q - 2 is not prime where q is an odd prime. These numbers cannot be prime because the binomial p^q = (6k-1)^q expands to 6h-1 some h. Then p^q-2 = 6h-1-2 is divisible by 3 thus not prime. - Cino Hilliard, Nov 12 2008 There exists a polygonal number P_s(3) = 3s - 3 = a(n) + 1. These are the only primes p with P_s(k) = p + 1, s >= 3, k >= 3, since P_s(k) - 1 is composite for k > 3. - Ralf Steiner, May 17 2018 A theorem due to Andrzej Mąkowski: every integer greater than 161 is the sum of distinct primes of the form 6k-1. Examples: 162 = 5 + 11 + 17 + 23 + 47 + 59; 163 = 17 + 23 + 29 + 41 + 53. (See Sierpiński and David Wells.)
Except for 2 and 3, all Sophie Germain primes are of the form 6k-1.
Except for 3, all the lesser of twin primes are also of the form 6k-1.
Dirichlet's theorem on arithmetic progressions states that this sequence is infinite. (End)
For all elements of this sequence p=6*k-1, there are no (x,y) positive integers such that k=6*x*y-x+y. - Pedro Caceres, Apr 06 2019
REFERENCES
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 870.
A. Mąkowski, Partitions into unequal primes, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astr. Phys. 8 (1960), 125-126.
Wacław Sierpiński, Elementary Theory of Numbers, p. 144, Warsaw, 1964.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
David Wells, The Penguin Dictionary of Curious and Interesting Numbers, Penguin Books, Revised edition, 1997, p. 127.
LINKS
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
FORMULA
Product_{k>=1} (1 - 1/a(k)^2) = 9* A175646/Pi^2 = 1/1.060548293.... =4/(3* A333240). Product_{k>=1} (1 + 1/a(k)^2) = A334482. Product_{k>=1} (1 - 1/a(k)^3) = A334480. Product_{k>=1} (1 + 1/a(k)^3) = A334479. (End) Legendre symbol (-3, a(n)) = -1 and (-3, A002476(n)) = +1, for n >= 1. For prime 3 one sets (-3, 3) = 0. - Wolfdieter Lang, Mar 03 2021
MAPLE
select(isprime, [seq(6*n-1, n=1..100)]); # Muniru A Asiru, May 19 2018
PROG
(Haskell)
a007528 n = a007528_list !! (n-1)
a007528_list = [x | k <- [0..], let x = 6 * k + 5, a010051' x == 1]
(GAP) Filtered(List([1..100], n->6*n-1), IsPrime); # Muniru A Asiru, May 19 2018
CROSSREFS
Prime sequences A# (k,r) of the form k*n+r with 0 <= r <= k-1 (i.e., primes == r (mod k), or primes p with p mod k = r) and gcd(r,k)=1: A000040 (1,0), A065091 (2,1), A002476 (3,1), A003627 (3,2), A002144 (4,1), A002145 (4,3), A030430 (5,1), A045380 (5,2), A030431 (5,3), A030433 (5,4), A002476 (6,1), this sequence (6,5), A140444 (7,1), A045392 (7,2), A045437 (7,3), A045471 (7,4), A045458 (7,5), A045473 (7,6), A007519 (8,1), A007520 (8,3), A007521 (8,5), A007522 (8,7), A061237 (9,1), A061238 (9,2), A061239 (9,4), A061240 (9,5), A061241 (9,7), A061242 (9,8), A030430 (10,1), A030431 (10,3), A030432 (10,7), A030433 (10,9), A141849 (11,1), A090187 (11,2), A141850 (11,3), A141851 (11,4), A141852 (11,5), A141853 (11,6), A141854 (11,7), A141855 (11,8), A141856 (11,9), A141857 (11,10), A068228 (12,1), A040117 (12,5), A068229 (12,7), A068231 (12,11). Cf. A034694 (smallest prime == 1 (mod n)). Cf. A038700 (smallest prime == n-1 (mod n)). Cf. A038026 (largest possible value of smallest prime == r (mod n)).
Composite numbers k congruent to 5 (mod 8) such that 2^((k-1)/2) mod k = k-1.
+10
22
3277, 29341, 49141, 80581, 88357, 104653, 196093, 314821, 458989, 489997, 800605, 838861, 873181, 1004653, 1251949, 1373653, 1509709, 1678541, 1811573, 1987021, 2269093, 2284453, 2387797, 2746477, 2909197, 3400013, 3429037, 3539101, 3605429, 4360621, 4502485, 5590621, 5599765
COMMENTS
This sequence contains the n mod 8 = 5 pseudoprimes to the following modified Fermat primality criterion:
Conjecture 1: if p is an odd prime congruent to {3,5} (mod 8) then 2^((p-1)/2) mod p = p-1.
This conjecture has been tested to 10^8.
This criterion produces far fewer pseudoprimes than the 2^(n-1) mod n = 1 test and thus has a higher probability of success. The number of pseudoprimes for the two tests up to 10^k are:
10^5 5 26 19.23%
10^6 13 78 16.66%
10^7 40 228 17.54%
There are 40 terms < 10^7. If an additional constraint 3^(n-1) mod n = 1 and 5^(n-1) mod n = 1 is added, only 4 terms remain: (29341, 314821, 873181, 9863461).
Number of terms below 10^k for k = 5..15: 5, 13, 40, 132, 369, 975, 2534, 6592, 17403, 45801, 122473. The corresponding numbers for 2^(n-1) mod n = 1: 26, 78, 228, 637, 1718, 4505, 11645, 29902, 76587, 197455, 513601. - Jens Kruse Andersen, Jul 13 2014 Also composite numbers 2n+1 with n even such that 2n+1 | 2^n+1. - Hilko Koning, Jan 27 2022 Conjecture 1 is true. With p = 2k+1 then 2^k mod (2k+1) == 2k. So 2k+1 | 2k-2^k. Prime numbers 2k+1 == +-3 (mod 8) are the prime numbers such that 2k+1 | 2^k+1 (Comments A007520). A reflection across the x-axis and +1 translation across the y-axis of the graph (2k-2^k) / (2k+1) gives the graph (2^k+1) / (2k+1). So the k values of both 2k+1 | 2k-2^k and 2k+1 | 2^k+1 are identical. - Hilko Koning, Feb 04 2022
MAPLE
for n from 5 to 10^7 by 8 do if 2^((n-1)/2) mod n = n-1 and not isprime(n) then print(n) fi od;
Search completed in 0.021 seconds
|