A144255 -id:A144255 - cp's OEIS frontend

A085722 Numbers k such that k^2 + 1 is a semiprime.

3, 5, 8, 9, 11, 12, 15, 19, 22, 25, 28, 29, 30, 34, 35, 39, 42, 44, 45, 46, 48, 49, 50, 51, 52, 58, 59, 60, 61, 62, 64, 65, 69, 71, 76, 78, 79, 80, 85, 86, 88, 92, 95, 96, 100, 101, 102, 104, 106, 108, 114, 121, 131, 136, 139, 140, 141, 144, 145, 152, 154, 158, 159, 164

Offset: 1

Jason Earls, Jul 20 2003

Corresponding semiprimes k^2+1 are in A144255.

Solutions to the equation: A000005(1+k^2) = 4. - Enrique Pérez Herrero, May 03 2012

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

Cf. A014442, A089120, A144255, A193432.

lst={}; Do[If[Plus@@Last/@FactorInteger[n^2+1]==2, AppendTo[lst,n]], {n,0,200}]; lst (* Vladimir Joseph Stephan Orlovsky, Mar 24 2009 *)
Select[Range[200],PrimeOmega[#^2+1]==2&] (* Harvey P. Dale, Feb 28 2013 *)

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

A085722 = A193432^-1({2}). - M. F. Hasler, Mar 11 2012

A089120 Smallest prime factor of n^2 + 1.

Original entry on oeis.org

2, 5, 2, 17, 2, 37, 2, 5, 2, 101, 2, 5, 2, 197, 2, 257, 2, 5, 2, 401, 2, 5, 2, 577, 2, 677, 2, 5, 2, 17, 2, 5, 2, 13, 2, 1297, 2, 5, 2, 1601, 2, 5, 2, 13, 2, 29, 2, 5, 2, 41, 2, 5, 2, 2917, 2, 3137, 2, 5, 2, 13, 2, 5, 2, 17, 2, 4357, 2, 5, 2, 13, 2, 5, 2, 5477, 2, 53, 2, 5, 2, 37, 2, 5, 2

Offset: 1

Cino Hilliard, Dec 05 2003

This includes A002496, primes that are of the form n^2+1.

Note that a(n) is the smallest prime p such that n^(p+1) == -1 (mod p). - Thomas Ordowski, Nov 08 2019

H. Rademacher, Lectures on Elementary Number Theory, pp. 33-38.

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A002496, A014442, A085722, A144255, A193432.

[Min(PrimeDivisors(n^2+1)):n in [1..100]]; // Marius A. Burtea, Nov 13 2019

Array[FactorInteger[#^2 + 1][[1, 1]] &, {83}] (* Michael De Vlieger, Sep 08 2015 *)

smallasqp1(m) = { for(a=1,m, y=a^2 + 1; f = factor(y); v = component(f,1); v1 = v[length(v)]; print1(v[1]",") ) }

A089120(n)=factor(n^2+1)[1,1]  \\ M. F. Hasler, Mar 11 2012

a(2k+1)=2; a(10k +/- 2)=5, else a(26k +/- 8)=13, else a(34k +/- 4)=17, else a(58k +/- 12)=29, else a(74k +/- 6)=37,... - M. F. Hasler, Mar 11 2012

A089120(n) = 2 if n is odd, else A089120(n) = min { A002144(k) | n = +/- A209874(k) (mod 2*A002144(k)) }.

A134406 Composite numbers of the form k^2 + 1.

Original entry on oeis.org

10, 26, 50, 65, 82, 122, 145, 170, 226, 290, 325, 362, 442, 485, 530, 626, 730, 785, 842, 901, 962, 1025, 1090, 1157, 1226, 1370, 1445, 1522, 1682, 1765, 1850, 1937, 2026, 2117, 2210, 2305, 2402, 2501, 2602, 2705, 2810, 3026, 3250, 3365, 3482, 3601, 3722, 3845

Offset: 1

Jani Melik, Jan 18 2008

nonn

Square roots of these numbers are quadratic irrationals and corresponding chain fraction representations are periodic: sqrt(10) = [3;{2,3}], sqrt(26) = [5;{2,5}], sqrt(50) = [7;{2,7}], ..., where {} is denoted a period (we write {6} == {2,3}).

			10 is a term because 10 = 3^2 + 1 is composite,
26 is a term because 26 = 5^2 + 1 is composite,
50 is a term because 50 = 7^2 + 1 is composite.

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

Cf. A002496, A005574, A134407.

Supersequence of A144255.

ts_fn1:=proc(n) local i,tren,ans; ans:=[ ]: for i from 1 to n do tren := i^(2)+1: if (isprime(tren) = false) then ans:=[ op(ans), tren ]: fi od: RETURN(ans) end: ts_fn1(200);

Select[Range[70]^2+1,!PrimeQ[#]&] (* Harvey P. Dale, Aug 12 2012 *)

for(n=3,99, if(!isprime(t=n^2+1), print1(t", "))) \\ Charles R Greathouse IV, Aug 29 2016

from sympy import isprime
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 not isprime(number)]
print(aupto(3845)) # Michael S. Branicky, Oct 26 2021

a(n) = 1 + A134407(n)^2. - R. J. Mathar, Oct 13 2019

A209874 Least m > 0 such that the prime p=A002313(n+1) divides m^2+1.

Original entry on oeis.org

1, 2, 8, 4, 12, 6, 32, 30, 50, 46, 34, 22, 10, 76, 98, 100, 44, 28, 80, 162, 112, 14, 122, 144, 64, 16, 82, 60, 228, 138, 288, 114, 148, 136, 42, 104, 274, 334, 20, 266, 392, 254, 382, 348, 48, 208, 286, 52, 118, 86, 24, 516, 476, 578, 194, 154, 504, 106, 58, 26, 566, 96, 380, 670, 722, 62, 456, 582, 318, 526, 246, 520, 650, 726, 494, 324

Offset: 0

M. F. Hasler, Mar 11 2012

nonn

This yields the prime factors of numbers of the form N^2+1, cf. formula in A089120: For n=0,1,2,... check whether N = +/- a(n) [mod 2*A002313(n+1)], if so, then A002313(n+1) is a prime factor of N^2+1.
Obviously, p then divides (2kp +/- a(n))^2+1 for all k >=0 ; in particular it will be the least prime factor of such numbers if there is no earlier match.
Alternatively one could deal separately with the case of odd N, for which p=2 divides N^2+1, and even N, for which only Pythagorean primes A002144(n)=A002313(n+1) can be prime factors of N^2+1.

Cf. A002496, A014442, A085722, A144255, A089120, A193432.

Cf. A002314, A177979.

A209874(n)=if( n, 2*lift(sqrt(Mod(-1, A002144[n])/4)), 1)

/* for illustrative purpose: a(n) is the smaller of the 2 possible remainders mod 2*p of numbers N such that N^2+1 has p as smallest prime factor */ forprime( p=1,199, p>2 & p%4 != 1 & next; my(c=[]); for(i=1,9e9, factor(i^2+1)[1,1]==p |next; c=vecsort(concat(c,i%(2*p)),,8); #c==1 || print1(","c[1]) || break))

For n>0, A209874(n) = 2*sqrt(-1/4 mod A002144(n)), where sqrt(a mod p) stands for the positive x < p/2 such that x^2=a in Z/pZ.

A209874(n) = A209877(n)*2 for n>0.

A243449 Primes of the form n^2 + 14.

Original entry on oeis.org

23, 239, 743, 1103, 2039, 5639, 7583, 8663, 27239, 33503, 38039, 42863, 59063, 81239, 88223, 91823, 119039, 131783, 140639, 164039, 189239, 205223, 245039, 263183, 288383, 328343, 342239, 378239, 393143, 400703, 431663, 439583, 514103, 660983, 710663, 950639

Offset: 1

Vincenzo Librandi, Jun 05 2014

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Cf. A121250 (associated n).

Cf. primes of the form n^2+k: A144255 (k=1), A056899 (k=2), A049423 (k=3), A005473 (k=4), A056905 (k=5), A056909 (k=6), A079138 (k=7), A138338 (k=8), A138353 (k=9), A138355 (k=10), A138362 (k=11), A138368 (k=12), A138375 (k=13), this sequence (k=14), A243450 (k=15), A243451 (k=16), A228244 (k=17), A174812 (k=42).

[a: n in [0..1000] | IsPrime(a) where a is n^2+14];

Select[Table[n^2 + 14, {n, 0, 2000}], PrimeQ]
Select[Range[1,1001,2]^2+14,PrimeQ] (* Harvey P. Dale, May 30 2023 *)

A186688 Semiprimes of the form n^4 + 1.

Original entry on oeis.org

82, 626, 2402, 4097, 10001, 14642, 20737, 28562, 38417, 83522, 104977, 194482, 234257, 279842, 456977, 707282, 810001, 1048577, 1500626, 1679617, 2085137, 2313442, 2560001, 3111697, 6250001, 7311617, 10556002, 11316497, 13845842, 14776337, 17850626, 21381377, 25411682

Offset: 1

Michel Lagneau, Feb 25 2011

			4097 is a member because 4097 = 8^4 + 1 = 17*241.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Cf. A144255.

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

semiPrimeQ[n_] := Total[FactorInteger[n]][[2]] == 2; Select[ Range[200]^4
  +1, semiPrimeQ]
Select[Table[n^4 + 1, {n, 80}], PrimeOmega[#] == 2&] (* Vincenzo Librandi, Sep 22 2012 *)

A209877 a(n) = A209874(n)/2: Least m > 0 such that 4*m^2 = -1 modulo the Pythagorean prime A002144(n).

Original entry on oeis.org

1, 4, 2, 6, 3, 16, 15, 25, 23, 17, 11, 5, 38, 49, 50, 22, 14, 40, 81, 56, 7, 61, 72, 32, 8, 41, 30, 114, 69, 144, 57, 74, 68, 21, 52, 137, 167, 10, 133, 196, 127, 191, 174, 24, 104, 143, 26, 59, 43, 12, 258, 238, 289, 97, 77, 252, 53, 29, 13, 283, 48, 190, 335, 361, 31, 228, 291, 159, 263, 123, 260, 325, 363, 247, 162

Offset: 1

M. F. Hasler, Mar 14 2012

nonn

Also: Square root of -1/4 in Z/pZ, for Pythagorean primes p=A002144(n).
Also: Least m>0 such that the Pythagorean prime p=A002144(n) divides 4(kp +/- m)^2+1 for all k>=0.
In practice these can also be determined by searching the least N^2+1 whose least prime factor is p=A002144(n): For given p, all of these N will have a(n) or p-a(n) as remainder mod 2p.

			a(1)=1 since A002144(1)=5 and 4*1^2+1 is divisible by 5; as a consequence 4*(5k+/-1)^2+1 = 100k^2 +/- 40k + 5 is divisible by 5 for all k.
a(2)=4 since A002144(2)=13 and 4*4^2+1 = 65 is divisible by 13, while 4*1^1+1=5, 4*2^2+1=17 and 4*3^2+1=37 are not. As a consequence, 4*(13k+/-4)^2+1 = 13(...)+4*4^1+1 is divisible by 13 for all k.

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

Cf. A209874.
Cf. A002496, A014442, A085722, A144255, A089120, A193432.
Cf. A002314, A177979.

f:= proc(p) local m;
   if not isprime(p) then return NULL fi;
   m:= numtheory:-msqrt(-1/4, p);
   min(m,p-m);
end proc:
map(f, [seq(i,i=5..1000,4)]); # Robert Israel, Mar 13 2018

f[p_] := Module[{r}, r /. Solve[4 r^2 == -1, r, Modulus -> p] // Min];
f /@ Select[4 Range[300] + 1, PrimeQ] (* Jean-François Alcover, Jul 27 2020 *)

apply(p->lift(sqrt(Mod(-1,p)/4)), A002144)

A247340 Numbers n such that each prime divisor of the semiprime n^2+1 is also a divisor of a^2+1 and b^2+1 respectively for some a, b < n.

Original entry on oeis.org

3, 8, 30, 46, 50, 76, 100, 144, 254, 266, 274, 286, 334, 380, 456, 494, 504, 516, 520, 526, 566, 664, 670, 726, 756, 810, 836, 844, 874, 1040, 1064, 1086, 1130, 1164, 1216, 1250, 1300, 1476, 1714, 1740, 1800, 1826, 1834, 1946, 1950, 2014, 2194, 2200, 2220, 2324

Offset: 1

Michel Lagneau, Sep 14 2014

nonn

Or numbers n such that n^2+1 = p*q, p and q primes => p | a^2+1 and q | b^2+1 for some a,b < n.
Subsequence of A085722 and except the first term, a(n) is even.
The squares of the sequence are 100, 144, 3364, 6084, 7396, 10404, 24964, 45796, 47524, 68644, 71824, 93636,...
Observation : a(n) = p*q => there exists a and b such that a^2+1 = m*p and b^2+1 = m*q. (see the examples).

			3^2+1 = 2*5 => 1^1+1 = 2 and 2^2+1 = 5 ;
8^2+1 = 5*13 => 3^2+1 = 2*5 and 5^2+1 = 2*13 ;
30^2+1 = 17*53 => 13^2+1=2*5*17 and 23^2+1 = 2*5*53 ;
46^2+1 = 29*73 => 17^2+1 = 2*5*29 and 27^2+1=2*5*73 ;
50^2+1 = 41*61 => 9^2+1 = 2*41 and 11^2+1 = 2*61 ;
76^2+1 = 53*109 => 23^2+1 = 2*5*53 and 33^2+1 = 2*5*109 ;
100^2+1 = 73*137 => 27^2+1=2*5*73 and 37^2+1 = 2*5*137 ;
144^2+1 = 89*233 => 55^2+1 = 2*17*89 and 89^2+1 = 2*17*233 ;
254^2+1 = 149*433 => 105^2+1 = 2*37*149 and 179^2+1 = 2*37*433 ;
266^2+1 = 173*409 => 93^2+1 = 2*5^2*173 and 143^2+1 = 2*5^2*409.

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

Cf. A085722, A144255.

with(numtheory):lst:={}:
for n from 1 to 3000 do:
   x:=factorset(n^2+1):n0:=nops(x):
     for i from 1 to n0 do:
      lst:=lst union {x[i]}:
     od:
      lst1:={}:nn:=n+1:xx:=factorset(nn^2+1):nn0:=nops(xx):
        for j from 1 to nn0 do:
         lst1:=lst1 union {xx[j]}:
        od:
        if
         nn0=2
         and bigomega(nn^2+1)=2
         and {xx[1],xx[2]} intersect lst = {xx[1],xx[2]}
         then
         printf(`%d, `,n+1):
         else
        fi:
        lst:=lst union lst1:
  od:

A248742 Numbers of the form x^2+1 with at most two prime factors.

Original entry on oeis.org

2, 5, 10, 17, 26, 37, 65, 82, 101, 122, 145, 197, 226, 257, 362, 401, 485, 577, 626, 677, 785, 842, 901, 1157, 1226, 1297, 1522, 1601, 1765, 1937, 2026, 2117, 2305, 2402, 2501, 2602, 2705, 2917, 3137, 3365, 3482, 3601, 3722, 3845, 4097, 4226, 4357, 4762

Offset: 1

R. J. Mathar, Oct 13 2014

nonn

Prime factors are counted with multiplicity, as in A144255.

Iwaniec shows that the sequence is infinite.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
H. Iwaniec, Almost-primes represented by quadratic polynomials, Inventiones Mathematicae 47:2 (1978), pp. 171-188.
Vishaal Kapoor, Almost-primes represented by quadratic polynomials, MS thesis (2006). arXiv:1910.02885 [math.NT]
Robert J. Lemke Oliver, Almost-primes represented by quadratic polynomials, Acta Arithm. 151 (2012) 241. DOI: 10.4064/aa151-3-2
Wikipedia, Landau's problems

Cf. A002496, A069987.

is(n)=issquare(n-1) && bigomega(n)<3 \\ Charles R Greathouse IV, Feb 05 2017

A002496 UNION A144255.

A263876 Numbers n such that n^2 + 1 has two distinct prime divisors less than n.

Original entry on oeis.org

7, 18, 38, 41, 68, 70, 182, 239, 500, 682, 776, 800, 1068, 1710, 1744, 4030, 4060, 5604, 5744, 8119, 12156, 15006, 16610, 17684, 21490, 25294, 26884, 27590, 32060, 32150, 37416, 37520, 45630, 47321, 58724, 71264, 84906, 88526, 98864, 109054, 109610, 128766

Offset: 1

Michel Lagneau, Oct 28 2015

nonn

Subsequence of A256011.

The numbers n such that n^2 + 1 = p*q are semiprimes (A085722) are not in the sequence. According to this property, the corresponding sequence of the number of prime divisors with multiplicity is 3, 3, 3, 3, 4, 3, 5, 5, 3, 5, 3, 3, 7, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 6, ...

			7 is in the sequence because 7^2 + 1 = 2*5^2 => 2 and 5 are less than 7.

Amiram Eldar, Table of n, a(n) for n = 1..500

Cf. A085722, A144255, A256011, A263877.

Select[Range[150000], PrimeNu[#^2+1] == 2&&FactorInteger[#^2+1][[1,1]]<# &&FactorInteger[#^2+1][[2,1]]<#&]

for(n=1, 1e5, t=n^2+1; if ((omega(t) == 2) && (factor(t)[, 1][2] < n), print1(n, ", "))); \\ Altug Alkan, Oct 28 2015

cp's OEIS Frontend

A085722 Numbers k such that k^2 + 1 is a semiprime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A089120 Smallest prime factor of n^2 + 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

A134406 Composite numbers of the form k^2 + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A209874 Least m > 0 such that the prime p=A002313(n+1) divides m^2+1.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

PARI

Formula

A243449 Primes of the form n^2 + 14.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

A186688 Semiprimes of the form n^4 + 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

A209877 a(n) = A209874(n)/2: Least m > 0 such that 4*m^2 = -1 modulo the Pythagorean prime A002144(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica