A134406 -id:A134406 - cp's OEIS frontend

A144255 Semiprimes of the form k^2+1.

10, 26, 65, 82, 122, 145, 226, 362, 485, 626, 785, 842, 901, 1157, 1226, 1522, 1765, 1937, 2026, 2117, 2305, 2402, 2501, 2602, 2705, 3365, 3482, 3601, 3722, 3845, 4097, 4226, 4762, 5042, 5777, 6085, 6242, 6401, 7226, 7397, 7745, 8465, 9026, 9217, 10001, 10202

Offset: 1

T. D. Noe, Sep 16 2008

Iwaniec proves that there are an infinite number of semiprimes or primes of the form n^2+1. Because n^2+1 is not a square for n>0, all such semiprimes have two distinct prime factors.

Moreover, this implies that one prime factor p of n^2+1 is strictly smaller than n, and therefore also divisor of (the usually much smaller) m^2+1, where m = n % p (binary "mod" operation). - M. F. Hasler, Mar 11 2012

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Henryk Iwaniec, Almost-primes represented by quadratic polynomials, Inventiones Mathematicae 47 (2) (1978), pp. 171-188.

Cf. A001358, A085722, A069987, A193432.

Subsequence of A134406.

IsSemiprime:= func; [s: n in [1..100] | IsSemiprime(s) where s is n^2 + 1]; // Vincenzo Librandi, Sep 22 2012

Select[Table[n^2  + 1, {n, 100}], PrimeOmega[#] == 2&] (* Vincenzo Librandi, Sep 22 2012 *)

select(n->bigomega(n)==2,vector(500,n,n^2+1)) \\ Zak Seidov Feb 24 2011

from sympy import primeomega
from itertools import count, takewhile
def aupto(limit):
    form = takewhile(lambda x: x <= limit, (k**2+1 for k in count(1)))
    return [number for number in form if primeomega(number)==2]
print(aupto(10202)) # Michael S. Branicky, Oct 26 2021

a(n) = A085722(n)^2 + 1.

Equals { n^2+1 | A193432(n)=2 }. - M. F. Hasler, Mar 11 2012

A206400 Number of composites of the form n^2 + 1 between two successive primes of this form.

Original entry on oeis.org

0, 1, 1, 3, 3, 1, 3, 3, 1, 9, 3, 13, 1, 9, 7, 9, 5, 3, 15, 5, 3, 3, 1, 3, 3, 11, 3, 5, 3, 9, 5, 3, 3, 19, 1, 3, 13, 5, 5, 3, 9, 5, 3, 3, 5, 9, 3, 15, 5, 7, 11, 13, 9, 33, 1, 9, 3, 5, 13, 9, 5, 3, 3, 19, 1, 3, 3, 15, 5, 39, 7, 11, 13, 5, 7, 9, 39, 1, 7, 1, 7

Offset: 1

Michel Lagneau, Feb 07 2012

nonn

a(n) is the number of composites of A134406 between A002496(n) and A002496(n+1).

			a(4) = 3 because there exist 3 composite numbers of the form n^2+1 : {50, 65, 82} between A002496(4) = 37 and A002496(5) = 101.

Michel Lagneau, Table of n, a(n) for n = 1..10000

Cf. A002522, A002496, A134406.

i:=0:for n from 2 to 1000 do:x:=n^2+1:if type (x,prime)=true then printf(`%d, `,i):i:=0:else i:=i+1:fi:od:

cfn2[{a_,b_}]:=Count[Range[a+1,b-1],?(IntegerQ[Sqrt[#-1]]&)]; cfn2/@ Partition[ Select[Prime[Range[50000]],IntegerQ[Sqrt[#-1]]&],2,1] (* _Harvey P. Dale, Jan 13 2019 *)

c=0; for(n=2,1e9, !ispseudoprime(n^2+1) & c++ & next; print1(c","); c=0) \\ M. F. Hasler, Feb 07 2012

A137351 Composite numbers n such that x^2 - n*y^2 represents -1.

Original entry on oeis.org

10, 26, 50, 58, 65, 74, 82, 85, 106, 122, 125, 130, 145, 170, 185, 202, 218, 226, 250, 265, 274, 290, 298, 314, 325, 338, 346, 362, 365, 370, 394, 425, 442, 445, 458, 481, 485, 493, 530, 533, 538, 554, 565, 586, 610, 626, 629, 634, 685, 697, 698, 730, 746

Offset: 1

N. J. A. Sloane, Apr 08 2008

nonn

Number of terms less than or equal to 10^k for k=0 .. : 0, 1, 8, 71, 712, 6702, 63485, 602870, ... . - Robert G. Wilson v, Jul 20 2008

			3^2 - 10*1^2 = -1, so 10 is a member.
4005^2 - 106*389^2 = -1, so 106 is a member.

Robert G. Wilson v, Table of n, a(n) for n = 1..63485
J. P. Robertson and K. R. Matthews, A continued fraction approach to a result of Feit, Amer. Math. Monthly, 115 (No. 4, 2008), 346-349.
Eric Weisstein's World of Mathematics, Pell Equation.

For the primes with this property see A002313. A134406 is a subset.

lst = {}; Do[ If[ !PrimeQ@ n && FindInstance[x^2 - n*y^2 == -1, {x, y}, Integers] != {}, AppendTo[lst, n]], {n, 2, 1000}]

More terms from Robert G. Wilson v, Jul 20 2008

A211175 Triangle read by rows: row n gives, in increasing order, the prime divisors of all the composites of the form k^2 + 1 between the two primes A002496(n) and A002496(n+1).

Original entry on oeis.org

2, 5, 2, 13, 2, 5, 13, 41, 2, 5, 17, 29, 61, 2, 113, 2, 5, 13, 29, 181, 2, 5, 13, 17, 53, 97, 2, 313, 2, 5, 13, 17, 37, 41, 53, 73, 89, 109, 157, 421, 613, 2, 5, 17, 137, 761, 2, 5, 13, 17, 29, 37, 41, 61, 73, 149, 281, 353, 461, 541, 1013, 1201, 1301, 2, 17

Offset: 2

Michel Lagneau, Feb 01 2013

A variety of conjecturally infinite subsequences and starting with {2, 5, ...} can be shown in the graph of the sequence. If the number of primes of the form n^2 + 1 is finite, then the last subsubsequence of the graph abruptly becomes A002144(n) union {2} (odd Pythagorean primes with the number 2). In this case, the discontinued forms of the graph disappear. But this case is highly improbable.

			The irregular triangle of divisors is:
[2, 5]
[2, 13]
[2, 5, 13, 41]
[2, 5, 17, 29, 61]
[2, 113]
[2, 5, 13, 17, 53, 97]
...
Row 1 is empty because there are no numbers of the form k^2 + 1 between A002496(1) = 2 and A002496(2) = 5.
row 2 = [2, 5] lists divisors of 3^2 + 1 between the primes A002496(2) and A002496(3);
row 3 = [2, 13] lists divisors of 5^2 + 1 between the primes A002496(3) and A002496(4);
row 4 = [2, 5, 13, 41] lists divisors of 7^2 + 1, 8^2 + 1, 9^2 + 1 between the primes A002496(4) and A002496(5).

Michel Lagneau, Rows n = 2..557 of irregular triangle, flattened

Cf. A002144, A002496, A002522, A134406, A181413, A206400.

with(numtheory) :lst:={}: for n from 2 to 150 do:p:=n^2+1:x:=factorset(p):lst:=lst union x:if type(p,prime)=true then print(lst minus {p}):lst:={}:else fi:od:

A211188 a(n) is the number of distinct prime divisors among all the composites of the form k^2 + 1 between the two primes A002496(n) and A002496(n+1).

Original entry on oeis.org

0, 2, 2, 4, 5, 2, 5, 6, 2, 13, 5, 17, 3, 12, 11, 15, 9, 6, 21, 11, 6, 7, 3, 7, 7, 18, 7, 10, 6, 14, 11, 7, 6, 29, 2, 6, 22, 10, 10, 6, 16, 12, 6, 5, 11, 15, 6, 24, 12, 13, 19, 21, 15, 45, 3, 17, 6, 11, 24, 15, 9, 9, 6, 28, 3, 7, 7, 26, 10, 55, 14, 21, 24, 8

Offset: 1

Michel Lagneau, Feb 03 2013

nonn

a(1)=0; for n > 1, a(n) = number of elements of each row in A211175(n).

Michel Lagneau, Table of n, a(n) for n = 1..10000

Cf. A002144, A002496, A002522, A134406, A181413, A206400, A211175.

with(numtheory) :lst:={}: for n from 2 to 600 do:p:=n^2+1:x:=factorset(p):lst:=lst union x:if type(p,prime)=true then m:=nops(lst minus {p}): printf(`%d, `,m):lst:={}:else fi:od:

A233418 a(n) is the smallest number k > 0 such that k^2+1, (k+1)^2+1,...,(k+n)^2+1 are composite numbers.

Original entry on oeis.org

1, 3, 8, 7, 32, 31, 30, 29, 28, 27, 44, 43, 42, 41, 96, 95, 188, 187, 186, 185, 364, 363, 362, 361, 360, 359, 358, 357, 356, 355, 354, 353, 352, 351, 502, 501, 500, 499, 498, 497, 3396, 3395, 3394, 3393, 3392, 3391, 3578, 3577, 3576, 3575, 3574, 3573, 3572

Offset: 0

Michel Lagneau, Dec 09 2013

nonn

			a(0) = 1 because  1^2+1 is prime.
a(1) = 3 because  3^2+1 is composite, but 4^2+1 is prime.
a(2) = 8 because  8^2+1, 9^2+1 are composites, but 10^2+1 is prime.
a(3) = 7 because  7^2+1, 8^2+1 and 9^2+1 are composites, but 10^2+1 is prime.

Michel Lagneau, Table of n, a(n) for n = 0..325

Cf. A002496, A002522, A134406.

for n from 0 to 60 do: ii:=0:for k from 1 to 10^8 while(ii=0) do:i:=0:for m from 0 to n while(type((k+m)^2+1,prime)=false ) do :i:=i+1:od:if i=n then ii:=1: printf(`%d, `,k):else fi:od:od:

nn = 50; t = Table[0, {nn}]; cnt = 0; k = 0; While[cnt < nn, k++; i = 0; While[! PrimeQ[(k + i)^2 + 1], i++]; If[i < nn && t[[i + 1]] == 0, t[[i + 1]] = k; cnt++]]; t (* T. D. Noe, Dec 10 2013 *)

A180507 Numbers k such that k^2 + 1 = p*q, p and q prime with p == q (mod k).

Original entry on oeis.org

3, 8, 12, 144, 1020, 8040, 13860, 34840, 729180, 1728240, 3232060, 17576520, 39279240, 85184880, 117649980, 778689840, 884737920, 1225045140, 1771563420, 3723878100, 3869896140, 4574299320, 7762395960, 12487172640, 14348911860, 14886940920, 21484957560, 24137574780

Offset: 1

Michel Lagneau, Jan 20 2011

nonn

q - p = k with k = 3, 8, 144.

The next terms with q - p = k are F(432) = 85738...5984 and F(570) where F(n) is the n-th Fibonacci number. All such terms are in A001906; the next such term, if one exists, has more than 25000 decimal digits. - Charles R Greathouse IV, Jan 21 2011

			a(3) = 12 because 12^2 + 1 = 5*29 and 29 - 5 = 2*12;
a(8) = 34840 because 34840^2 + 1 = 4289 * 283009 and 283009 - 4289 = 278720 = 8*34840.

Jinyuan Wang, Table of n, a(n) for n = 1..10000

Subset of A085722.

Cf. A001906, A002496, A005574, A027862, A134406, A134407.

with(numtheory):for k from 1 to 40000 do: x:=k^2+1:y:=factorset(x):yy:=bigomega(x):if
  yy=2 and irem(y[2],k) =y[1] then printf(`%d, `,k):else fi:od:

w(m, r) = Vec(x*(1-x)/(1-(m^2+2)*x+x^2) + O(x^r));
isok(s, t) = isprime(s) && isprime(s+t);
lista(nn) = {my(g, k, m=1, r, u=w(1, nn), v=List([])); for(i=2, r=#u, g=k=(u[i]+sqrtint(5*u[i]^2-4))/2; if(isok(u[i], k), listput(v, k))); while(r>2, u=w(m++, r); for(i=2, #u, k=(m*u[i]+sqrtint((m^2+4)*u[i]^2-4))/2; if(kJinyuan Wang, Mar 29 2020

More terms from Charles R Greathouse IV, Jan 24 2011

Missing terms inserted and more terms from Jinyuan Wang, Mar 30 2020

A187401 Numbers k such that k^2 + 1 = p*q, p and q primes and |p-q| is square.

Original entry on oeis.org

30, 100, 144, 274, 484, 516, 526, 756, 1046, 1250, 1714, 1806, 1834, 2284, 2440, 2610, 2940, 3524, 3824, 4190, 5084, 5746, 6766, 7486, 9746, 9920, 10310, 13024, 13210, 15396, 16916, 17546, 18726, 19256, 20000, 21194, 23214, 24964, 30370, 30394, 31126, 31496, 35180, 36680, 37816

Offset: 1

Michel Lagneau, Mar 09 2011

nonn

Note that if k^2+1 = p*q, then p+q cannot be a square. Proof by contradiction. There are two cases: p an odd prime and p=2. Case 1: suppose p and q are odd primes and q = y^2-p. Note that y must be an even number in order for q to be odd. Then p(y^2-p) = x^2+1 for some even x. Rearranging terms, we obtain p*y^2-1 = p^2+x^2. Looking at this equation modulo 4, we obtain -1 = 1, a contradiction. Case 2: Let p=2. Then we obtain 2y^2-x^2 = 5, which has no solutions in integers. - T. D. Noe, Mar 10 2011

			20000 is in the sequence because 20000^2+1 = 19801 * 20201 and 20201 - 19801 = 20^2.

Robert Israel, Table of n, a(n) for n = 1..600

Cf. A134406, A134407, A002522, A005574.

with(numtheory):nn:=50000:for i from 1 to nn do: n:=i^2+1:x:=factorset(n):x1:=nops(x):x2:=bigomega(n):if  x1=2 and x2=2 then z:=x[2]-x[1] :w:=sqrt(z):if w= floor(w) then printf(`%d,  `, i):else fi:else fi :od:
# Alternative:
N:= 500: # to get a(1) to a(N)
count:= 0:
for k from 2 by 2 while count < N do
  f:= ifactors(k^2+1)[2];
  if nops(f) = 2 and {f[1,2],f[2,2]}={1} and issqr(abs(f[1,1]-f[2,1])) then
    count:= count+1;
    A[count]:= k;
  fi
od:
seq(A[i],i=1..count); # Robert Israel, Jun 09 2014

okQ[k_] := Module[{ff = FactorInteger[k^2+1]}, Length[ff] == 2 && ff[[All, 2]] == {1, 1} && IntegerQ[Sqrt[ff[[2, 1]] - ff[[1, 1]]]]];
Select[Range[2, 40000, 2], okQ] (* Jean-François Alcover, Jun 25 2019 *)

A = []
for k in range(2, 2000, 2):
    K = k^2 + 1
    f = prime_divisors(K)
    if len(f) == 2:
        if mul(f) == K:
            if is_square(abs(f[0]-f[1])):
                A.append(k)
print(A) # Peter Luschny, Jun 10 2014

A211189 Number of prime divisors formed by {2} and the consecutive Pythagorean primes for all the composites k^2 + 1 between the two primes A002496(n) and A002496(n+1).

Original entry on oeis.org

0, 2, 1, 3, 2, 1, 3, 4, 1, 4, 2, 7, 1, 4, 7, 6, 4, 2, 6, 4, 2, 4, 1, 2, 2, 4, 4, 3, 2, 5, 4, 3, 2, 10, 1, 2, 7, 4, 2, 3, 5, 4, 2, 2, 4, 5, 3, 4, 6, 5, 4, 7, 4, 7, 1, 5, 3, 2, 7, 5, 3, 4, 2, 8, 1, 2, 4, 7, 2, 9, 5, 4, 12, 2, 4, 6, 10, 1, 4, 1, 2, 9, 2, 5, 2, 4

Offset: 1

Michel Lagneau, Feb 03 2013

a(1)=0; for n > 1, a(n) = number of consecutive elements of the form {2, A002144(1), A002144(2), ...} of each row in A211175(n).
The immediate objective of this sequence is to show that it is difficult to obtain a large range of consecutive Pythagorean primes from the decomposition of n^2 + 1, because the growth of a(n) is very slow, for example a(351) = 29, a(22215) = 34, ...
These considerations confirm the opinion of the truthfulness of the conjecture about an infinity of primes of the form n^2 + 1. This sequence gives the length of a variety of conjecturally infinite subsequences of consecutive primes starting with {2, 5, ...}. If the number of primes of the form n^2 + 1 were finite, there should exist a last prime p such that this sequence stops abruptly from p because the length of A002144(n) is infinite. In this case, we should observe a contradictory behavior of this sequence between the stability of the slow growth of a(n) and the discontinuity from the prime p. But this case is highly improbable.

			a(8) = 4 because the set formed by the union of the prime divisors of all the numbers k^2+1 between the primes A002496(8) = 401 and A002496(9) = 577 are {2, 5, 13, 17, 53, 97} and the subset {2} union {5, 13, 17} contains 4 consecutive elements, hence 4 is in the sequence.

Michel Lagneau, Table of n, a(n) for n = 1..10000

Cf. A002144, A002496, A002522, A134406, A181413, A206400, A211175, A211188.

with(numtheory) :lst:={2}:lst1:={}:
     for k from 1 to 1000 do: q:=4*k+1:
          if type(q,prime)=true then
          lst:=lst union {q}:else fi:
     od:
  L:=subsop(lst):
        for n from 2 to 1000 do:p:=n^2+1:x:=factorset(p):lst1:=lst1 union x:
          if type(p,prime)=true then
          z:=lst1 minus {p}: n1:=nops(z): jj:=0: d0:=0:
            for j from 1 to n1 while(jj=0) do:
               d:=nops(z intersect L[1..j]): if d>d0 then
              d0:=d:
              else
              jj:=1:fi:
            od:
            lst1:={}: printf(`%d, `,d0):
           fi:
          od:

A238947 Numbers k such that k^2 + 1 = p*q, p < q primes and q-p is a power of 2.

Original entry on oeis.org

8, 100, 3524, 5084, 36680, 77980, 21474824, 134201344, 148647496, 300741464, 73851531256, 153122539756, 778318386944, 6669171349484, 16526971109344, 596403262068016, 9376599920124524, 26698166963373164, 140144514160214876, 1613032378604451500

Offset: 1

Michel Lagneau, Mar 07 2014

Note that if n^2+1 = p*q, then p+q cannot be a power of 2. Proof by contradiction: There are two cases: p an odd prime and p=2. Case 1: suppose p and q are odd primes and q = 2^m-p. Then p(2^m-p) = n^2+1 for some even n. Rearranging terms, we obtain p*2^m-1 = p^2+n^2. Looking at this equation modulo 4, we obtain -1 = 1, a contradiction. Case 2: Let p=2. Then we obtain 2^(m+1)-n^2 = 5, which has no solutions in integers.

			8^2+1 = 65 = 5*13 and 13-5 = 2^3;
100^2+1 = 10001 = 73*137 and 137-73 = 2^6;
3524^2+1 = 12418577 = 3049*4073 and 4073-3049 = 2^10.

Giovanni Resta, Some terms greater than a(20)

Cf. A134406, A134407, A002522.

Subsequence of A085722.

with(numtheory):for a from 1 to 200000 do:p:=ithprime(a):for i from 1 to 50 do:q:=p+2^i:if type(q,prime)=true then x:=sqrt(p*q-1):if x=floor(x) then print(x):else fi:fi:od:od:

Select[Range[10^5],!PrimeQ[#^2+1]&&Plus@@Last/@FactorInteger[#^2+1]==2&&PrimeNu[#^2+1]==2&&IntegerQ[Log[2,FactorInteger[#^2+1][[2]][[1]]-FactorInteger[#^2+1][[1]][[1]]]]&]

isok(n) = (bigomega(n^2+1) == 2) && (f = factor(n^2+1)) && ((f[2, 1] - f[1, 1])== 2^(valuation(f[2, 1] - f[1, 1], 2))); \\ Michel Marcus, Mar 07 2014

a(7)-a(20) from Giovanni Resta, Mar 07 2014

cp's OEIS Frontend

A144255 Semiprimes of the form k^2+1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Formula

A206400 Number of composites of the form n^2 + 1 between two successive primes of this form.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A137351 Composite numbers n such that x^2 - n*y^2 represents -1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A211175 Triangle read by rows: row n gives, in increasing order, the prime divisors of all the composites of the form k^2 + 1 between the two primes A002496(n) and A002496(n+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A211188 a(n) is the number of distinct prime divisors among all the composites of the form k^2 + 1 between the two primes A002496(n) and A002496(n+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

A233418 a(n) is the smallest number k > 0 such that k^2+1, (k+1)^2+1,...,(k+n)^2+1 are composite numbers.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A180507 Numbers k such that k^2 + 1 = p*q, p and q prime with p == q (mod k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Extensions

A187401 Numbers k such that k^2 + 1 = p*q, p and q primes and |p-q| is square.

Views