A115957 -id:A115957 - cp's OEIS frontend

A115958 Numbers k having exactly 4 distinct prime factors, the largest of which is greater than or equal to sqrt(k) (i.e., sqrt(k)-rough numbers with exactly 4 distinct prime factors).

930, 1110, 1230, 1290, 1410, 1590, 1770, 1806, 1830, 1974, 2010, 2130, 2190, 2226, 2370, 2478, 2490, 2562, 2670, 2814, 2910, 2982, 3030, 3066, 3090, 3210, 3270, 3318, 3390, 3486, 3660, 3738, 3810, 3930, 4020, 4074, 4110, 4170, 4242, 4260, 4326, 4380

Offset: 1

Emeric Deutsch, Feb 02 2006

nonn

			3660 is in the sequence because it has 4 distinct prime factors (2, 3, 5 and 61) and 61 > sqrt(3660).

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

Cf. A115956, A115957, A115959, A115960, A115961.

with(numtheory): a:=proc(n) if nops(factorset(n))=4 and factorset(n)[4]^2>=n then n else fi end: seq(a(n),n=1..4500);

pf4Q[n_]:=Module[{f=FactorInteger[n]},Length[f]==4 && f[[-1,1]] >= Sqrt[ n]]; Select[Range[5000],pf4Q] (* Harvey P. Dale, Sep 13 2017 *)

A115959 Numbers k having exactly 5 distinct prime factors, the largest of which is greater than or equal to sqrt(k) (i.e., sqrt(k)-rough numbers with exactly 5 distinct prime factors).

Original entry on oeis.org

44310, 46830, 47670, 48090, 48930, 50190, 50610, 52710, 53970, 55230, 56490, 56910, 58170, 59010, 59430, 61530, 64470, 65310, 65730, 66570, 69510, 70770, 72870, 73290, 74130, 75390, 77070, 78330, 79590, 80430, 81690, 83370, 84210

Offset: 1

Emeric Deutsch, Feb 02 2006

nonn

			46830 is in the sequence because it has 5 distinct prime factors (2, 3, 5, 7 and 223) and 223 > sqrt(46830).

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

Cf. A115956, A115957, A115958, A115960, A115961.

with(numtheory): a:=proc(n) if nops(factorset(n))=5 and factorset(n)[5]^2>=n then n else fi end: seq(a(n),n=1..93000);

A115956 Numbers k having exactly 2 distinct prime factors, the largest of which is greater than or equal to sqrt(k) (i.e., sqrt(k)-rough numbers with exactly 2 distinct prime factors).

Original entry on oeis.org

6, 10, 14, 15, 20, 21, 22, 26, 28, 33, 34, 35, 38, 39, 44, 46, 51, 52, 55, 57, 58, 62, 65, 68, 69, 74, 76, 77, 82, 85, 86, 87, 88, 91, 92, 93, 94, 95, 99, 104, 106, 111, 115, 116, 117, 118, 119, 122, 123, 124, 129, 133, 134, 136, 141, 142, 143, 145, 146, 148, 152, 153

Offset: 1

Emeric Deutsch, Feb 02 2006

nonn

			20 is in the sequence because it has 2 distinct prime factors (2 and 5) and 5 > sqrt(20).

Cf. A115957, A115958, A115959, A115960, A115961.

with(numtheory): a:=proc(n) if nops(factorset(n))=2 and factorset(n)[2]^2>=n then n else fi end: seq(a(n),n=1..170);

tdpfQ[n_]:=Module[{fi=FactorInteger[n]},Length[fi]==2&&fi[[2,1]]>Sqrt[n]]; Select[Range[ 200],tdpfQ] (* Harvey P. Dale, Aug 07 2023 *)

A115960 Numbers k having exactly 6 distinct prime factors, the largest of which is greater than or equal to sqrt(k) (i.e., sqrt(k)-rough numbers with exactly 6 distinct prime factors).

Original entry on oeis.org

5338410, 5389230, 5403090, 5407710, 5421570, 5430810, 5444670, 5477010, 5490870, 5500110, 5504730, 5518590, 5527830, 5541690, 5569410, 5583270, 5597130, 5629470, 5638710, 5652570, 5680290, 5698770, 5712630, 5721870

Offset: 1

Emeric Deutsch, Feb 02 2006

nonn

			5389230 is in the sequence because it has 6 distinct prime factors (2, 3, 5, 7, 11 and 2333) and 2333 > sqrt(5389230).

Cf. A115956, A115957, A115958, A115959, A115961.

with(numtheory): a:=proc(n) if nops(factorset(n))=6 and factorset(n)[6]^2>=n then n else fi end: seq(a(n),n=(2*3*5*7*11)^2..5850000);

dpf6Q[n_]:=Module[{pf=FactorInteger[n][[All,1]]},Length[pf]==6 && pf[[6]]>=Sqrt[n]]; Select[Range[6*10^6],dpf6Q] (* Harvey P. Dale, Mar 24 2017 *)

A115961 a(n)=least number having exactly n distinct prime factors, the largest of which is greater than or equal to sqrt(a(n)).

Original entry on oeis.org

2, 6, 42, 930, 44310, 5338410, 902311410, 260630159790, 94084209188970, 49770436899273090, 41856930884959119930, 40224510201386387907030, 55067354465876062759959510, 92568222856398333359120816010

Offset: 1

Emeric Deutsch, Feb 02 2006

nonn

			a(3)=42; indeed, 42=2*3*7, 7>sqrt(42) and 2*3*5 does not qualify because
5<sqrt(30).

Cf. A115956, A115957, A115958, A115959, A115960.

Cf. A002110.

a:=n->product(ithprime(j),j=1..n-1)*nextprime(product(ithprime(j),j=1..n-1)): seq(a(n),n=1..16);

a(n)=y*(smallest prime that is larger than y), where y is the product of first n-1 consecutive primes.

a(n) = (n-1)# * NextPrime((n-1)#). a(n) = A002110(n-1) * NextPrime(A002110(n-1)). E.g. a(15) = 14# * 13082761331670077 = (2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43) + 13082761331670077, since 13082761331670077 = 14# + 47 is the least prime > 14#. - Jonathan Vos Post, Feb 13 2006

A306330 Squarefree n with >= 3 factors that admit idempotent factorizations n = p*q.

Original entry on oeis.org

30, 42, 66, 78, 102, 105, 114, 130, 138, 165, 170, 174, 182, 186, 195, 210, 222, 246, 255, 258, 266, 273, 282, 285, 290, 318, 330, 345, 354, 366, 370, 390, 399, 402, 410, 426, 434, 435, 438, 455, 462, 465, 474, 498, 510, 518, 530, 534, 546, 555, 570, 582, 602

Offset: 1

Barry Fagin, Feb 07 2019

nonn

An idempotent factorization of n is a way of writing n = p*q such that b^(k(p-1)(q-1)+1) is congruent to b mod n for any integer k >= 0 and any b in Z_n. For example, p = 19, q = 15 is an idempotent factorization of n = 285.  All factorizations of semiprimes are idempotent, so this sequence is restricted to n with >= 3 factors.  Idempotent factorizations have the property that p and q generate correctly functioning RSA keys, even if one or both are composite.
We show in the reference below that a bipartite factorization of a squarefree integer n = pq is idempotent if and only if lambda(pq) divides (p-1)(q-1).
(p and q are not required to be primes. - N. J. A. Sloane, Feb 08 2019)

			30 = 5 * 6, 42 = 7 * 6, 66 = 11 * 6, 78 = 13 * 6, 102 = 17 * 6, 105 = 7 * 15, 114 = 19 * 6, 130 = 13 * 10 are the idempotent factorizations for the first 8 terms in the sequence. 210 = 10 * 21 is the smallest n with a fully composite idempotent factorization, one in which both p and q are composite. The number n = p * 6 is idempotent for any prime p >= 5.

Barry Fagin, Table of n, a(n) for n = 1..5920 (all terms <= 2^16)
Barry Fagin, Idempotent factorizations for all n < 2^26
Barry Fagin, Idempotent Factorizations of Square-Free Integers, Information 2019, 10(7), 232.

Cf. A115957, A138636, A002322.

Subsequence of A120944 (composite squarefree numbers).

isok3(p, q, n) = frac((p-1)*(q-1)/lcm(znstar(n)[2])) == 0;
isok(n) = {if (issquarefree(n) && omega(n) >= 3, my(d = divisors(n)); for (k=1, #d\2, if ((d[k] != 1) && isok3(d[k], n/d[k], n), return (1););););} \\ Michel Marcus, Feb 22 2019

Edited by N. J. A. Sloane, Feb 08 2019

A306508 Squarefree numbers that have fully composite idempotent factorizations.

Original entry on oeis.org

210, 462, 570, 1155, 1302, 1330, 1365, 1785, 2210, 2310, 2730, 3003, 3410, 3710, 3990, 4305, 4515, 4758, 4810, 5005, 5187, 5474, 5610, 5642, 6006, 6105, 6118, 6270, 6510, 6622, 6630, 7410, 7770, 8265, 8385, 8463, 8645, 9282, 9471, 9870, 10010, 10101, 10230, 10374, 10545, 10582

Offset: 1

Barry Fagin, Feb 20 2019

nonn

Fully composite idempotent factorizations are bipartite factorizations n=p*q such that p and q are composite numbers with the property that for any b in Z_n, b^(k(p-1)(q-1)+1) is congruent to b mod n for any integer k >= 0. Idempotent factorizations have the property that p and q generate correctly functioning RSA keys, even if one or both are composite.

2730 has more than one fully composite idempotent factorization (10*273, 21*130). It is the smallest positive integer with that property. 7770 and 8463 are similar.

			210=10*21, 462=22*21, 570=10*57, 1155=21*55, 1302=6*217, 1330=10*133, 1365=15*91 and 1785=21*85 are the fully composite idempotent factorizations for the first eight terms.

Barry Fagin, Table of n, a(n) for n = 1..63737
Barry Fagin, All n < 2^27 and their fully composite idempotent factorizations
Barry Fagin, Idempotent Factorizations of Square-Free Integers, Information 2019, 10(7), 232.
Barry Fagin, Search Heuristics and Constructive Algorithms for Maximally Idempotent Integers, Information (2021) Vol. 12, No. 8, 305.

Cf. A115957, A138636, A002322.
Subsequence of A120944 (composite squarefree numbers).
Subsequence of A306330 (composite squarefree numbers with idempotent factorizations).

isokc(p, q, n) = (p != 1) && !isprime(p) && !isprime(q) && (frac((p-1)*(q-1)/lcm(znstar(n)[2])) == 0);
isok(n) = {if (issquarefree(n) && omega(n) >= 3, my(d = divisors(n)); for (k=1, #d\2, if (isokc(d[k], n/d[k], n), return (1););););} \\ Michel Marcus, Feb 22 2019

for n in range(2,max_n):
    factor_list = numbthy.factor(n)
    numFactors = len(factor_list)
    if numFactors <= 3:
        continue
    if not bsflib.is_composite_and_square_free_with_list(n,factor_list):
        continue
    fciFactorizations = bsflib.fullyCompositeIdempotentFactorizations(n,factor_list)
    numFCIFs = len(fciFactorizations)
    if numFCIPs > 0:
        fcIdempotents += 1
    print(n)

A380438 Integers k that are the product of 3 distinct primes, the smallest of which is larger than the 5th root of k: k = pqr, where p, q, r are primes and k^(1/5) < p < q < r.

Original entry on oeis.org

30, 105, 165, 195, 231, 385, 455, 595, 665, 715, 805, 935, 1001, 1015, 1045, 1085, 1105, 1235, 1265, 1295, 1309, 1435, 1463, 1495, 1505, 1547, 1595, 1615, 1645, 1705, 1729, 1771, 1855, 1885, 1955, 2015, 2035, 2065, 2093, 2135, 2185, 2233, 2255, 2261, 2345, 2365, 2387, 2405, 2431, 2465, 2485

Offset: 1

Matthew Goers, Jan 24 2025

nonn

This subsequence of the sphenics (A007304) is similar to A362910 or A138109 for semiprimes. Ishmukhametov and Sharifullina defined semiprimes n = p*q where each prime is greater than n^(1/4) as strongly semiprime. This sequence defines sphenic numbers with an analogous 'strength' as a product of 3 distinct primes k = p*q*r where each prime is greater than k^(1/5), or, alternately, k < p^5.
The only even term is 30 = 2*3*5.
As there are many equivalent ways of expressing Ishmukhametov and Sharifullina's "strongly semiprime" criterion, it is not obvious how it should most appropriately be extended to measure an equivalent "strength" of numbers with more prime factors. Here we follow a comparison of the least prime factor, p, to the factored number, k; but we could instead compare the greatest prime factor, r, to k; or p to r; or measure the variance/standard deviation of the prime factors (more precisely, after twice taking the logarithm of each factor as is done in A379271). Furthermore, it looks clear that the comparison used here (p against k^(1/5)) could be shown to give a substantially lower density asymptotically within the sphenics than Ishmukhametov and Sharifullina's equivalent for semiprimes. - Peter Munn, Feb 18 2025 and May 13 2025

			231 = 3*7*11 and 231^(1/5) < 3, so 231 is in the sequence.
255 = 3*5*17 but 255^(1/5) > 3, so 255 is not in the sequence.

Chai Wah Wu, Table of n, a(n) for n = 1..10000 (terms 1..420 from Matthew Goers).
Sh. T. Ishmukhametov and F. F. Sharifullina, On distribution of semiprime numbers, Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 2014, No. 8, pp. 53-59. On distribution of semiprime numbers, English translation, Russian Mathematics, Vol. 58, No. 8 (2014), pp. 43-48, ResearchGate link.

Subsequence of A253567, A290965, A379271, and A007304.
A046301 is a subsequence (product of 3 successive primes).
Cf. A115957, A138109, A251728, A362910 (strong semiprimes), A380995.

q[k_] := Module[{f = FactorInteger[k]}, f[[;; , 2]] == {1, 1, 1} && f[[1, 1]]^5 > k]; Select[Range[2500], q] (* Amiram Eldar, Feb 14 2025 *)

isok(k) = my(f=factor(k)); (bigomega(f)==3) && (omega(f)==3) && (k < vecmin(f[,1])^5); \\ Michel Marcus, Jan 27 2025

list(lim)=my(v=List()); forprime(p=2,sqrtnint(lim\=1,3), forprime(q=p+1,min(sqrtint(lim\p),p^2), forprime(r=q+2,min(lim\(p*q),p^4\q), listput(v,p*q*r)))); Set(v) \\ Charles R Greathouse IV, May 20 2025

from math import isqrt
from sympy import primepi, primerange, integer_nthroot
def A380438(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return n+x-sum(max(0,primepi(min(x//(p*q),p**4//q))-b) for a,p in enumerate(primerange(integer_nthroot(x,3)[0]+1),1) for b,q in enumerate(primerange(p+1,isqrt(x//p)+1),a+1))
    return bisection(f,n,n) # Chai Wah Wu, Mar 28 2025

A380995 Integers k that are the product of 3 distinct primes, the smallest of which is larger than the 4th root of k: k = pqr, where p, q, r are primes and k^(1/4) < p < q < r.

Original entry on oeis.org

385, 455, 595, 1001, 1309, 1463, 1547, 1729, 1771, 2093, 2233, 2261, 2387, 2431, 2717, 3289, 3553, 4147, 4199, 4301, 4433, 4807, 5083, 5291, 5423, 5681, 5797, 5863, 6061, 6149, 6409, 6479, 6721, 6851, 6919, 7163, 7337, 7429, 7579, 7657, 7667, 7733, 7843, 8041, 8177, 8437, 8569, 8671, 8723, 8789, 8987, 9061

Offset: 1

Matthew Goers, Feb 12 2025

nonn

This subsequence of the sphenics (A007304) is similar to A362910 or A138109 for semiprimes. Ishmukhametov and Sharifullina defined semiprimes n = p*q where each prime is greater than n^(1/4) as strongly semiprime. This sequence lists sphenic numbers that are a product of 3 distinct primes k = p*q*r where each prime is greater than k^(1/4).
Sequence is intersection of A007304 (sphenics) and A088382 (numbers not exceeding the 4th power of their smallest prime factor).
No terms have 2 or 3 as a prime factor, as all sphenic numbers are greater than 2^4 = 16 and all odd sphenic numbers are greater than 3^4 = 81.
A380438 is the 'less strong' sequence of sphenic numbers k = p*q*r, where k^(1/5) < p < q < r.

			595 = 5*7*17 and 595^(1/4) < 5, so 595 is in the sequence.
665 = 5*7*19 but 665^(1/4) > 5, so 665 is not in the sequence.

David A. Corneth, Table of n, a(n) for n = 1..10000 (first 231 terms from Matthew Goers)
Sh. T. Ishmukhametov and F. F. Sharifullina, On distribution of semiprime numbers, Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 2014, No. 8, pp. 53-59. On distribution of semiprime numbers, English translation, Russian Mathematics, Vol. 58, No. 8 (2014), pp. 43-48, ResearchGate link.
Matthew Goers, Factors of Terms

Cf. A007304 (sphenics), A088382, A380438, A115957, A362910 (strong semiprimes), A251728, A138109.

Subsequence of A253567, A290965.

q[k_] := Module[{f = FactorInteger[k]}, f[[;; , 2]] == {1, 1, 1} && f[[1, 1]]^4 > k]; Select[Range[10^4], q] (* Amiram Eldar, Feb 14 2025 *)

is(n) = my(f = factor(n)); f[,2] == [1,1,1]~ && f[1,1]^4 > n \\ David A. Corneth, Apr 24 2025

from math import isqrt
from sympy import primepi, primerange, integer_nthroot
def A380995(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1		
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return n+x-sum(max(0,primepi(min(x//(p*q),p**3//q))-b) for a,p in enumerate(primerange(integer_nthroot(x,3)[0]+1),1) for b,q in enumerate(primerange(p+1,isqrt(x//p)+1),a+1))
    return bisection(f,n,n) # Chai Wah Wu, Mar 28 2025

A306812 Maximally idempotent integers with three or more factors.

Original entry on oeis.org

273, 455, 1729, 2109, 2255, 2387, 3367, 3515, 4433, 4697, 4921, 5673, 6643, 6935, 7667, 8103, 8723, 8729, 9139, 9455, 10235, 10787, 11543, 13237, 13505, 14497, 16211, 16385, 16523, 17507, 18031, 18907, 20033, 20801, 21437, 22649, 23579, 24583

Offset: 1

Barry Fagin, Mar 11 2019

nonn

An integer n has an idempotent factorization n=pq if b^(k(p-1)(q-1)+1) is congruent to b mod n for any integer k >= 0 and any b in Z_n (see A306330). An integer is maximally idempotent if all its bipartite factorizations n=pq are idempotent.

There are 15506 maximally idempotent integers less than 2^30. 15189 have three factors, 315 have four, two have five. The smallest maximally idempotent integer with four factors is 63973=7*13*19*37, a Carmichael number. The two with five factors are 13*19*37*73*109 and 11*31*41*101*151. The smallest maximally idempotent integer with six factors is 11*31*41*61*101*151.

			273 is the smallest maximally idempotent integer.  Factorization is (3,7,13).  Bipartite factorizations are (3,91), (7,39), (13,21).  Lambda(273) = 12, (2*90),(6*38) and (12*20) are all divisible by 12, thus 273 is maximally idempotent.  The same is true for 455 = 5*7*13.  The next entry in the sequence, 1729=7*13*19, is a Carmichael number, but most Carmichael numbers are not maximally idempotent.

Barry Fagin, Table of n < 2^30
Barry Fagin, Table of n < 2^30 with factorizations
Barry Fagin, Idempotent Factorizations of Square-Free Integers, Information 2019, 10(7), 232.

Cf. A115957, A138636, A002322, A306508.

Subsequence of A120944 (composite squarefree numbers). Subsequence of A306330 (squarefree numbers that admit idempotent factorizations). Members of the sequence with >= 4 factors for a subsequence of A306508 (squarefree integers with fully composite idempotent factorizations).

## This uses a custom library of number theory functions and the numbthy library.
## Hopefully the names of the functions make the process clear.
for n in range(2,max_n):
    factor_list = numbthy.factor(n)
    numFactors = len(factor_list)
    if numFactors <= 2: # skip primes and semiprimes
        continue
    if not bsflib.is_composite_and_square_free_with_list(n,factor_list):
        continue
    ipList = bsflib.idempotentPartitions(n, factor_list)
    if len(ipList) == 2**(numFactors-1)-1:
        print(n)

cp's OEIS Frontend

A115958 Numbers k having exactly 4 distinct prime factors, the largest of which is greater than or equal to sqrt(k) (i.e., sqrt(k)-rough numbers with exactly 4 distinct prime factors).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A115959 Numbers k having exactly 5 distinct prime factors, the largest of which is greater than or equal to sqrt(k) (i.e., sqrt(k)-rough numbers with exactly 5 distinct prime factors).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

A115956 Numbers k having exactly 2 distinct prime factors, the largest of which is greater than or equal to sqrt(k) (i.e., sqrt(k)-rough numbers with exactly 2 distinct prime factors).

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

A115960 Numbers k having exactly 6 distinct prime factors, the largest of which is greater than or equal to sqrt(k) (i.e., sqrt(k)-rough numbers with exactly 6 distinct prime factors).

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

A115961 a(n)=least number having exactly n distinct prime factors, the largest of which is greater than or equal to sqrt(a(n)).

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Formula

A306330 Squarefree n with >= 3 factors that admit idempotent factorizations n = p*q.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A306508 Squarefree numbers that have fully composite idempotent factorizations.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

A380438 Integers k that are the product of 3 distinct primes, the smallest of which is larger than the 5th root of k: k = p*q*r, where p, q, r are primes and k^(1/5) < p < q < r.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A380438 Integers k that are the product of 3 distinct primes, the smallest of which is larger than the 5th root of k: k = pqr, where p, q, r are primes and k^(1/5) < p < q < r.

A380995 Integers k that are the product of 3 distinct primes, the smallest of which is larger than the 4th root of k: k = pqr, where p, q, r are primes and k^(1/4) < p < q < r.