A089120 -id:A089120 - 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

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.

A248527 Numbers n such that the smallest prime divisor of n^2+1 is 13.

Original entry on oeis.org

34, 44, 60, 70, 86, 96, 164, 174, 190, 200, 216, 226, 294, 304, 320, 330, 346, 356, 424, 434, 450, 460, 476, 486, 554, 564, 580, 590, 606, 616, 684, 694, 710, 720, 736, 746, 814, 824, 840, 850, 866, 876, 944, 954, 970, 980, 996, 1006, 1074, 1084, 1100, 1110

Offset: 1

Michel Lagneau, Oct 08 2014

nonn

Or numbers n such that the smallest prime divisor of A002522(n) is A002313(3).
a(n) == 8 (mod 26) if n is odd and a(n) == 18 (mod 26) if n is even.
It is interesting to observe that a(n) is given by a linear formula (see the formula below).

			34 is in the sequence because 34^2+1= 13*89.

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

Cf. A002522, A089120, A002313.

[n: n in [2..3000] | PrimeDivisors(n^2+1)[1] eq 13]; // Bruno Berselli, Oct 08 2014

* first program *
with(numtheory):p:=13:
   for n from 1 to 1000 do:
    if factorset(n^2+1)[1] = p then printf(`%d, `, n):
    else
    fi:
   od:
* second program using the formula*
for n from 0 to 100 by 5 do:
   for k from 1 to 3 do:
     x:=8+(k+n)*26:y:=18+(k+n)*26:
     printf(`%d, `,x):printf(`%d, `,y):
   od:
  od:

lst={};Do[If[FactorInteger[n^2+1][[1,1]]==13,AppendTo[lst,n]],{n,2,2000}];lst
p = 13; ps = Select[Range[p - 1], Mod[#, 4] != 3 && PrimeQ[#] &]; Select[Range[1200], Divisible[(nn = #^2 + 1), p] && ! Or @@ Divisible[nn, ps] &] (* Amiram Eldar, Aug 16 2019 *)

isok(n) = factor(n^2+1)[1,1] == 13; \\ Michel Marcus, Oct 08 2014

{a(n)} = {8+(k + m)*26} union {18+(k + m)*26} for m = 0, 5, 10,...,5p,... and k = 1, 2, 3 (values in increasing order).

A248531 Numbers n such that the smallest prime divisor of n^2+1 is 41.

Original entry on oeis.org

50, 114, 196, 214, 296, 624, 706, 770, 870, 934, 1034, 1180, 1280, 1426, 1444, 1590, 1690, 1754, 1836, 1936, 2000, 2164, 2246, 2264, 2346, 2574, 2674, 2756, 2820, 2984, 3066, 3084, 3230, 3330, 3394, 3494, 3576, 3640, 3740, 3886, 3904, 4214, 4296, 4460, 4624

Offset: 1

Michel Lagneau, Oct 08 2014

Or numbers n such that the smallest prime divisor of n^2+1 is A002313(7).

a(n)== 32 or 50 (mod 82).

			50 is in the sequence because 50^2+1= 41*61.

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

Cf. A089120, A002313, A209874, A248527, A248528, A248529, A248530.

[n: n in [2..5000] | PrimeDivisors(n^2+1)[1] eq 41]; // Bruno Berselli, Oct 08 2014

lst={};Do[If[FactorInteger[n^2+1][[1, 1]]==41, AppendTo[lst, n]], {n, 2, 2000}]; lst
Select[Range[5000],FactorInteger[#^2+1][[1,1]]==41&] (* Harvey P. Dale, Aug 15 2017 *)
p = 41; ps = Select[Range[p - 1], Mod[#, 4] != 3 && PrimeQ[#] &]; Select[Range[5000], Divisible[(nn = #^2 + 1), p] && ! Or @@ Divisible[nn, ps] &] (* Amiram Eldar, Aug 16 2019 *)

A248528 Numbers n such that the smallest prime divisor of n^2+1 is 17.

Original entry on oeis.org

4, 30, 64, 106, 140, 166, 234, 276, 310, 336, 344, 370, 404, 446, 480, 506, 514, 540, 574, 650, 676, 744, 786, 820, 846, 854, 880, 914, 956, 990, 1016, 1024, 1050, 1160, 1186, 1194, 1220, 1254, 1296, 1330, 1356, 1364, 1390, 1424, 1466, 1534, 1560, 1636, 1670

Offset: 1

Michel Lagneau, Oct 08 2014

Or numbers n such that the smallest prime divisor of n^2+1 is A002313(4).

a(n)== 4 or 30 (mod 34).

			30 is in the sequence because 30^2+1= 17*53.

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

Cf. A089120, A002313, A248527.

[n: n in [2..2000] | PrimeDivisors(n^2+1)[1] eq 17]; // Bruno Berselli, Oct 08 2014

lst={};Do[If[FactorInteger[n^2+1][[1, 1]]==17, AppendTo[lst, n]], {n, 2, 2000}]; lst
p = 17; ps = Select[Range[p - 1], Mod[#, 4] != 3 && PrimeQ[#] &]; Select[Range[1670], Divisible[(nn = #^2 + 1), p] && ! Or @@ Divisible[nn, ps] &] (* Amiram Eldar, Aug 16 2019 *)

A248549 Numbers n such that the smallest prime divisor of n^2+1 is 61.

Original entry on oeis.org

194, 316, 416, 804, 904, 926, 1026, 1170, 1270, 1414, 1536, 1780, 2024, 2490, 2734, 2856, 3000, 3100, 3244, 3344, 3366, 3610, 3954, 3976, 4320, 4564, 4830, 4930, 5074, 5196, 5540, 5684, 6394, 6416, 6516, 6760, 6904, 7004, 7126, 7270, 7370, 7514, 7614, 7736

Offset: 1

Michel Lagneau, Oct 08 2014

Or numbers n such that the smallest prime divisor of n^2+1 is A002313(9).

a(n)== 50 or 72 (mod 122).

			194 is in the sequence because 194^2+1= 61*617.

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

Cf. A089120, A002313, A209874, A248527-A248531, A248549-A248553.

lst={};Do[If[FactorInteger[n^2+1][[1, 1]]==61, AppendTo[lst, n]], {n, 2, 10000}]; lst
p = 61; ps = Select[Range[p - 1], Mod[#, 4] != 3 && PrimeQ[#] &]; Select[Range[8000], Divisible[(nn = #^2 + 1), p] && ! Or @@ Divisible[nn, ps] &] (* Amiram Eldar, Aug 16 2019 *)

A248553 Numbers n such that the smallest prime divisor of n^2+1 is 101.

Original entry on oeis.org

10, 414, 596, 1000, 1020, 1606, 1626, 2030, 2414, 2434, 2616, 3444, 3626, 3646, 4030, 5040, 5060, 5646, 5666, 6070, 6454, 6474, 6656, 6676, 7060, 7464, 7666, 7686, 8070, 8090, 8474, 8696, 9080, 9504, 10090, 10494, 10696, 10716, 11504, 11706, 12534, 12716, 12736

Offset: 1

Michel Lagneau, Oct 08 2014

Or numbers n such that the smallest prime divisor of n^2+1 is A002313(13).

a(n)== 10 or 192 (mod 202).

			414 is in the sequence because 414^2+1= 101*1697.

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

Cf. A089120, A002313, A209874, A248527-A248531, A248549-A248553.

lst={};Do[If[FactorInteger[n^2+1][[1, 1]]==101, AppendTo[lst, n]], {n, 2, 10000}]; lst
p = 101; ps = Select[Range[p - 1], Mod[#, 4] != 3 && PrimeQ[#] &]; Select[Range[13000], Divisible[(nn = #^2 + 1), p] && ! Or @@ Divisible[nn, ps] &] (* Amiram Eldar, Aug 16 2019 *)
Select[Range[13000],FactorInteger[#^2+1][[1,1]]==101&] (* Harvey P. Dale, Oct 01 2024 *)

A248529 Numbers n such that the smallest prime divisor of n^2+1 is 29.

Original entry on oeis.org

46, 104, 186, 220, 244, 360, 394, 510, 534, 626, 766, 800, 916, 940, 974, 1056, 1090, 1114, 1206, 1264, 1346, 1380, 1404, 1496, 1520, 1554, 1694, 1810, 1844, 1926, 1960, 2076, 2100, 2134, 2216, 2250, 2366, 2390, 2424, 2506, 2564, 2680, 2714, 2796, 2830, 2854

Offset: 1

Michel Lagneau, Oct 08 2014

Or numbers n such that the smallest prime divisor of n^2+1 is A002313(5).

a(n)== 12 or 46 (mod 58).

			46 is in the sequence because 46^2+1= 29*73.

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

Cf. A089120, A002313, A209874, A248527, A248528.

[n: n in [2..3000] | PrimeDivisors(n^2+1)[1] eq 29]; // Bruno Berselli, Oct 08 2014

lst={};Do[If[FactorInteger[n^2+1][[1, 1]]==29, AppendTo[lst, n]], {n, 2, 2000}]; lst
p = 29; ps = Select[Range[p - 1], Mod[#, 4] != 3 && PrimeQ[#] &]; Select[Range[3000], Divisible[(nn = #^2 + 1), p] && ! Or @@ Divisible[nn, ps] &] (* Amiram Eldar, Aug 16 2019 *)
Select[Range[2,3000,2],FactorInteger[#^2+1][[1,1]]==29&] (* or *) Select[ Flatten[ #+{12,46}&/@(58*Range[0,60])],FactorInteger[#^2+1][[1,1]]==29&](* Harvey P. Dale, Jul 01 2022 *)

A248530 Numbers n such that the smallest prime divisor of n^2+1 is 37.

Original entry on oeis.org

6, 80, 154, 290, 364, 376, 524, 586, 660, 734, 894, 1030, 1104, 1116, 1190, 1326, 1400, 1486, 1634, 1770, 1856, 1930, 2004, 2066, 2226, 2300, 2510, 2584, 2596, 2744, 2806, 2880, 2966, 3040, 3114, 3176, 3250, 3324, 3484, 3546, 3620, 3694, 3706, 3780, 3854, 3916

Offset: 1

Michel Lagneau, Oct 08 2014

Or numbers n such that the smallest prime divisor of n^2+1 is A002313(6).

a(n)== 6 or 68 (mod 74).

			80 is in the sequence because 80^2+1= 37*173.

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

Cf. A089120, A002313, A209874, A248527, A248528, A248529.

[n: n in [2..4000] | PrimeDivisors(n^2+1)[1] eq 37]; // Bruno Berselli, Oct 08 2014

lst={};Do[If[FactorInteger[n^2+1][[1, 1]]==37, AppendTo[lst, n]], {n, 2, 4000}]; lst
p = 37; ps = Select[Range[p - 1], Mod[#, 4] != 3 && PrimeQ[#] &]; Select[Range[4000], Divisible[(nn = #^2 + 1), p] && ! Or @@ Divisible[nn, ps] &] (* Amiram Eldar, Aug 16 2019 *)

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)

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

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

A248527 Numbers n such that the smallest prime divisor of n^2+1 is 13.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A248531 Numbers n such that the smallest prime divisor of n^2+1 is 41.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

A248528 Numbers n such that the smallest prime divisor of n^2+1 is 17.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

A248549 Numbers n such that the smallest prime divisor of n^2+1 is 61.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A248553 Numbers n such that the smallest prime divisor of n^2+1 is 101.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A248529 Numbers n such that the smallest prime divisor of n^2+1 is 29.

Views