A037143 -id:A037143 - cp's OEIS frontend

A101049 Number of partitions of n into parts having at most two prime-factors.

1, 2, 3, 5, 7, 11, 15, 21, 29, 40, 53, 71, 93, 122, 158, 203, 259, 329, 415, 521, 651, 809, 1001, 1234, 1515, 1853, 2258, 2743, 3321, 4009, 4825, 5791, 6932, 8277, 9859, 11715, 13889, 16431, 19398, 22854, 26873, 31539, 36949, 43210, 50446, 58796, 68419

Offset: 1

Reinhard Zumkeller, Nov 28 2004

nonn

			n=10 has two partitions with parts having more than two
prime-factors: 10 = 2*2*2 + 2 = 2*2*2 + 1 + 1, therefore
a(10) = A000041(10) - 2 = 42 - 2 = 40.

Feihu Liu, Guoce Xin, and Chen Zhang, Ehrhart Polynomials of Order Polytopes: Interpreting Combinatorial Sequences on the OEIS, arXiv:2412.18744 [math.CO], 2024. See p. 15.

Cf. A000041, A101048, A037143, A101040.

Table[Count[IntegerPartitions[n], ?(AllTrue[#, PrimeOmega[#] <= 2 &] &)], {n, 40}] (* _Michael De Vlieger, Jan 14 2025 *)

A129597 Central diagonal of array A129595.

Original entry on oeis.org

1, 4, 6, 16, 10, 24, 14, 64, 54, 40, 22, 96, 26, 56, 90, 256, 34, 216, 38, 160, 126, 88, 46, 384, 250, 104, 486, 224, 58, 360, 62, 1024, 198, 136, 350, 864, 74, 152, 234, 640, 82, 504, 86, 352, 810, 184, 94, 1536, 686, 1000, 306, 416, 106, 1944, 550, 896, 342

Offset: 1

Antti Karttunen, May 01 2007, based on Marc LeBrun's Jan 11 2006 message on SeqFan mailing list

nonn

These are the positions of first appearances of each positive integer in A346704. - Gus Wiseman, Oct 16 2021

Antti Karttunen, Table of n, a(n) for n = 1..10000

a(n) = A129595(n,n).
The sum of prime indices of a(n) is 2*A056239(n) - A061395(n) + 1 for n > 1.
The version for odd indices is A342768(n) = a(n)/2 for n > 1.
Except the first term, the sorted version is 2*A346635.
These are the positions of first appearances in A346704.
A001221 counts distinct prime factors.
A001222 counts prime factors with multiplicity.
A027187 counts partitions of even length, ranked by A028260.
A346633 adds up the even bisection of standard compositions (odd: A209281).
A346698 adds up the even bisection of prime indices (reverse: A346699).
Cf. A000290, A006530, A037143, A329888, A344606, A345957, A346697, A346700, A346701.

Table[If[n==1,1,2*n^2/FactorInteger[n][[-1,1]]],{n,100}] (* Gus Wiseman, Aug 10 2021 *)

A129597(n) = if(1==n, n, my(f=factor(n)); (2*n*n)/f[#f~, 1]); \\ Antti Karttunen, Oct 16 2021

From Gus Wiseman, Aug 10 2021: (Start)
For n > 1, A001221(a(n)) = A099812(n).
If g = A006530(n) is the greatest prime factor of n > 1, then a(n) = 2n^2/g.
a(n) = A100484(A000720(n)) = 2n iff n is prime.
a(n > 1) = 2*A342768(n).
(End)

A275013 Lower ends of record gaps between numbers that are either primes or semiprimes.

Original entry on oeis.org

2, 7, 26, 97, 241, 2521, 16022, 26603, 39343, 104659, 248407, 506509, 584213, 2560177, 4036967, 4417813, 5167587, 9725107, 25045771, 27489679, 70416259, 111555371, 174266683, 359589563, 1075714923, 6820213333, 15378035161, 16598109467, 19423306039, 30133946677, 74466436042

Offset: 1

Bobby Jacobs, Nov 12 2016

nonn

This sequence is infinite, since the asymptotic density of the primes and semiprimes is 0. - Charles R Greathouse IV, Nov 12 2016

			a(5) = 241 because the next prime or semiprime after 241 is 247, and that is a record gap of size 6.

Giovanni Resta, Table of n, a(n) for n = 1..37 (terms < 10^13)

Cf. A037143, A111087, A275014, A275108.

r=0; last=2; for(n=3,1e9, if(bigomega(n)<3, if(n-last>r, r=n-last; print1(last", ")); last=n)) \\ Charles R Greathouse IV, Nov 12 2016

checkrange(a,b,r)=while(b-a>r, forstep(n=a+r, a+1, -1, if(bigomega(n)<3, a=n; next(2))); for(n=a+r+1,b, if(bigomega(n)<3, return([a,n])))); 0
print1(2); p=5; r=1; forprime(q=7,1e9, if(q-p<=r, p=q; next); t=checkrange(p,q,r); while(t!=0, print1(", "t[1]); t=checkrange(t[2],q,r=t[2]-t[1])); p=q) \\ Charles R Greathouse IV, Nov 12 2016

a(n) = A275014(n) - A275108(n).

a(7)-a(31) from Charles R Greathouse IV, Nov 12 2016

A275014 Upper ends of record gaps between numbers that are either primes or semiprimes.

Original entry on oeis.org

3, 9, 29, 101, 247, 2531, 16033, 26615, 39359, 104677, 248426, 506531, 584237, 2560202, 4036993, 4417843, 5167619, 9725141, 25045807, 27489719, 70416301, 111555415, 174266734, 359589619, 1075714987, 6820213399, 15378035231, 16598109538, 19423306117, 30133946758, 74466436127

Offset: 1

Bobby Jacobs, Nov 12 2016

nonn

This sequence is infinite, since the asymptotic density of the primes and semiprimes is 0. - Charles R Greathouse IV, Nov 12 2016

			a(5) = 247 because the next prime or semiprime after 241 is 247, and that is a record gap of size 6.

Giovanni Resta, Table of n, a(n) for n = 1..37 (terms < 10^13)

Cf. A037143, A111087, A275013, A275108.

r=0; last=2; for(n=3, 1e9, if(bigomega(n)<3, if(n-last>r, r=n-last; print1(n", ")); last=n)) \\ Charles R Greathouse IV, Nov 12 2016

checkrange(a, b, r)=while(b-a>r, forstep(n=a+r, a+1, -1, if(bigomega(n)<3, a=n; next(2))); for(n=a+r+1, b, if(bigomega(n)<3, return([a, n])))); 0
print1(3); p=5; r=1; forprime(q=7, 1e9, if(q-p<=r, p=q; next); t=checkrange(p, q, r); while(t!=0, print1(", "t[2]); t=checkrange(t[2], q, r=t[2]-t[1])); p=q) \\ Charles R Greathouse IV, Nov 12 2016

a(n) = A275013(n) + A275108(n).

a(7)-a(31) from Charles R Greathouse IV, Nov 12 2016

A098962 Smallest sequence such that over all terms each prime p occurs exactly p times as prime factor; a(1)=1.

Original entry on oeis.org

1, 2, 3, 5, 6, 7, 11, 13, 15, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 91, 97, 101, 103, 107, 109, 113, 119, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209, 211

Offset: 1

Reinhard Zumkeller, Oct 22 2004

nonn

A000040 is a subsequence.
A099619 gives k such that a(k) = n-th prime; A099620 gives the greatest term divisible by the n-th prime.
A001222(a(n)) <= 2.

			p=2: a(2)=2, a(5)=6=2*3: 4=2*2 is missing, otherwise 2 would occur more than 2 times, there are no more even terms greater than 6;
p=3: a(3)=3, a(5)=6=2*3, a(9)=15=3*5: 9=3*3 is missing, otherwise 3 would occur more than 3 times, there are no more multiples of 3 greater than 15;
p=5: a(4)=5, a(9)=15=3*5, a(13)=25=5*5, a(16)=35=5*7: no more multiples of 5 greater than 35;
p=7: a(6)=7, a(16)=35=5*7, a(21)=49=7*7, a(28)=77=7*11, a(32)=91=7*13, a(39)=119=7*17: no more multiples of 7 greater than 119.
- _Reinhard Zumkeller_, Feb 17 2013

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

Cf. A020639, A008578, A005145, subsequence of A037143.

import Data.List (delete)
a098962 n = a098962_list !! (n-1)
a098962_list = 1 : f [2..] (tail a175944_list) where
   f xs'@(x:xs) ps'@(p:ps)
     | a010051 x == 1    = x : f xs (delete x ps')
     | u == q && v == q' = x : f xs' zs
     | otherwise         = f xs ps'
     where q = a020639 x; q' = div x q
           (us, u:us') = span (< q) ps'
           (vs, v:vs') = span (< q') us'
           zs@(z:_) = us ++ vs ++ vs'
           xs' = if z == p then xs else filter ((> 0) . (`mod` p)) xs
-- Reinhard Zumkeller, Feb 17 2013

#{(n,k): A027746(a(n),k)=p, 1<=k<=A001222(a(n))} = p for all primes p. - Reinhard Zumkeller, Feb 17 2013

A275108 Record gaps between numbers that are either primes or semiprimes.

Original entry on oeis.org

1, 2, 3, 4, 6, 10, 11, 12, 16, 18, 19, 22, 24, 25, 26, 30, 32, 34, 36, 40, 42, 44, 51, 56, 64, 66, 70, 71, 78, 81, 85, 86, 91, 106, 110, 112, 128

Offset: 1

Bobby Jacobs, Nov 13 2016

			a(5) = 6 because the next prime or semiprime after 241 is 247, and that is a record gap of size 6.

Cf. A037143, A111087, A275013, A275014.

checkrange(a, b, r)=while(b-a>r, forstep(n=a+r, a+1, -1, if(bigomega(n)<3, a=n; next(2))); for(n=a+r+1, b, if(bigomega(n)<3, return([a, n])))); 0
print1(1); p=5; r=1; forprime(q=7, 1e9, if(q-p<=r, p=q; next); t=checkrange(p, q, r); while(t, print1(", "t[2]-t[1]); t=checkrange(t[2], q, r=t[2]-t[1])); p=q) \\ Charles R Greathouse IV, Nov 19 2016

a(n) = A275014(n) - A275013(n).

a(32)-a(37) from Giovanni Resta, Apr 25 2020

A166718 Numbers with at most 4 prime factors (counted with multiplicity).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 73, 74, 75, 76

Offset: 1

Michael B. Porter, Oct 20 2009

Complement of A046304, A001222(a(n)) <= 4.
Maynard shows there are infinitely many integers n such that the interval [n,n+90] contains 2 primes and a number with at most 4 prime factors [Jonathan Vos Post, May 23 2012]
Subset of the 5-free numbers (numbers where each exponent in the prime factorization is <=4). - R. J. Mathar, Aug 08 2012

			88 = 2*2*2*11 is in the sequence since it has 4 prime factors
72 = 2*2*2*3*3 is not in the sequence since it has 5 prime factors

G. C. Greubel, Table of n, a(n) for n = 1..10000
James Maynard, Bounded length intervals containing two primes and an almost-prime, arXiv:1205.5020v1 [math.NT], May 22 2012

Cf. A046304, A001222

For numbers with at most n prime factors: n=1: A000040, n=2: A037143, n=3: A037144, n=5: A166719

Select[Range[100],PrimeOmega[#]<= 4 &] (* G. C. Greubel, May 24 2016 *)

PARI
```
isA166718(n) = (bigomega(n) <= 4)
```

UNION of A000040, A001358, A014612, and A014613. - R. J. Mathar, Aug 08 2012

A276825 Number of ways to write n as x^3 + P_2, where x and P_2 are positive integers with P_2 a product of at most two primes.

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 2, 3, 2, 2, 2, 3, 1, 2, 2, 2, 2, 2, 2, 3, 1, 2, 1, 2, 2, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 2, 2, 2, 2, 1, 3, 4, 2, 3, 2, 4, 1, 1, 3, 3, 3, 1, 2, 3, 2, 2

Offset: 1

Zhi-Wei Sun, Sep 19 2016

nonn

Conjecture: Any integer n > 1 can be written as x^3 + P_2, where x and P_2 are positive integers with P_2 a product of at most two primes.
We have verified this for n up to 10^8, and we guess that a(n) > 1 for all n > 3275.
It seems that any integer n > 1 also can be written as x^2 + P_2, where x and P_2 are positive integers with P_2 a product of at most two primes. Goldbach's conjecture implies that for each integer n > 1 we can write 2*n as p + q with p <= n and q >= n both prime, and hence n^2 - (n-p)^2 = p*(2n-p) = p*q is a product of two primes. In 1923 Hardy and Littlewood conjectured that if an integer n is large enough and not a square then it can be written as the sum of a prime and a square.

			a(7) = 1 since 7 = 1^3 + 2*3 with 2 and 3 both prime.
a(17) = 1 since 17 = 2^3 + 3^2 with 3 prime.
a(28) = 1 since 28 = 3^3 + 1.
a(76) = 1 since 76 = 3^3 + 7^2 with 7 prime.
a(995) = 1 since 995 = 6^3 + 19*41 with 19 and 41 both prime.
a(1072) = 1 since 1072 = 5^3 + 947 with 947 prime.
a(1252) = 1 since 1252 = 9^3 + 523 with 523 prime.
a(1574) = 1 since 1574 = 7^3 + 1231 with 1231 prime.
a(1637) = 1 since 1637 = 7^3 + 2*647 with 2 and 647 both prime.
a(2458) = 1 since 2458 = 5^3 + 2333 with 2333 prime.
a(2647) = 1 since 2647 = 12^3 + 919 with 919 prime.
a(2752) = 1 since 2752 = 5^3 + 37*71 with 37 and 71 both prime.
a(2764) = 1 since 2764 = 11^3 + 1433 with 1433 prime.
a(3275) = 1 since 3275 = 1^3 + 2*1637 with 2 and 1637 both prime.

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
G. H. Hardy and J. E. Littlewood, Some problems of 'Partitio numerorum'; III: on the expression of a number as a sum of primes, Acta Mathematica, Vol. 44, pp. 1-70, 1923.

Cf. A000040, A000290, A000578, A037143, A045917, A235645.

P2[n_]:=P2[n]=PrimeQ[Sqrt[n]]||(SquareFreeQ[n]&&Length[FactorInteger[n]]<=2)
Do[r=0;Do[If[P2[n-k^3],r=r+1],{k,1,(n-1)^(1/3)}];Print[n," ",r];Continue,{n,1,80}]

A283267 Smallest b-a such that a < prime(n) < b, where a,b are semiprimes.

Original entry on oeis.org

2, 3, 4, 4, 6, 6, 3, 7, 7, 3, 7, 7, 3, 4, 4, 4, 4, 5, 5, 5, 3, 4, 11, 11, 11, 5, 5, 4, 6, 4, 7, 7, 9, 9, 3, 5, 3, 8, 5, 5, 7, 7, 7, 7, 4, 5, 9, 9, 9, 10, 10, 4, 5, 3, 7, 7, 4, 9, 9, 4, 4, 5, 5, 5, 5, 4, 9, 9, 9, 3, 6, 6, 4, 4, 5, 3, 5, 4, 5, 5, 10, 10, 8, 8, 4

Offset: 3

Vladimir Shevelev, Mar 04 2017

nonn

This is the first sequence from the series of sequences: "Smallest b-a such that a < prime(n)^k < b, where a,b are semiprimes", k = 1, 2, 3, ... .
This series of sequences was inspired by Zak Seidov's message to Seqfans (Mar 02 2017) where he suggested listing the triples of primes squared with neighbor semiprimes.
There are no semiprimes below prime(2) = 3 but there are below prime(3) = 5 so the offset is 3. - David A. Corneth, Mar 04 2017
From Michael De Vlieger, Mar 04 2017: (Start)
Largest term in range a(3)..a(10^m): {7, 11, 24, 38, 54, 74, ...}.
Largest term in range a(3)..a(2^m), m>1: {3, 6, 7, 11, 11, 14, 19, 20, 24, 25, 38, 38, 38, 47, 47, 55, 70, 74, ...}.
Largest run in range a(3)..a(10^m): {2, 4, 6, 8, 10, 12, ...}.
Largest run in range a(3)..a(2^m), m>1: {1, 2, 2, 4, 4, 4, 4, 5, 6, 7, 7, 8, 8, 10, 10, 10, 12, 12, ...}. (End)

			For a(3), the largest semiprime below 5 is 4. The least semiprime above 5 is 6. Therefore, (a, b) = (4, 6) giving a(3) = 6 - 4 = 2. - _David A. Corneth_, Mar 04 2017

Charles R Greathouse IV, Table of n, a(n) for n = 3..10000

Cf. A000040, A001358, A037143.

Table[Module[{p = Prime@ n, a, b}, a = p - 1; b = p + 1; While[PrimeOmega@ a != 2, a--]; While[PrimeOmega@ b != 2, b++]; b - a], {n, 3, 120}] (* Michael De Vlieger, Mar 04 2017 *)

issemi(n)=bigomega(n)==2
a(n,p=prime(n))=my(a=p,b=p); while(!issemi(a--), ); while(!issemi(b++), ); b-a \\ Charles R Greathouse IV, Mar 04 2017

a(n) = A102414(n) - A102415(n). - Michel Marcus, Mar 04 2017

More terms from Peter J. C. Moses, Mar 04 2017

A336530 Number of triples of divisors d_i < d_j < d_k of n such that gcd(d_i, d_j, d_k) > 1.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 5, 0, 0, 0, 4, 0, 5, 0, 5, 0, 0, 0, 23, 0, 0, 1, 5, 0, 12, 0, 10, 0, 0, 0, 36, 0, 0, 0, 23, 0, 12, 0, 5, 5, 0, 0, 62, 0, 5, 0, 5, 0, 23, 0, 23, 0, 0, 0, 87, 0, 0, 5, 20, 0, 12, 0, 5, 0, 12, 0, 120, 0, 0, 5, 5, 0, 12, 0, 62, 4

Offset: 1

Michel Lagneau, Oct 04 2020

nonn

Number of elements in the set {(x, y, z): x|n, y|n, z|n, x < y < z, GCD(x, y, z) > 1}.
Every element of the sequence is repeated indefinitely, for instance:
a(n) = 0 for n = 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, ... (Numbers with at most 2 prime factors (counted with multiplicity). See A037143);
a(n) = 1 for n = 8, 27, 125, 343, 1331, 2197, 4913,... (cubes of primes. See A030078);
a(n) = 4 for n = 16, 81, 625, 2401, 14641, 28561, ... (prime(n)^4. See A030514);
a(n) = 5 for n = 12, 18, 20, 28, 44, 45, ... (Numbers which are the product of a prime and the square of a different prime (p^2 * q). See A054753);
a(n) = 12 for n = 30, 42, 66, 70, 78, 102, 105, 110,... (Sphenic numbers: products of 3 distinct primes. See A007304);
a(n) = 20 for n = 64, 729, 15625, 117649, ... (Numbers with 7 divisors. 6th powers of primes. See A030516);
a(n) = 23 for n = 24, 40, 54, 56, 88, 104, 135, 136, ... (Product of the cube of a prime (A030078) and a different prime. See A065036);
a(n) = 36 for n = 36, 100, 196, 225, 441, 484, 676,... (Squares of the squarefree semiprimes (p^2*q^2). See A085986);
a(n) = 62 for n = 48, 80, 112, 162, 176, 208, 272, ... (Product of the 4th power of a prime (A030514) and a different prime (p^4*q). See A178739);
a(n) = 87 for n = 60, 84, 90, 126, 132, 140, 150, 156, ... (Product of exactly four primes, three of which are distinct (p^2*q*r). See A085987);
a(n) = 120 for n = 72, 108, 200, 392, 500, 675, 968, ... (Numbers of the form p^2*q^3, where p,q are distinct primes. See A143610);
It is possible to continue with a(n) = 130, 235, 284, 289, 356, ...

			a(12) = 5 because the divisors of 12 are {1, 2, 3, 4, 6, 12} and GCD(d_i, d_j, d_k) > 1 for the 5 following triples of divisors: (2,4,6), (2,4,12), (2,6,12), (3,6,12) and (4,6,12).

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

Cf. A275387.

with(numtheory):nn:=100:
for n from 1 to nn do:
it:=0:d:=divisors(n):n0:=nops(d):
  for i from 1 to n0-2 do:
   for j from i+1 to n0-1 do:
     for k from j+1 to n0 do:
    if igcd(d[i],d[j],d[k])> 1
       then
       it:=it+1:
       else
      fi:
     od:
     od:
     od:
    printf(`%d, `,it):
   od:

Array[Count[GCD @@ # & /@ Subsets[Divisors[#], {3}], ?(# > 1 &)] &, 81] (* _Michael De Vlieger, Oct 05 2020 *)

a(n) = my(d=divisors(n)); sum(i=1, #d-2, sum (j=i+1, #d-1, sum (k=j+1, #d, gcd([d[i], d[j], d[k]]) > 1))); \\ Michel Marcus, Oct 31 2020

a(n) = {my(f = factor(n), vp = vecprod(f[,1]), d = divisors(vp), res = 0);
for(i = 2, #d, res-=binomial(numdiv(n/d[i]), 3)*(-1)^omega(d[i])); res} \\ David A. Corneth, Nov 01 2020

Name clarified by editors, Oct 31 2020

cp's OEIS Frontend

A101049 Number of partitions of n into parts having at most two prime-factors.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A129597 Central diagonal of array A129595.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A275013 Lower ends of record gaps between numbers that are either primes or semiprimes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

Extensions

A275014 Upper ends of record gaps between numbers that are either primes or semiprimes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

Extensions

A098962 Smallest sequence such that over all terms each prime p occurs exactly p times as prime factor; a(1)=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Formula

A275108 Record gaps between numbers that are either primes or semiprimes.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

Extensions

A166718 Numbers with at most 4 prime factors (counted with multiplicity).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula