A180278 -id:A180278 - cp's OEIS frontend

A219017 Smallest number k such that k^2 - 1 has exactly n distinct prime factors.

2, 4, 11, 29, 131, 419, 1429, 14629, 77141, 509081, 1456729, 22486309, 117048931, 1625292241, 10326137821, 117440297701, 1110819807371, 8678298841211, 138645880242871, 980010587880169

Offset: 1

Michel Lagneau, Nov 09 2012

a(14) <= 1625292241. - Donovan Johnson, Nov 10 2012

			a(3) = 11 is the smallest number of the set {k(i)} = {11, 13, 14, 16, 19, 20, ...} where k(i)^2 - 1 contains 3 distinct prime factors.
a(10) = 509081 because 509081^2-1 = 2 ^ 4 * 3 * 5 * 7 * 11 * 13 * 17 * 23 * 31 * 89 with 10 distinct prime factors.

Michael S. Branicky, Python program

Cf. A180278.

with(numtheory) :for n from 1 to 11 do:ii:=0:for k from 1 to 10^10 while(ii=0) do:x:=k^2-1:y:=factorset(x):n1:=nops(y):if n1=n then ii:=1: printf ( "%d %d \n",n,k):
else fi:od:od:

L = {}; Do[n = 2; While[Length[FactorInteger[n^2 - 1]] != k, n++];  Print@AppendTo[L, n], {k, 15}] (* Giovanni Resta, Nov 10 2012 *)

a(12)-a(13) from Donovan Johnson, Nov 10 2012
a(14)-a(17) from Giovanni Resta, May 10 2017
a(18) from Michael S. Branicky, Feb 08 2023
a(19) from Michael S. Branicky, Feb 15 2023
a(20) from Michael S. Branicky, Feb 19 2023
Name clarified by Pontus von Brömssen, Sep 12 2023

A257366 Smallest integer m such that m^2 + 1 has exactly n prime factors, counted with multiplicity.

Original entry on oeis.org

1, 3, 7, 43, 57, 307, 1068, 2943, 12943, 45807, 110443, 670807, 2733307, 25670807, 113561432, 123327057, 657922943, 17213170807, 7200891693, 148802454193, 1120482141693

Offset: 1

Zak Seidov, Apr 21 2015

Or, first occurrences of n in A193330.
Is the sequence finite?
a(n) exists for arbitrarily large n, and in particular a(n+k) < A185952(n) by the Chinese Remainder Theorem and the fact that -1 is a square mod the primes in A002313, for some k >= 0. Probably a(n) exists for each n. - Charles R Greathouse IV, Apr 21 2015
From Jon E. Schoenfield, Jun 14-15 2015: (Start)
Numbers of the form m^2+1 cannot be divisible by 3; they may be divisible by 2 (but not 2^2), and the only other numbers they can have as prime factors are 5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, ..., i.e., the terms of A002144. This explains why 5 tends to appear with such high multiplicity in the factorizations of a(n)^2+1, as numbers with a higher multiplicity of the prime factor 5 are more likely to be small enough to be the smallest integer with n prime factors than numbers whose n prime factors (counted with multiplicity) are mostly larger than 5. Having 2 as one of the n prime factors is also an advantage, which accounts for the predominance of odd terms, yielding even values of m^2+1.
For k>1, if m^2+1 is divisible by 5^k, then there are only two possible residues of m mod 5^k; e.g., if m^2+1 is divisible by 5^4, then m mod 5^4 must be either 182 or 443. Thus it is not coincidental that the last few digits of some terms also appear as the last few digits of other terms, e.g., terms ending in 443 or 443+500 = 943, or in 182+125 = 307 or 182+625 = 807. (End)

			a(1)=1 because 1^2+1=2(prime),
a(2)=3 because 3^2+1=10=2*5,
a(3)=7 because 7^2+1=50=2*2*5,
...............
a(14)=25670807 because 25670807^2+1=2*5^11*149*45289.

Cf. A002144, A180278, A193330.

Table[m = 1; While[PrimeOmega[m^2 + 1] != n, m++]; m, {n, 12}] (* Michael De Vlieger, Apr 21 2015 *)

a(n)=my(m); while(bigomega(m++^2+1)!=n, ); m \\ Charles R Greathouse IV, Apr 21 2015

a(15)-a(17) from Jon E. Schoenfield, Jun 14 2015
a(18)-a(19) from Jon E. Schoenfield, Jun 15 2015
a(20) from Jon E. Schoenfield, Jul 10 2015
a(21) from Max Alekseyev, Jan 08 2025

A192770 Numbers k such that k^2 + 1 is divisible by precisely four distinct primes where the sum of the largest and the smallest is equal to the sum of the other two.

Original entry on oeis.org

948, 1560, 1772, 13236, 36984, 40452, 94536, 100512, 127224, 425808, 757382, 850416, 875784, 1241106, 2102736, 3343164, 4361808, 4530480, 5401464, 8006700, 8645004, 9806604, 10379136, 10829580, 11366424, 11692746, 13960260

Offset: 1

Michel Lagneau, Jul 09 2011

nonn

			1772 is in the sequence because 1772^2+1 = 5 * 17^2 * 41 * 53 and 5 + 53 = 17 + 41.

Amiram Eldar, Table of n, a(n) for n = 1..80 (terms below 10^9)

Cf. A180278, A192771.

with(numtheory):for n from 1 to 100000 do:x:=n^2+1:y:=factorset(x):n1:=nops(y):if n1=4 and y[4] + y[1] = y[2]+y[3] then printf ( "%d %d \n",n,x):else fi:od:

seqQ[n_] := Module[{p = FactorInteger[n^2 + 1][[;;,1]]}, Length[p] == 4 && p[[1]] + p[[4]] == p[[2]] + p[[3]]]; Select[Range[10^6], seqQ] (* Amiram Eldar, Jan 15 2020 *)

is(n)=my(f=factor(n^2+1)[,1]);#f==4&&f[1]+f[4]==f[2]+f[3]
forstep(n=2,1e7,2,if(is(n),print1(n", "))) \\ Charles R Greathouse IV, Jul 11 2011

a(10)-a(27) from Charles R Greathouse IV, Jul 11 2011

A192771 Numbers k such that k^2 + 1 is divisible by precisely five distinct primes where the sum of the largest and the smallest is equal to the sum of the other three.

Original entry on oeis.org

2153, 2697, 8487, 11293, 12553, 18065, 32247, 43999, 55945, 107607, 134223, 214641, 218783, 366937, 429855, 595471, 620865, 645327, 1330849, 1363977, 1387689, 1532465, 1557535, 1631191, 1716663, 1778711, 2156031, 3166415, 3857215, 4546071

Offset: 1

Michel Lagneau, Jul 09 2011

nonn

			11293 is in the sequence because 11293^2+1 = 2 * 5 ^ 2 * 29 * 281 * 313 and 313 + 2 = 5 + 29 + 281 = 315.

Amiram Eldar, Table of n, a(n) for n = 1..144 (terms below 10^9, terms 1..77 from Lukas Naatz)

Cf. A180278, A192770.

isA192771 := proc(n) local p,s1,n2 ; n2 := n^2+1 ; if A001221(n2) = 5 then p := numtheory[factorset](n2) ; s1 := max(op(p)) + min( op(p)) ; evalb( add(k,k=p) = 2*s1 ) ; else false; end if; end proc:
for n from 1 do if isA192771(n) then printf("%d,\n",n); end if; end do: # R. J. Mathar, Jul 11 2011

seqQ[n_] := Module[{p = FactorInteger[n^2 + 1][[;;,1]]}, Length[p] == 5 && p[[1]] + p[[5]] == p[[2]] + p[[3]] + p[[4]]]; Select[Range[10^6], seqQ] (* Amiram Eldar, Jan 15 2020 *)

for(k=1,5000000,my(f=factor(k^2+1));if(#f[,2]==5,if(f[1,1]+f[5,1]==f[2,1]+f[3,1]+f[4,1],print1(k,", ")))) \\ Hugo Pfoertner, Jan 08 2020

a(17) and beyond from Lukas Naatz, Jan 08 2020

A219108 a(n) = k is the smallest number such that k^3 + 1 has exactly n distinct prime factors.

Original entry on oeis.org

0, 1, 3, 5, 17, 59, 101, 563, 2617, 9299, 22109, 132989, 364979, 1970869, 23515229, 109258049, 831731339

Offset: 0

Jonathan Vos Post, Nov 11 2012

This is to exponent 3 as A180278 is to exponent 2.

			a(0) = 0 because 0^3 + 1 = 1 has no prime factors (being a unit).
a(1) = 1 because 1^3 + 1 = 2 has one prime factor (being a prime).
a(2) = 3 because 3^3 + 1 = 28 has two distinct prime factors {2, 7}.
a(3) = 5 because 5^3 + 1 = 126 has three distinct prime factors {2, 3, 7}.
a(4) = 17 because 17^3 + 1 = 4914 has four distinct prime factors {2, 3, 7, 13}.
a(5) = 59 because 59^3 + 1 = 205380 has five distinct prime factors {2, 3, 5, 7, 163}.

Cf. A001093, A001221, A180278.

k = 1; t = Table[0, {15}]; While[k < 30000001, a = PrimeNu[k^3 + 1]; If[ t[[a]] == 0, t[[a]] = k; Print[{a, k}]]; k++]; t (* Robert G. Wilson v, Dec 12 2012 *)

a(n)=for(k=0, oo, if(omega(k^3+1) == n, return(k))) \\ Andrew Howroyd, Sep 12 2023

a(n) = MIN{k>=0 such that A001221(A001093(k)) = omega(k^3 + 1) = n}.

a(13)-a(14) from Robert G. Wilson v, Dec 12 2012
a(15)-a(16) from Giovanni Resta, May 10 2017
Name clarified and incorrect program removed by Pontus von Brömssen, Sep 12 2023

A164511 Least prime p such that p^2+1 is the product of n distinct primes.

Original entry on oeis.org

2, 3, 13, 47, 463, 2917, 30103, 241727, 3202337, 26066087, 455081827, 7349346113, 122872146223, 2523038248697, 28435279521433, 119919330795347

Offset: 1

T. D. Noe, Aug 14 2009

For n>1, there appear to be an infinite number of primes q for which q^2+1 is the product of n distinct primes (and thus has 2^n divisors). This sequence gives the smallest such prime for each n. See A048161 for primes q such that q^2+1 has two prime factors. Note that all prime factors of p^2+1 must be 2 or primes of the form 4k+1.

			1+2^2 = 5
1+3^2 = 2*5
1+13^2 = 2*5*17
1+47^2 = 2*5*13*17
1+463^2 = 2*5*13*17*97
1+2917^2 = 2*5*13*29*37*61
1+30103^2 = 2*5*13*17*41*73*137
1+241727^2 = 2*5*13*17*29*37*41*601
1+3202337^2 = 2*5*13*17*29*41*73*193*277
1+26066087^2 = 2*5*13*17*29*37*41*89*233*337
1+455081827^2 = 2*5*13*17*37*53*61*73*97*317*349

Cf. A180278.

nn=8; t=Table[0,{nn}]; p=1; While[Times@@t==0, While[p=NextPrime[p]; {q,e}=Transpose[FactorInteger[p^2+1]]; !(Union[e]=={1} && Length[e]<=nn && t[[Length[e]]]==0)]; t[[Length[e]]]=p]; t

generate(A, B, n) = A=max(A, vecprod(primes(n))); (f(m, p, j) = my(list=List()); my(s=sqrtnint(B\m, j)); if(j==1, forprime(q=max(p, ceil(A/m)), s, if(q%4 == 3, next); my(v=m*q); if(issquare(v-1) && isprime(sqrtint(v-1)), listput(list, sqrtint(v-1)))), forprime(q=p, s, if(q%4 == 3, next); list=concat(list, f(m*q, q+1, j-1)))); list); vecsort(Vec(f(1, 2, n)));
a(n) = my(x=vecprod(primes(n)), y=2*x); while(1, my(v=generate(x, y, n)); if(#v >= 1, return(v[1])); x=y+1; y=2*x); \\ Daniel Suteu, Feb 20 2023

a(n) >= A180278(n). - Daniel Suteu, Feb 20 2023

a(12)-a(13) from Donovan Johnson, Oct 09 2009

a(14)-a(16) from Daniel Suteu, Feb 20 2023

A196219 Numbers n such that n^2 is divisible by the sum of the distinct prime divisors of n^2 + 1.

Original entry on oeis.org

7, 18, 187, 378, 1560, 1683, 1710, 1719, 4697, 7788, 8832, 10693, 21708, 22968, 27378, 28322, 29032, 30016, 30635, 32220, 32368, 33813, 36725, 41028, 42444, 44733, 45630, 45985, 50085, 57768, 69936, 81639, 86420, 87116, 92667, 95418, 96348, 97185, 114100

Offset: 1

Michel Lagneau, Sep 29 2011

nonn

			1560 is in the sequence because the sum of the prime distinct divisors of 1560^2+1 is 17+37+53+73=180 and 1560^2 /180=13520.

Charles R Greathouse IV and Zak Seidov, Table of n, a(n) for n = 1..500 (1..100 from Levin)

Cf. A002522, A180278.

with(numtheory):for k from 1 to 120000 do: y:=factorset(k^2+1): s:=sum(y[i],i=1..nops(y)):if irem(k^2,s)=0 then printf(`%d, `, k):else fi:od:

c=0;s={};Do[If[PowerMod[n,2,Plus@@First/@FactorInteger[n^2+1]]==0,AppendTo[s,n];c++;If[c==100,Break[]]],{n,2*10^6}];s (* Zak Seidov, Oct 14 2011 *)

is(n)=my(f=factor(n^2+1)[,1]);n^2%sum(i=1,#f,f[i])==0 \\ Charles R Greathouse IV, Oct 25 2011

A219018 Smallest number k > 0 such that k^n + 1 has exactly n distinct prime factors.

Original entry on oeis.org

1, 3, 5, 43, 17, 47, 51, 1697, 59, 512, 521, 3255, 8189, 18951, 656

Offset: 1

Michel Lagneau, Nov 09 2012

a(16) > 2 * 10^6; a(18) = 19208. - Daniel Suteu, Feb 06 2023

			a(3) = 5 is the smallest number of the set  {k(i)} = {5, 9, 10, 11, 12, 13, 14, 19,….} where k(i)^3 + 1 has exactly 3 distinct prime factors.

Cf. A180278, A001221, A281940.

with(numtheory) :for n from 1 to 10 do:ii:=0:for k from 1 to 10^10 while(ii=0) do:x:=k^n+1:y:=factorset(x):n1:=nops(y):if n1=n then ii:=1: printf ( "%d %d \n",n,k):
else fi:od:od:

L = {}; Do[n = 1; While[Length[FactorInteger[n^k + 1]] != k, n++];  Print@AppendTo[L, n], {k, 15}] (* Giovanni Resta, Nov 09 2012 *)

a(n) = my(k=1); while (omega(k^n+1) != n, k++); k; \\ Daniel Suteu, Feb 06 2023

Definition clarified by Daniel Suteu, Feb 06 2023

a(13)-a(15) from Daniel Suteu, Feb 06 2023

A356872 a(n) = k is the smallest number such that 3*k+1 contains n distinct prime factors.

Original entry on oeis.org

1, 3, 23, 303, 4363, 56723, 1077743, 33410043, 718854803, 22284498903, 824526459423, 35454637755203, 1588862487308763, 68321086954276823, 4167586304210886223, 213640038906023626563, 13032042373267441220363, 873146839008918561764343, 63739719247651055008797063

Offset: 1

Alex Ratushnyak, Sep 02 2022

nonn

David A. Corneth, Table of n, a(n) for n = 1..349

Cf. A002110, A180278, A219108.

from sympy import factorint, isprime
from itertools import count, islice
def f(n): return 1 if isprime(n) else len(factorint(n))
def agen():
    n = 1
    for k in count(0):
        v = f(3*k+1)
        while v >= n: yield k; n += 1
print(list(islice(agen(), 7))) # Michael S. Branicky, Sep 02 2022

From Michael S. Branicky, Sep 02 2022: (Start)
a(n) >= ceiling((A002110(n)-1)/3).
a(n) <= (c*A002110(n+1)/3-1)/3 for n > 1, and c = 1 or 2 chosen so the expression is an integer, with equality holding for c = 1 for n = 2, 3, 6, 7, ... . (End)

a(8) from Michael S. Branicky, Sep 02 2022

a(9)-a(19) from Jon E. Schoenfield, Sep 02 2022

A196220 Integer quotients of k^2 by the sum of the prime distinct divisors of k^2+1, where k = A196219(n).

Original entry on oeis.org

7, 18, 121, 2268, 13520, 1377, 8550, 5157, 7381, 8496, 76176, 83521, 161604, 284229, 1028196, 4092529, 275804, 274432, 336985, 1153476, 962948, 48841, 319225, 276676, 617796, 3946827, 684450, 156349, 632025, 1256454, 6368547, 244917, 2506180, 2256004, 5410947

Offset: 1

Michel Lagneau, Sep 29 2011

nonn

Generated by k = 7, 18, 187, 378, 1560, 1683, … (A196219).

			For k = 378, the prime distinct divisors of 378^2 + 1 are 5, 17, 41 and 378^2 /(5+17+41) = 2268. Hence 2268 is in the sequence.

Amiram Eldar, Table of n, a(n) for n = 1..500 (calculated from the b-file at A196219)

Cf. A002522, A008472, A180278, A196219.

with(numtheory):for k from 1 to 120000 do: y:=factorset(k^2+1): s:=sum(y[i],i=1..nops(y)):if irem(k^2,s)=0 then printf(`%d, `, k^2/s):else fi:od:

Select[Table[n^2/Total[Transpose[FactorInteger[n^2+1]][[1]]],{n,10^5}],IntegerQ] (* Harvey P. Dale, Apr 18 2015 *)

a(n) = A196219(n)^2/A008472(A196219(n)^2 + 1). - Amiram Eldar, Mar 09 2020

cp's OEIS Frontend

A219017 Smallest number k such that k^2 - 1 has exactly n distinct prime factors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A257366 Smallest integer m such that m^2 + 1 has exactly n prime factors, counted with multiplicity.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Extensions

A192770 Numbers k such that k^2 + 1 is divisible by precisely four distinct primes where the sum of the largest and the smallest is equal to the sum of the other two.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A192771 Numbers k such that k^2 + 1 is divisible by precisely five distinct primes where the sum of the largest and the smallest is equal to the sum of the other three.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A219108 a(n) = k is the smallest number such that k^3 + 1 has exactly n distinct prime factors.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A164511 Least prime p such that p^2+1 is the product of n distinct primes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A196219 Numbers n such that n^2 is divisible by the sum of the distinct prime divisors of n^2 + 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs