A175607 -id:A175607 - cp's OEIS frontend

A076605 Largest prime divisor of n^2 - 1.

3, 2, 5, 3, 7, 3, 7, 5, 11, 5, 13, 7, 13, 7, 17, 3, 19, 5, 19, 11, 23, 11, 23, 13, 5, 13, 29, 7, 31, 5, 31, 17, 11, 17, 37, 19, 37, 19, 41, 7, 43, 11, 43, 23, 47, 23, 47, 5, 17, 13, 53, 13, 53, 7, 19, 29, 59, 29, 61, 31, 61, 31, 13, 11, 67, 17, 67, 17, 71, 7

Offset: 2

Jon Perry, Oct 21 2002

nonn

Also the largest prime that divides either n-1 or n+1.

Størmer shows that a(n) tends to infinity with n. Schinzel shows that lim inf a(n)/log log n >= 2 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

			n=11: the largest prime factor of 10 and 12 is 5, therefore a(11) = 5.

K. Mahler, "Uber den grossten Primteiler spezieller Polynome zweiten Grades", Arch. Math. Naturvid. B.41, 1935, pp. 3 - 26.

T. D. Noe, Table of n, a(n) for n = 2..10000
D. H. Lehmer, On a problem of Størmer, Ill. J. Math., 8 (1964), 57-79.
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 udgivne af Videnskabsselskabet i Christiania: Mathematisk-naturvidenskabelig Klasse, 2 (1897), 48 pp.

Cf. A006530, A037464, A074399 (bisections).
Cf. A175607.
Cf. A014442 (largest prime divisor of n^2 + 1). - Tomohiro Yamada, Apr 15 2017

Table[ Last[ Table[ # [[1]]] & /@ FactorInteger[n^2 - 1]], {n, 2, 80}]

for (n=3,100, print1(","max(factor(n-1)[,1][length(factor(n-1)[,1])],factor(n+1)[,1][length(factor(n+1)[,1])])))

A181447 Numbers k such that 3 is the largest prime factor of k^2 - 1.

Original entry on oeis.org

2, 5, 7, 17

Offset: 1

Artur Jasinski, Oct 21 2010

Sequence is finite and complete, for proof see A175607.

Search for terms can be restricted to the range from 2 to A175607(2) = 17; primepi(3) = 2.

Cf. A175607, A181448-A181470, A181568.

[ n: n in [2..20] | m eq 3 where m is D[#D] where D is PrimeDivisors(n^2-1) ]; // Klaus Brockhaus, Feb 17 2011

Select[Range[20], FactorInteger[#^2-1][[-1, 1]]==3&]

is(n)=n=n^2-1;my(o=valuation(n,3)); o && n>>valuation(n/3^o,2)==1 \\ Charles R Greathouse IV, Jul 01 2013

A181470 Numbers n such that 97 is the largest prime factor of n^2 - 1.

Original entry on oeis.org

96, 98, 193, 195, 290, 389, 484, 581, 583, 775, 872, 874, 969, 971, 1066, 1163, 1165, 1359, 1456, 1551, 1553, 1648, 1747, 1844, 1939, 2036, 2133, 2135, 2232, 2521, 2715, 2911, 3008, 3103, 3299, 3394, 3396, 3590, 3976, 4267, 4269, 4463, 4558, 4946, 5045

Offset: 1

Artur Jasinski, Oct 21 2010

Sequence is finite, for proof see A175607.

Search for terms can be restricted to the range from 2 to A175607(25) = 99913980938200001; primepi(97) = 25.

Lucas A. Brown, Table of n, a(n) for n = 1..2734 (2679 terms from Artur Jasinski, 55 missing terms from Lucas A. Brown, complete subject to the effective abc conjecture c < rad(abc)^2)
From _David A. Corneth_, Oct 03 2022: (Start)
To verify full I listed all 97-smooth numbers k that are a multiple of 97 below (inclusive) A175607(25) + 2. I then checked if k+2 is 97-smooth. If so, k+1 is a term. Then similarily I checked if k-2 is 97-smooth. If so, k-1 is a term.
Doing so found the 2734 terms from the b-file. All candidates have been checked completing the proof of full. (End)

Cf. A175607, A181447-A181469, A181568.

[ n: n in [2..300000] | m eq 97 where m is D[#D] where D is PrimeDivisors(n^2-1) ]; // Klaus Brockhaus, Feb 21 2011

p:=(97*89*83*79*73*71)^5 *(67*61*59*53*47*43*41)^6 *(37*31*29)^7 *(23*19*17)^8 *13^9 *11^10 *7^13 *5^15 *3^23 *2^36; [ n: n in [2..50000000] | p mod (n^2-1) eq 0 and (D[#D] eq 97 where D is PrimeDivisors(n^2-1)) ]; // Klaus Brockhaus, Feb 21 2011

jj = 2^36 * 3^23 * 5^15 * 7^13 * 11^10 * 13^9 * 17^8 * 19^8 * 23^8 * 29^7 * 31^7 * 37^7*41^6 * 43^6 * 47^6 * 53^6 * 59^6 * 61^6 * 67^6 * 71^5 * 73^5 * 79^5 * 83^5 * 89^5 * 97^5; rr = {}; n = 2; While[n < 3222617400, If[GCD[jj, n^2 - 1] == n^2 - 1, k = FactorInteger[n^2 - 1]; kk = Last[k][[1]]; If[kk == 97, AppendTo[rr, n]]]; n++]; rr
(* or *)
Select[Range[300000], FactorInteger[#^2 - 1][[-1, 1]] == 97 &]

is(n)=n=n^2-1;forprime(p=2,89,n/=p^valuation(n,p));n>1 && 97^valuation(n,97)==n \\ Charles R Greathouse IV, Jul 01 2013

A181568 Numbers k such that the largest prime factor of k^2-1 is 101.

Original entry on oeis.org

100, 201, 203, 302, 304, 403, 405, 506, 607, 706, 807, 809, 1009, 1011, 1112, 1211, 1312, 1415, 1514, 1516, 1716, 1819, 1918, 2221, 2324, 2524, 2526, 2625, 2627, 3231, 3233, 3334, 3433, 3635, 3736, 3839, 4041, 4241, 4344, 4445, 4544, 4645, 4647, 4746

Offset: 1

Klaus Brockhaus, Oct 31 2010

Sequence is finite, number of terms and last term are still unknown (cf. A175607, A181471).
From David A. Corneth, Sep 11 2019: (Start)
Are there any terms > 941747621709311?
As k^2 - 1 = (k - 1)(k + 1), a(n) is of the form 101*m +- 1. (End)

David A. Corneth, Table of n, a(n) for n = 1..3340 (first 2325 terms from Klaus Brockhaus, terms < 10^17).
Florian Luca, Filip Najman, On the largest prime factor of x^2-1, arXiv:1005.1533 [math.NT], 2010.
Florian Luca, Filip Najman, On the largest prime factor of x^2-1, Mathematics of Computation 80 (2011), 429-435. (Paper has errata that was posted on the MOC website.)

Cf. A175607, A181471, A181447-A181470.

[ n: n in [2..5000] | m eq 101 where m is D[#D] where D is PrimeDivisors(n^2-1) ];

Select[Range[4746], FactorInteger[#^2-1][[-1, 1]]==101&] (* Metin Sariyar, Sep 15 2019 *)

is(n)=n=n^2-1; forprime(p=2, 97, n/=p^valuation(n, p)); n>1 && 101^valuation(n, 101)==n \\ Charles R Greathouse IV, Jul 01 2013

A002072 a(n) = smallest number m such that for all k > m, either k or k+1 has a prime factor > prime(n).

Original entry on oeis.org

1, 8, 80, 4374, 9800, 123200, 336140, 11859210, 11859210, 177182720, 1611308699, 3463199999, 63927525375, 421138799639, 1109496723125, 1453579866024, 20628591204480, 31887350832896, 31887350832896, 119089041053696, 2286831727304144, 9591468737351909375, 9591468737351909375, 9591468737351909375, 9591468737351909375, 9591468737351909375, 19316158377073923834000

Offset: 1

N. J. A. Sloane

An effective abc conjecture (c < rad(abc)^2) would imply that a(27) = a(28) = ... = a(32), and a(33) = 124225935845233319439173. - Lucas A. Brown, Sep 20 2020

			a(1) = 1 since for any number k greater than 1, it is impossible that k and k+1 both are powers of 2, so at least one of them has a prime factor > 2. (For m = 0 this would not hold for k = 1, k+1 = 2.)
a(2) = 8 since for any larger k, we cannot have k and k+1 both 3-smooth (cf. A003586).
31887350832897 = 3^9*7*37*41^2*61^2, 31887350832896 = 2^8*13*19*23*29^4*31, this number appears twice because there is no pair of numbers with max. factor = 67 that is larger than this number.

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, Python program.
E. F. Ecklund and R. B. Eggleton, Prime factors of consecutive integers, Amer. Math. Monthly, 79 (1972), 1082-1089.
D. H. Lehmer, On a problem of Størmer, Ill. J. Math., 8 (1964), 57-79.
Don Reble, Python program
Jim White, Results to P = 127
Wikipedia, Størmer's theorem

Cf. A002071, A003032, A003033, A122463, A145606, A175607.

Equals A117581(n) - 1.

smoothNumbers[p_?PrimeQ, max_Integer] := 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}]; Sort[Flatten[Table[Times @@ (pp^aa), Evaluate[ Sequence @@ iter]]]]]; a[n_] := Module[{sn = smoothNumbers[Prime[n], Ceiling[2000 + 10^n/n]], pos}, pos = Position[Differences[sn], 1][[-1, 1]]; sn[[pos]]]; Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 1, 12}] (* Jean-François Alcover, Nov 17 2016, after M. F. Hasler's observation *)

A002072(n, a=[1, 8, 80, 4374, 9800, 123200, 336140, 11859210, 11859210, 177182720, 1611308699, 3463199999, 63927525375, 421138799639, 1109496723125, 1453579866024])=a[n] \\ "practical" solution for use in other sequences, easily extended to more values. - M. F. Hasler, Jan 16 2015

A2072=List(1); A002072(n)={while(#A2072 best && isSmooth(sol, P) && isSmooth(sol+1, P) && best=sol, p=primes([1, P])); for(i=1, 2^#p, i==2 && next; my(qq = 2*vecprod(vecextract(p,i-1)), qn = [qq, sqrtint(qq), 0, 1], cf = [1,0,0,1], xi, aa, x0, x1, y0, y1); until(x0, aa = (qn[2]+qn[3])\qn[4]; qn[3] = aa*qn[4] - qn[3]; qn[4] = (qn[1] - qn[3]^2) \ qn[4]; cf = [aa*cf[1]+cf[3], aa*cf[2]+cf[4], cf[1], cf[2]]; cf[1]^2 - qq*cf[2]^2 == 1 && [x0,x1, y0,y1] = [x1, cf[1], y1, cf[2]] ); isSmooth(y0, P) || next; check(xi = x0); check(x1); for (i=3, max(P\/2, 3), [x0, x1] = [x1, x1 * xi * 2 - x0]; check(x1)))/*for i*/; listput(A2072, best) } \\ Following Don Reble's Python program. - M. F. Hasler, Mar 01 2025

a(n) < 10^n/n except for n=4. (Conjectured, from experimental data.) - M. F. Hasler, Jan 16 2015

More terms from Don Reble, Jan 11 2005
a(18)-a(26) from Fred Schneider, Sep 09 2006
Corrected and extended by Andrey V. Kulsha, Aug 10 2011, according to Jim White's computations.

A223701 Irregular triangle of numbers k such that prime(n) is the largest prime factor of k^2 - 1.

Original entry on oeis.org

3, 2, 5, 7, 17, 4, 9, 11, 19, 26, 31, 49, 161, 6, 8, 13, 15, 29, 41, 55, 71, 97, 99, 127, 244, 251, 449, 4801, 8749, 10, 21, 23, 34, 43, 65, 76, 89, 109, 111, 197, 199, 241, 351, 485, 769, 881, 1079, 6049, 19601, 12, 14, 25, 27, 51, 53, 64, 79, 129, 131, 155

Offset: 1

T. D. Noe, Apr 03 2013

Note that the first number of each row forms the sequence 3, 2, 4, 6, 10, 12,..., which is A039915. The first 25 rows, except the first, are in A181447-A181470.

			Irregular triangle:
  {3},
  {2, 5, 7, 17},
  {4, 9, 11, 19, 26, 31, 49, 161},
  {6, 8, 13, 15, 29, 41, 55, 71, 97, 99, 127, 244, 251, 449, 4801, 8749}

Andrew Howroyd, Table of n, a(n) for n = 1..16223 (first 25 rows for primes up to 97)
Florian Luca and Filip Najman, On the largest prime factor of x^2-1, arXiv:1005.1533 [math.NT], 2010.
Florian Luca and Filip Najman, On the largest prime factor of x^2-1, Mathematics of Computation 80 (2011), 429-435. (Paper has errata that was posted on the MOC website.)
Filip Najman, List of Publications Page (Adjacent to entry number 4 are links with the data files for the first 25 rows (=16223 terms) of this sequence)

Rows 2..25 with complete data are: A181447, A181448, A181449, A181450, A181451, A181452, A181453, A181454, A181455, A181456, A181457, A181458, A181459, A181460, A181461, A181462, A181463, A181464, A181465, A181466, A181467, A181468, A181469, A181470.
Row 26 is A181568.
Cf. A039915 (first terms), A175607 (last terms), A181471 (row lengths), A379344 (row sums).
Cf. A223702, A223703, A223704 (related tables).

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

A068310 n^2 - 1 divided by its largest square divisor.

Original entry on oeis.org

3, 2, 15, 6, 35, 3, 7, 5, 11, 30, 143, 42, 195, 14, 255, 2, 323, 10, 399, 110, 483, 33, 23, 39, 3, 182, 87, 210, 899, 15, 1023, 17, 1155, 34, 1295, 38, 1443, 95, 1599, 105, 1763, 462, 215, 506, 235, 138, 47, 6, 51, 26, 2703, 78, 2915, 21, 3135, 203, 3363, 870, 3599

Offset: 2

Lekraj Beedassy, Feb 25 2002

In other words, squarefree part of n^2-1.

Least m for which x^2 - m*y^2 = 1 has a solution with x = n.

			a(6) = 35, as 6^2 - 1 = 35 itself is squarefree.
7^2-1 = 48 = A005563(6), whose largest square divisor is A008833(48) = 16, so a(7) = 48/16 = 3.

Reinhard Zumkeller, Table of n, a(n) for n = 2..10000

Cf. A002350, A007913, A067872, A033314, A027746, A175607.

a068310 n = f 1 $ a027746_row (n^2 - 1) where
   f y [] = y
   f y [p] = y*p
   f y (p:ps'@(p':ps)) | p == p' = f y ps
                       | otherwise = f (y*p) ps'
-- Reinhard Zumkeller, Nov 26 2011

a[n_] := Times@@(#[[1]] ^ Mod[ #[[2]], 2]&/@FactorInteger[n^2-1])
Table[(n^2-1)/Max[Select[Divisors[n^2-1],IntegerQ[Sqrt[#]]&]],{n,2,60}] (* Harvey P. Dale, Dec 08 2019 *)

a(n) = core(n*n - 1); \\ David Wasserman, Mar 07 2005

a(n) = A007913(n^2-1).

a(n) = A005563(n-1) / A008833(n^2 - 1). - Reinhard Zumkeller, Nov 26 2011; corrected by Georg Fischer, Dec 10 2022

Edited by Dean Hickerson, Mar 19 2002

Entry revised by N. J. A. Sloane, Apr 27 2007

A145606 Largest number x such that x and x+1 are prime(n)-smooth but not prime(n-1)-smooth.

Original entry on oeis.org

1, 8, 80, 4374, 9800, 123200, 336140, 11859210, 5142500, 177182720, 1611308699, 3463199999, 63927525375, 421138799639, 1109496723125, 1453579866024, 20628591204480, 31887350832896, 12820120234375, 119089041053696, 2286831727304144, 9591468737351909375, 17451620110781856, 166055401586083680, 49956990469100000, 4108258965739505499, 19316158377073923834000, 386539843111191224

Offset: 1

T. D. Noe, Oct 14 2008

Note that this sequence is not always increasing. For many n, a(n) is the same as A002072(n). See A145605 for a triangle of values.

An effective abc conjecture (c < rad(abc)^2) would imply that a(29)-a(33) is (90550606380841216610, 205142063213188103639, 53234795127882729824, 4114304445616636016031, 124225935845233319439173). - Lucas A. Brown, Sep 20 2020

Jim White, Results to P = 127

Cf. A002072, A117581, A145605, A175607.

Terms a(16) onward by Andrey V. Kulsha, Aug 10 2011, according to Jim White's computations

A181471 a(n) = number of numbers of the form k^2-1 having n-th prime as largest prime divisor.

Original entry on oeis.org

1, 4, 8, 16, 20, 34, 47, 72, 95, 126, 168, 208, 262, 343, 433, 507, 634, 799, 976, 1146, 1439, 1698, 2082, 2371, 2734

Offset: 1

Artur Jasinski, Oct 21-22 2010

Theorem: zero does not occur in this sequence. Proof: (p-1)^2-1=(p-2)p. This means that p is greatest prime divisor of (p-1)^2-1 for every p.

An effective abc conjecture (c < rad(abc)^2) would imply that a(24)-a(33) are (2371, 2734, 3360, 4022, 4637, 5575, 6424, 7268, 8351, 9661). - Lucas A. Brown, Oct 01 2022

Florian Luca and Filip Najman, On the largest prime factor of x^2-1, arXiv:1005.1533 [math.NT], 2010.
Florian Luca and Filip Najman, On the largest prime factor of x^2-1, Mathematics of Computation 80 (2011), 429-435. (Paper has errata that was posted on the MOC website.)
Wikipedia, Størmer's theorem.

Row lengths of A223701.

Cf. A039915, A175607.

Wrong terms a(24)-a(25) removed by Lucas A. Brown, Oct 01 2022

a(24)-a(25) from David A. Corneth, Oct 01 2022

A185389 Largest number k such that the greatest prime factor of k^2+1 is A002313(n), the n-th prime not congruent to 3 mod 4.

Original entry on oeis.org

1, 7, 239, 268, 307, 18543, 2943, 485298, 330182, 478707, 24208144, 22709274, 2189376182, 284862638, 599832943, 19696179, 314198789, 3558066693, 69971515635443, 18986886768, 18710140581, 104279454193

Offset: 1

Charles R Greathouse IV, Feb 21 2011

For any prime p, there are finitely many k such that k^2+1 has p as its largest prime factor.

Numbers k such that k^2+1 is p-smooth appear in arctan-relations for the computation of Pi (for example, Machin's identity Pi/4 = 4*arctan(1/5) - arctan(1/239)), see the fxtbook link. [Joerg Arndt, Jul 02 2012]

Joerg Arndt, Matters Computational (The Fxtbook), section 32.5 "Arctangent relations for Pi", pp. 633-640.
Filip Najman, Smooth values of some quadratic polynomials, Glasnik Matematicki Series III 45 (2010), pp. 347-355.
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, Home Page (gives all 811 numbers x such that x^2+1 has no prime factor greater than 197)

Equivalents for other polynomials: A175607 (k^2 - 1), A145606 (k^2 + k).

cp's OEIS Frontend

A076605 Largest prime divisor of n^2 - 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

A181447 Numbers k such that 3 is the largest prime factor of k^2 - 1.

Views

Author

Keywords

Comments

Crossrefs

Programs

Magma

Mathematica

PARI

A181470 Numbers n such that 97 is the largest prime factor of n^2 - 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Magma

Mathematica

PARI

A181568 Numbers k such that the largest prime factor of k^2-1 is 101.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

A002072 a(n) = smallest number m such that for all k > m, either k or k+1 has a prime factor > prime(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A223701 Irregular triangle of numbers k such that prime(n) is the largest prime factor of k^2 - 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A068310 n^2 - 1 divided by its largest square divisor.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs