A256011 -id:A256011 - cp's OEIS frontend

A014442 Largest prime factor of n^2 + 1.

2, 5, 5, 17, 13, 37, 5, 13, 41, 101, 61, 29, 17, 197, 113, 257, 29, 13, 181, 401, 17, 97, 53, 577, 313, 677, 73, 157, 421, 53, 37, 41, 109, 89, 613, 1297, 137, 17, 761, 1601, 29, 353, 37, 149, 1013, 73, 17, 461, 1201, 61, 1301, 541, 281, 2917, 89, 3137, 13, 673

Offset: 1

Glen Burch (gburch(AT)erols.com)

All a(n) except for a(1) = 2 are the Pythagorean primes, i.e., primes of form 4k+1. Conjecture: every Pythagorean prime appears in a(n) at least once.
Problem 11831 [Ozols 2015] is to prove that lim inf a(n)/n is zero. - Michael Somos, May 11 2015
From Michael Kaltman, Jun 10 2015: (Start)
For all numbers k in A256011, a(k) < k.
Conjecture: every Pythagorean prime p appears exactly two times among the first p integers of the sequence. Further: if a(i) = a(j) = p and both i and j are less than p (and i is not equal to j), then i + j = p and ij == 1 (mod p). [If a(k) = p as well, then k > p; in fact, k is in A256011.] Two examples: a(2) = a(3) = 5, with 2+3 = 5 and 2*3 = 6 == 1 (mod 5); a(4) = a(13) = 17, with 4+13 = 17 and 4*13 = 52 == 1 (mod 17).
(End)
The conjecture is true. If p is a Pythagorean prime, -1 is a quadratic residue mod p. Then -1 has exactly two square roots mod p, i.e., there are exactly two integers x,y with 1 <= x,y <= p-1 such that x^2 == y^2 == -1 (mod p), i.e., p divides x^2+1 and y^2+1, and moreover y == -x (mod p) so x + y = p, and x*y == -x^2 == 1 (mod p). Any other prime factor q of x^2 + 1 must divide (x^2+1)/p, and since x^2+1 < p^2 we have q < p, so a(x) = p and similarly a(y) = p. - Robert Israel, Jun 11 2015
Conjecture: if n is even and a(n) > n, then n+a(n) is in A256011. Examples: 2+a(2) = 2+5 = 7, 4+a(4) = 4+17 = 21, 6+a(6) = 6+37 = 43, and so on. Note that 18+a(18) is NOT in A256011, but 18 itself is. - Michael Kaltman, Jun 13 2015
This is also true. Suppose A = a(n) > n. n^2+1 is odd so A is an odd prime; n^2 + 1 = A *B with B < A also odd. Then (A+n)^2 + 1 = A*(A+2*n+B) and A+2*n+B is even. The largest prime factor of A+2*n+B is thus at most (A+2*n+B)/2 < A + n, while A < A + n as well. - Robert Israel, Jun 17 2015
Størmer shows that a(n) tends to infinity with n. Chowla shows that a(n) >> log log n.  Schinzel shows that lim inf a(n)/log log n >= 4 and, using lower bounds for linear forms of logarithms, this inequality can be generalized for general quadratic polynomials, with 2 replaced by 4/7 for irreducible ones and 2/7 for reducible ones. - Tomohiro Yamada, Apr 15 2017
According to Hooley, an unpublished manuscript of Chebyshev contains the result that a(n)/n is unbounded which was first published and fully proved by Markov. - Charles R Greathouse IV, Oct 27 2018
Note that a(n) is the largest prime p such that n^(p+1) == -1 (mod p). - Thomas Ordowski, Nov 08 2019

A. A. Markov, Über die Primteiler der Zahlen von der Form 1+4x^2, Bulletin de l'Académie impériale des sciences de St.-Pétersbourg 3 (1895), pp. 55-59.
H. Rademacher, Lectures on Elementary Number Theory, pp. 33-38.

T. D. Noe, Table of n, a(n) for n = 1..10000
S. Chowla, The greatest prime factor of x^2 + 1, J. London Math. Soc. 10 (1935), 117--120.
J. M. Deshouillers and H. Iwaniec, On the greatest prime factor of n^2+1, Annales de l'institut Fourier, 32 no. 4 (1982), p. 1-11.
Christopher Hooley, On the greatest prime factor of a quadratic polynomial, Acta Mathematica 117 (1967), pp. 281-299.
Jori Merikoski, Largest prime factor of n^2+1, arXiv:1908.08816 [math.NT], 2019.
R. Ozols, Problem 11831, The American Mathematical Monthly, Vol. 122, No. 4 (April 2015), page 390
A. Schinzel, On two theorems of Gelfond and some of their applications, Acta Arith. 13 (1967), 177--236.
Carl Størmer, Quelques théorèmes sur l'équation de Pell x^2 - Dy^2 = +-1 et leurs applications (in French), Skrifter Videnskabs-selskabet (Christiania), Mat.-Naturv. Kl. I (2), 48 pp.

Includes primes from A002496.
Cf. A002144 (Pythagorean primes: primes of form 4n+1).
Cf. A256011.
Cf. A076605 (largest prime factor of n^2 - 1).

List([1..60],n->Reversed(Factors(n^2+1))[1]); # Muniru A Asiru, Oct 27 2018

[Maximum(PrimeDivisors(n^2+1)): n in [1..60]]; // Vincenzo Librandi, Jun 17 2015

seq(max(numtheory:-factorset(n^2+1)),n=1..100) ; # Robert Israel, Jun 11 2015

Table[FactorInteger[n^2+1,FactorComplete->True][[ -1,1]],{n,5!}] ..and/or.. Table[Last[Table[ #[[1]]]&/@FactorInteger[n^2+1]],{n,5!}] ..and/or.. PrimeFactors[n_]:=Flatten[Table[ #[[1]],{1}]&/@FactorInteger[n]]; Table[PrimeFactors[n^2+1][[ -1]],{n,5!}] (* Vladimir Joseph Stephan Orlovsky, Aug 12 2009 *)
a[ n_] := If[ n < 1, 0, FactorInteger[n n + 1][[All, 1]] // Last]; (* Michael Somos, May 11 2015 *)
Table[FactorInteger[n^2 + 1][[-1, 1]], {n, 80}] (* Vincenzo Librandi, Jun 17 2015 *)

largeasqp1(m) = { for(a=1,m, y=a^2 + 1; f = factor(y); v = component(f,1); v1 = v[length(v)]; print1(v1",") ) } \\ Cino Hilliard, Jun 12 2004

{a(n) = if( n<1, 0, Vecrev(factor(n*n + 1)[,1])[1])}; /* Michael Somos, May 11 2015 */

a(n) = A006530(1+n^2). - R. J. Mathar, Jan 28 2017

A073501 Primes p such that the largest prime factor of p^2+1 is less than p.

Original entry on oeis.org

7, 41, 43, 47, 73, 83, 157, 173, 191, 193, 211, 233, 239, 251, 293, 307, 313, 337, 401, 421, 431, 443, 463, 467, 499, 509, 557, 577, 593, 599, 601, 659, 701, 743, 757, 787, 811, 829, 853, 857, 863, 911, 919, 1087, 1109, 1123, 1223, 1229, 1277, 1297, 1301

Offset: 1

Benoit Cloitre, Aug 27 2002

Primes p such that the largest prime factor of p+1 is less than p gives A065091, odd primes.

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

Cf. A065091, A073501, A256011.

[p:p in PrimesUpTo(1500)|Max(PrimeDivisors(p^2+1)) lt p]; // Marius A. Burtea, Aug 07 2019

filter:= proc(n) max(numtheory:-factorset(n^2+1))Robert Israel, Aug 07 2019

<Ray Chandler, Jan 08 2005 *)
Select[Prime[Range[212]], Max[First /@ FactorInteger[#^2 + 1]] < # &] (* Jayanta Basu, Jul 01 2013 *)

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

A263877 Numbers n such that n^2 + 1 has three distinct prime divisors less than n.

Original entry on oeis.org

21, 43, 57, 72, 99, 111, 117, 119, 128, 132, 142, 172, 174, 185, 192, 193, 200, 211, 212, 216, 251, 268, 294, 305, 322, 336, 338, 342, 351, 360, 378, 394, 408, 418, 431, 443, 448, 450, 460, 485, 498, 509, 515, 524, 552, 560, 562, 568, 580, 601, 606, 612, 616

Offset: 1

Michel Lagneau, Oct 28 2015

nonn

Subsequence of A256011.
The "triprimes n^2+1 numbers" are the numbers that are the product of exactly three (not necessarily distinct) primes less than n.
If the three prime divisors are distinct, the corresponding subsequence is 21, 72, 111, 119, 128, 142, 172, 174, 185, 192, 200, 211, 212, 216, 294, 305, 322, 336, 338, 342, 351, 360, 394, 431, 448, 450, 460, 485, 498, 509, 524, 552, 560, 562, 580, ...
The corresponding sequence of the number of prime divisors with multiplicity is 3, 4, 5, 3, 4, 3, 4, 3, 3, 4, 3, 3, 3, 3, 3, 5, 3, 3, 3, 3, 4, 5, 3, 3, 3, 3, 3, 3, 3, 3, 4, 3, 4, 4, 3, 6, 3, 3, 3, 3, 3, 3, 4, 3, 3, 3, 3, 5, 3, 3, 4, 3, 4, 3, 3, 3, 3, 4, 3, 4, ...

			72 is in the sequence because 72^2 + 1 = 5*17*61 and 5, 17 and 61 are less than 72.

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

Cf. A014612, A256011, A263876.

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

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

A282538 Odd integers n with the property that the largest prime factor of n^2+4 is less than n.

Original entry on oeis.org

11, 29, 49, 59, 99, 111, 121, 127, 141, 161, 179, 199, 205, 211, 213, 219, 237, 247, 261, 283, 289, 309, 311, 335, 359, 369, 387, 393, 411, 417, 419, 433, 441, 469, 479, 485, 521, 523, 527, 535, 569, 581, 595, 603, 611, 619, 621, 633, 643, 679, 691, 705, 711, 715, 723, 729, 739, 741, 749, 759

Offset: 1

Michael Kaltman, Feb 17 2017

nonn

Every Pythagorean prime p can be uniquely written as the sum of two positive integers a and b such that ab is congruent to 1 (mod p). If a>b, then the difference a-b must be an odd number; no number on this list can be said difference, and every positive odd integer NOT on this list is the difference of exactly one pair.

			Examples: 5 is not on this list, and 17-12=5 while 17+12=29 and (17)(12)==1 mod 29.  9 is not on this list, and 13-4=9 while 13+4=17 and (13)(4)==1 mod 17.  13 is not on this list, and 93-80=13 while 93+80=173 and (93)(80)==1 mod 173.  Note that 5^2+4=29, 9^2+4=85=17(5), and 13^2+4=173

Cf. A256011 (generated similarly, but for n^2+1 instead of n^2+4).

fQ[n_] := FactorInteger[n^2 + 4][[-1, 1]] < n; Select[2 Range[380] - 1, fQ] (* Robert G. Wilson v, Feb 17 2017 *)

isok(n) = (n%2) && vecmax(factor(n^2+4)[,1]) < n; \\ Michel Marcus, Feb 18 2017

a(22) onward from Robert G. Wilson v, Feb 17 2017

A309562 Numbers k such that the largest prime divisor of k^4+1 is less than k.

Original entry on oeis.org

1600, 2949, 3370, 8651, 8758, 8777, 9308, 9647, 10181, 10566, 10820, 11518, 12400, 12461, 13360, 13724, 14051, 14273, 14971, 16802, 18073, 18283, 18324, 18979, 22143, 22812, 23343, 23766, 24590, 24780, 25152, 25253, 25313, 25897, 26097, 26659, 27106, 27134, 28523, 28526, 29586, 29588, 30660

Offset: 1

J. M. Bergot and Robert Israel, Aug 07 2019

nonn

To see if some m is a term we don't have to factor m^4 + 1 entirely. All we need to know is if the largest prime factor is less than k = m^4 + 1. - David A. Corneth, Jul 31 2020

			1600 is a member because 1600^4+1=17^2*113*337*641*929 has all its prime divisors < 1600.

David A. Corneth, Table of n, a(n) for n = 1..7762 (first 1000 terms from Robert Israel)

Cf. A102326 (primes in this sequence), A256011.

[k: k in [1..31000]| Max(PrimeDivisors(k^4+1)) lt k]; // Marius A. Burtea, Aug 07 2019

filter := proc(n) max(numtheory:-factorset(n^4 + 1)) < n; end proc:
select(filter, [$1..40000]);

filterQ[k_] := FactorInteger[k^4 + 1][[-1, 1]] < k;
Select[Range[40000], filterQ] (* Jean-François Alcover, Jul 31 2020 *)

is(n) = my(f = factor(n^4 + 1, n + 1)); f[#f~, 1] < n \\ David A. Corneth, Jul 31 2020

A336883 a(n) = ((A002144(n) - 1)/2)! (mod A002144(n)) where A002144(n) is the n-th Pythagorean prime.

Original entry on oeis.org

2, 5, 13, 12, 31, 9, 23, 11, 27, 34, 22, 91, 33, 15, 37, 44, 129, 80, 162, 81, 183, 122, 144, 64, 16, 187, 217, 53, 138, 288, 114, 189, 213, 42, 104, 274, 63, 381, 266, 29, 254, 382, 348, 48, 301, 286, 489, 439, 483, 24, 77, 125, 578, 423, 487, 149, 555, 615, 651, 135, 96, 380, 87, 39, 707

Offset: 1

Hiroyuki Hara, Aug 06 2020

nonn

Let p(n) = A002144(n) be the n-th Pythagorean prime.
Pythagorean prime p can be divided into a pair of integers (a,b) such as p =a+b and a*b==1 mod p. And (p-2)!==1 mod p because of Wilson's Theorem (p-1)!==-1 mod p. It can be divided into two parts (a,b) such as {2*3*4*...*((p(n)-1)/2)==a(n) mod p(n)} and {((p(n)-1)/2+1)*...*(p(n)-4)*(p(n)-3)*(p(n)-2)==-a(n)==(p(n)-a(n)) mod p(n)}. The pair numbers make a(n)+(p(n)-a(n))=p(n) and a(n)*(p(n)-a(n))==1 mod p(n). The left integer of the pair numbers is a(n). The right integer (p(n)-a(n)) is A336884(n).
The set of selecting odd numbers from {a(n)} and A336884 is A206549. The set of selecting even numbers from {a(n)} and A336884 is A209874 except for the number 1. A256011 never appears in {a(n)} or A336884. It is related to nonexistence of numbers that the largest prime factor of n^2+1 is greater than n.
The odd number of the difference |a(n)-A336884(n)|=|a(n)-(p(n)-a(n))|=|2*a(n)-p(n)| is A186814(n). A282538 never appears in the set of the difference |a(n)-A336884(n)|.
If p(n) is unknown, p(n) can be derived from a(n) using following equation. From a*b==1 mod p, a*b=k*p+1. With p=a+b, it can transform to b(n)=(k*a(n)+1)/(a(n)-k), k is an odd integer parameter when the fraction makes an integer. If there are many k's, select the minimum k in those. Then a(n)+b(n)=p(n). b(n) is A336884(n).

			p(1)=5: (5-2)!=2*3=a(1)*(5-a(1))==1 mod 5. 5=2+3.
p(2)=13: (13-2)!=(2*3*4*5*6)*(7*8*9*10*11)=(2*3*4*5*6)*((p-6)*(p-5)*(p-4)*(p-3)*(p-2))==5*(-5)==5*(13-5)=5*8==a(2)*(13-a(2))==1 mod 13. 13=5+8.
a(n)=13: b(n)=(k*13+1)/(13-k)=(3*13+1)/(13-3)=4, k=3. p(n)=13+4=17.
a(n)=12: b(n)=(k*12+1)/(12-k)=(7*12+1)/(12-7)=17, k=7. p(n)=12+17=29.

Hiroyuki Hara, Table of n, a(n) for n = 1..4783 [reformatted and restored by _Georg Fischer_, Oct 15 2020]

Cf. A336884, A002144 (Pythagorean primes), A206549, A209874, A256011, A186814, A282538.

Map[Mod[((# - 1)/2)!, #] &, Select[4 Range[192] + 1, PrimeQ]] (* Michael De Vlieger, Oct 15 2020 *)

my(v=select(p->p%4==1, primes(100))); apply(x->(((x-1)/2)! % x), v) \\ Michel Marcus, Aug 07 2020

n_start=5
n_end=n_start+10000
k = 1
for n in range(n_start, n_end, 4):
    c=(n-1)//2
    r=1
    for i in range(2, c+1):
        r=r*i % n
        if r==0:
            break
    if (n-r)*r % n ==1:
        print(k, r)
        k = k + 1
# modified by Georg Fischer, Oct 16 2020

A336884 a(n) = A002144(n) - A336883(n) where A002144(n) is the n-th Pythagorean prime.

Original entry on oeis.org

3, 8, 4, 17, 6, 32, 30, 50, 46, 55, 75, 10, 76, 98, 100, 105, 28, 93, 19, 112, 14, 107, 89, 177, 241, 82, 60, 228, 155, 25, 203, 148, 136, 311, 269, 115, 334, 20, 143, 392, 179, 67, 109, 413, 208, 235, 52, 118, 86, 553, 516, 476, 35, 194, 154, 504, 106, 58, 26, 566, 613, 353, 670, 722

Offset: 1

Hiroyuki Hara, Aug 06 2020

nonn

For more information see A336883.

			p(1)=5: (5-2)!=2*3=A336883(1)*a(1)==1 mod 5. 5=2+3.
p(2)=13: (13-2)!=(2*3*4*5*6)*(7*8*9*10*11)=(2*3*4*5*6)*((p-6)*(p-5)*(p-4)*(p-3)*(p-2))==5*(-5)==5*(13-5)=5*8==A336883(2)*a(2)==1 mod 13. 13=5+8.
a(n)=4: A336883(n)=(k*4+1)/(4-k)=(3*4+1)/(4-3)=13, k=3. p(n)=13+4=17.
a(n)=17: A336883(n)=(k*17+1)/(17-k)=(7*17+1)/(17-7)=12, k=7. p(n)=12+17=29.

Hiroyuki Hara, Table of n, a(n) for n = 1..4783 [reformatted and restored by _Georg Fischer_, Oct 16 2020]

Cf. A336883, A002144 (Pythagorean primes), A206549, A209874, A256011, A186814, A282538.

v = Select[Prime[Range[1000]], Mod[#, 4] == 1&];
v - Mod[((v-1)/2)!, v] (* Jean-François Alcover, Oct 24 2020, after PARI *)

my(v=select(p->p%4==1, primes(100))); apply(x->x - (((x-1)/2)! % x), v) \\ Michel Marcus, Aug 07 2020

n_start=5
n_end=n_start+100000
k=1
for n in range(n_start, n_end, 4):
    c=(n-1)//2
    r=1
    for i in range(2, c+1):
        r=r*i % n
        if r==0:
            break
    if (n-r)*r % n ==1:
        print(k, n-r)
        k = k + 1
# modified by Georg Fischer, Oct 16 2020

a(n) == (A002144(n) - 2)!/((A002144(n) - 1)/2)! == -((A002144(n) - 1)/2)! == -A336883(n) == A002144(n) - A336883(n) mod A002144(n).

cp's OEIS Frontend

A014442 Largest prime factor of n^2 + 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

PARI

Formula

A073501 Primes p such that the largest prime factor of p^2+1 is less than p.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A263877 Numbers n such that n^2 + 1 has three distinct prime divisors less than n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A282538 Odd integers n with the property that the largest prime factor of n^2+4 is less than n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Extensions

A309562 Numbers k such that the largest prime divisor of k^4+1 is less than k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

A336883 a(n) = ((A002144(n) - 1)/2)! (mod A002144(n)) where A002144(n) is the n-th Pythagorean prime.

Views

Author

Keywords

Comments

Examples