A285283 -id:A285283 - cp's OEIS frontend

A175607 Largest number k such that the greatest prime factor of k^2 - 1 is prime(n).

3, 17, 161, 8749, 19601, 246401, 672281, 23718421, 10285001, 354365441, 3222617399, 9447152318, 127855050751, 842277599279, 2218993446251, 2907159732049, 41257182408961, 63774701665793, 25640240468751, 238178082107393, 4573663454608289, 19182937474703818751, 34903240221563713, 332110803172167361, 99913980938200001

Offset: 1

Charles R Greathouse IV, Jul 23 2010

For any prime p, there are finitely many k such that k^2-1 has p as its largest prime factor.
For every prime p, is there some k where the greatest prime factor of k^2-1 is p? Answer from Artur Jasinski, Oct 22 2010: Yes.
As mentioned by Luca and Najman, this problem is closely related to the one in A002071.
The terms give an upper bound with a method for the simultaneous computation of logarithms of small primes, see the fxtbook link. - Joerg Arndt, Jul 03 2012

Charles R Greathouse IV, Table of n, a(n) for n = 1..25
Joerg Arndt, Matters Computational (The Fxtbook), section 32.4, pp.632-633.
Florian Luca and Filip Najman, "On the largest prime factor of x^2-1", Mathematics of Computation 80:273 (2011), pp. 429-435. (Paper has errata that was posted on the MOC website.)
Filip Najman, Home Page (gives all 16223 numbers k such that k^2-1 has no prime factor greater than 97)

Cf. A214093 (largest primes p such that the greatest prime factor of p^2-1 is prime(n)).
Cf. A076605 (largest prime divisor of n^2-1).
Cf. A285283 (equivalent for k^2+1). - Tomohiro Yamada, Apr 22 2017
Cf. A006530, A005563. - M. F. Hasler, Jun 13 2018

/* up to term for p=97 */
/* S[] is the list computed by Filip Najman (16223 elements) */
S=[2,3,4, ... ,332110803172167361, 19182937474703818751];
lpf(n)={ vecmax(factor(n)[, 1]) } /* largest prime factor */
{ forprime (p=2, 97,
  t = 0;
  for (n=1,#S, if ( lpf(S[n]^2-1)==p, t=n ) );
  print1(S[t],", ");
);}
/* Joerg Arndt, Jul 03 2012 */

More terms (using Filip Najman's list) by Joerg Arndt, Jul 03 2012

A002071 Number of pairs of consecutive integers x, x+1 such that all prime factors of both x and x+1 are at most the n-th prime.

Original entry on oeis.org

1, 4, 10, 23, 40, 68, 108, 167, 241, 345, 482, 653, 869, 1153, 1502, 1930, 2454, 3106, 3896

Offset: 1

N. J. A. Sloane

Størmer's theorem proves that a(n) is finite. - Charles R Greathouse IV, Feb 19 2013
Also: Number of positive integers x such that x(x+1) is prime(n)-smooth. - M. F. Hasler, Jan 16 2015
Also: Row lengths of A138180; partial sums of A145604. - M. F. Hasler, Jan 16 2015
On an effective abc conjecture (c < rad(abc)^2), we have that a(20)-a(33) is (4839, 6040, 7441, 9179, 11134, 13374, 16167, 19507, 23367, 27949, 33233, 39283, 46166, 54150). - Lucas A. Brown, Oct 16 2022

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Lucas A. Brown, stormer.py.
E. F. Ecklund and R. B. Eggleton, Prime factors of consecutive integers, Amer. Math. Monthly, 79 (1972), 1082-1089.
D. Eppstein, Smooth pairs.
D. Eppstein, Python program
D. H. Lehmer, On a problem of Størmer, Ill. J. Math., 8 (1964), 57-69.
C. Stormer, Quelques théorèmes sur l'équation de Pell x^2 - Dy^2 = +-1 et leurs applications, Skrifter Videnskabs-selskabet (Christiania), Mat.-Naturv (1897). Kl. I (2).
Wikipedia, Størmer's theorem
OEIS Index entries for sequences related to the abc conjecture

Cf. A002072, A145604, A145605, A145606.
Cf. A138180 (triangle of x values for each n).
Cf. A085152, A085153.
Cf. A285283 (equivalent for x^2 + 1). - Tomohiro Yamada, Apr 22 2017

(* This program needs x maxima taken from A002072. *) xMaxima = A002072;
smoothNumbers[p_, max_] := Module[{a, aa, k, pp, iter}, k = PrimePi[p]; aa = Array[a, k]; pp = Prime[Range[k]]; iter = Table[{a[j], 0, PowerExpand @ Log[pp[[j]], max/Times @@ (Take[pp, j-1]^Take[aa, j-1])]}, {j, 1, k}]; Table[Times @@ (pp^aa), Sequence @@ iter // Evaluate] // Flatten // Sort]; a[n_] := Module[{sn, cnt}, sn = smoothNumbers[Prime[n], xMaxima[[n]]+1]; cnt = 0; Do[If[sn[[i]]+1 == sn[[i+1]], cnt++], {i, 1, Length[sn]-1}]; cnt]; Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 1, 16}] (* Jean-François Alcover, Nov 10 2016 *)
A002072 = {1, 8, 80, 4374, 9800, 123200, 336140, 11859210, 11859210};
Table[Length[Select[Table[Max[FactorInteger[x], FactorInteger[x + 1]], {x, A002072[[n]]}], # <= Prime[n] &]], {n, 7}] (* Robert Price, Oct 29 2018 *)

A002071(n)=[1,4,10,23,40,68,108,167,241,345,482,653,869,1153,1502][n] \\ "practical" solution. - M. F. Hasler, Jan 16 2015

A002071(n,b=A002072,c=1,p=prime(n))={for(k=2,b(n),vecmax(factor(k++,p)[,1])<=p && vecmax(factor(k--+(k<2),p)[,1])<=p && c++); c} \\ b can be any upper bound for A002072, e.g., n->10^n should work, too. - M. F. Hasler, Jan 16 2015

a(n) <= (2^n-1)*(prime(n)+1)/2 is implicit in Lehmer 1964. - Charles R Greathouse IV, Feb 19 2013

Better description and more terms from David Eppstein, Mar 23 2007
a(16) from Jean-François Alcover, Nov 10 2016
a(17)-a(18) from Lucas A. Brown, Aug 23 2020
a(19) from Lucas A. Brown, Oct 16 2022

A223702 Irregular triangle of numbers k such that A002313(n), the n-th prime not congruent to 3 mod 4 is the largest prime factor of k^2 + 1.

Original entry on oeis.org

1, 2, 3, 7, 5, 8, 18, 57, 239, 4, 13, 21, 38, 47, 268, 12, 17, 41, 70, 99, 157, 307, 6, 31, 43, 68, 117, 191, 302, 327, 882, 18543, 9, 32, 73, 132, 278, 378, 829, 993, 2943, 23, 30, 83, 182, 242, 401, 447, 606, 931, 1143, 1772, 6118, 34208, 44179, 85353, 485298

Offset: 1

T. D. Noe, Apr 03 2013

Note that primes of the form 4x+3 are not divisors.

			Irregular triangle:
   p | {k}
-----+---------------------------------
   2 | {1},
   5 | {2, 3, 7},
  13 | {5, 8, 18, 57, 239},
  17 | {4, 13, 21, 38, 47, 268},
  29 | {12, 17, 41, 70, 99, 157, 307},
  37 | {6, 31, 43, 68, 117, 191, 302, 327, 882, 18543},
  41 | {9, 32, 73, 132, 278, 378, 829, 993, 2943}
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..811 (first 22 rows for primes up to 197)
Florian Luca, Primitive divisors of Lucas sequences and prime factors of x^2 + 1 and x^4 + 1, Acta Academiae Paedagogicae Agriensis, Sectio Mathematicae 31 (2004), pp. 19-24.
Filip Najman, Smooth values of some quadratic polynomials, Glasnik Matematicki Series III 45 (2010), pp. 347-355
Filip Najman, List of Publications Page (Adjacent to entry number 7 are links with a data file for the first 22 rows (=811 terms) of this sequence). [As of Dec 2024, the link has the incorrect URL. Should be https://web.math.pmf.unizg.hr/~fnajman/rezplus1.html]

Cf. A002313, A014442, A177979 (first terms), A185389 (last terms), A223705, A285283, A379346 (row lengths), A379347 (row sums).
Cf. A285282, A285523.
Cf. A223701, A223703, A223704 (related tables).

t = Table[FactorInteger[n^2 + 1][[-1,1]], {n, 10^5}]; Table[Flatten[Position[t, Prime[n]]], {n, 13}]

Definition amended by Andrew Howroyd, Dec 22 2024

A379346 Number of integers of the form k^2 + 1 whose greatest prime factor is A002313(n), the n-th prime not congruent to 3 mod 4.

Original entry on oeis.org

1, 3, 5, 6, 7, 10, 9, 16, 17, 20, 26, 36, 36, 40, 46, 47, 56, 67, 73, 86, 97, 107

Offset: 1

Andrew Howroyd, Dec 22 2024

See A223702 for additional information.

Florian Luca, Primitive divisors of Lucas sequences and prime factors of x^2 + 1 and x^4 + 1, Acta Academiae Paedagogicae Agriensis, Sectio Mathematicae 31 (2004), pp. 19-24.
Filip Najman, Smooth values of some quadratic polynomials, Glasnik Matematicki Series III 45 (2010), pp. 347-355.

Row lengths of A223702.
First differences of A285283.
Cf. A002313, A177979, A185389.

A285523 Numbers n such that n^2 + 1 is 100-smooth.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 17, 18, 21, 22, 23, 27, 30, 31, 32, 34, 38, 41, 43, 46, 47, 50, 55, 57, 68, 70, 72, 73, 75, 83, 99, 117, 119, 123, 132, 133, 157, 172, 173, 182, 191, 216, 233, 239, 242, 255, 265, 268, 278, 302, 307, 319, 327, 378, 401, 411, 438, 447

Offset: 1

Tomohiro Yamada, Apr 22 2017

Equivalently: Numbers n such that all prime factors of n^2 + 1 are <= 97.
Since an odd prime factor of n^2 + 1 must be of the form 4m + 1, n^2 + 1 must be of the form 2^t*5^a*13^b*17^c*29^d*37^e*41^f*53^g*61^h*73^i*89^j*97^k, with t = 0 or 1.
Luca determined all terms.

			157^2 + 1 = 2*5^2*17*29 so 157 is a term.

Tomohiro Yamada, Table of n, a(n) for n = 1..156
D. H. Lehmer, On a problem of Størmer, Ill. J. Math., 8 (1964), 57--69.
Florian Luca, Primitive divisors of Lucas sequences and prime factors of x^2 + 1 and x^4 + 1, Acta Academiae Paedagogicae Agriensis, Sectio Mathematicae 31 (2004), pp. 19--24.
Filip Najman, Smooth values of some quadratic polynomials, Glas. Mat. 45 (2010), 347--355. Tables are available in the author's Home Page (gives all 811 numbers n such that n^2 + 1 has no prime factor greater than 197).
A. Schinzel, On two theorems of Gelfond and some of their applications, Acta Arithmetica 13 (1967-1968), 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 Nr. 2 (1897), 48 pp.

Cf. A285282 (n^2 + 1 is 13-smooth), A285283.

isok(n) = vecmax(factor(n^2+1)[,1]) <= 100; \\ Michel Marcus, Apr 23 2017

cp's OEIS Frontend

A175607 Largest number k such that the greatest prime factor of k^2 - 1 is prime(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

A002071 Number of pairs of consecutive integers x, x+1 such that all prime factors of both x and x+1 are at most the n-th prime.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A223702 Irregular triangle of numbers k such that A002313(n), the n-th prime not congruent to 3 mod 4 is the largest prime factor of k^2 + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A379346 Number of integers of the form k^2 + 1 whose greatest prime factor is A002313(n), the n-th prime not congruent to 3 mod 4.

Views

Author

Keywords

Comments

Links

Crossrefs

A285523 Numbers n such that n^2 + 1 is 100-smooth.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI