cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-8 of 8 results.

A001221 Number of distinct primes dividing n (also called omega(n)).

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 1, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 3, 1, 2, 2, 1, 2, 3, 1, 2, 2, 3, 1, 2, 1, 2, 2, 2, 2, 3, 1, 2, 1, 2, 1, 3, 2, 2, 2, 2, 1, 3, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 1, 2, 3, 2, 1, 2, 1, 3, 2
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

From Peter C. Heinig (algorithms(AT)gmx.de), Mar 08 2008: (Start)
This is also the number of maximal ideals of the ring (Z/nZ,+,*). Since every finite integral domain must be a field, every prime ideal of Z/nZ is a maximal ideal and since in general each maximal ideal is prime, there are just as many prime ideals as maximal ones in Z/nZ, so the sequence gives the number of prime ideals of Z/nZ as well.
The reason why this number is given by the sequence is that the ideals of Z/nZ are precisely the subgroups of (Z/nZ,+). Hence for an ideal to be maximal it has form a maximal subgroup of (Z/nZ,+) and this is equivalent to having prime index in (Z/nZ) and this is equivalent to being generated by a single prime divisor of n.
Finally, all the groups arising in this way have different orders, hence are different, so the number of maximal ideals equals the number of distinct primes dividing n. (End)
Equals double inverse Mobius transform of A143519, where A051731 = the inverse Mobius transform. - Gary W. Adamson, Aug 22 2008
a(n) is the number of unitary prime power divisors of n (not including 1). - Jaroslav Krizek, May 04 2009 [corrected by Ilya Gutkovskiy, Oct 09 2019]
Sum_{d|n} 2^(-A001221(d) - A001222(n/d)) = Sum_{d|n} 2^(-A001222(d) - A001221(n/d)) = 1 (see Dressler and van de Lune link). - Michel Marcus, Dec 18 2012
Up to 2*3*5*7*11*13*17*19*23*29 - 1 = 6469693230 - 1, also the decimal expansion of the constant 0.01111211... = Sum_{k>=0} 1/(10 ^ A000040(k) - 1) (see A073668). - Eric Desbiaux, Jan 20 2014
The average order of a(n): Sum_{k=1..n} a(k) ~ Sum_{k=1..n} log log k. - Daniel Forgues, Aug 13-16 2015
From Peter Luschny, Jul 13 2023: (Start)
We can use A001221 and A001222 to classify the positive integers as follows.
A001222(n) = A001221(n) = 0 singles out {1}.
Restricting to n > 1:
A001222(n)^A001221(n) = 1: A000040, prime numbers.
A001221(n)^A001222(n) = 1: A246655, prime powers.
A001222(n)^A001221(n) > 1: A002808, the composite numbers.
A001221(n)^A001222(n) > 1: A024619, complement of A246655.
n^(A001222(n) - A001221(n)) = 1: A144338, products of distinct primes. (End)
Inverse Möbius transform of the characteristic function of primes (A010051). - Wesley Ivan Hurt, Jun 22 2024
Dirichlet convolution of A010051(n) and 1. - Wesley Ivan Hurt, Jul 15 2025

References

  • M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 844.
  • G. H. Hardy, Ramanujan: twelve lectures on subjects suggested by his life and work, Cambridge, University Press, 1940, pp. 48-57.
  • J. Peters, A. Lodge and E. J. Ternouth, E. Gifford, Factor Table (n<100000) (British Association Mathematical Tables Vol.V), Burlington House/Cambridge University Press London 1935.
  • 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).

Links

Crossrefs

Cf. A001222 (primes counted with multiplicity), A046660, A285577, A346617. Partial sums give A013939.
Cf. also A125666, A069010, A087624, A091202, A091221, A143519, A144494, A158210, A156542, A156552, A000010, A008683.
Sum of the k-th powers of the primes dividing n for k=0..10: this sequence (k=0), A008472 (k=1), A005063 (k=2), A005064 (k=3), A005065 (k=4), A351193 (k=5), A351194 (k=6), A351195 (k=7), A351196 (k=8), A351197 (k=9), A351198 (k=10).
Sequences of the form n^k * Sum_{p|n, p prime} 1/p^k for k=0..10: this sequence (k=0), A069359 (k=1), A322078 (k=2), A351242 (k=3), A351244 (k=4), A351245 (k=5), A351246 (k=6), A351247 (k=7), A351248 (k=8), A351249 (k=9), A351262 (k=10).

Programs

  • Haskell
    import Math.NumberTheory.Primes.Factorisation (factorise)
a001221 = length . snd . unzip . factorise
-- Reinhard Zumkeller, Nov 28 2015
  • Julia
    using Nemo
function NumberOfPrimeFactors(n; distinct=true)
    distinct && return length(factor(ZZ(n)))
    sum(e for (p, e) in factor(ZZ(n)); init=0)
end
println([NumberOfPrimeFactors(n) for n in 1:60]) # Peter Luschny, Jan 02 2024
  • Magma
    [#PrimeDivisors(n): n in [1..120]]; // Bruno Berselli, Oct 15 2021
  • Maple
    A001221 := proc(n) local t1, i; if n = 1 then return 0 else t1 := 0; for i to n do if n mod ithprime(i) = 0 then t1 := t1 + 1 end if end do end if; t1 end proc;
A001221 := proc(n) nops(numtheory[factorset](n)) end proc: # Emeric Deutsch
omega := n -> NumberTheory:-NumberOfPrimeFactors(n, 'distinct'): # Peter Luschny, Jun 15 2025
  • Mathematica
    Array[ Length[ FactorInteger[ # ] ]&, 100 ]
PrimeNu[Range[120]]  (* Harvey P. Dale, Apr 26 2011 *)
  • MuPAD
    func(nops(numlib::primedivisors(n)), n):
  • MuPAD
    numlib::omega(n)$ n=1..110 // Zerinvary Lajos, May 13 2008
  • PARI
    a(n)=omega(n)
  • Python
    from sympy.ntheory import primefactors
print([len(primefactors(n)) for n in range(1, 1001)])  # Indranil Ghosh, Mar 19 2017
  • Sage
    def A001221(n): return sum(1 for p in divisors(n) if is_prime(p))
[A001221(n) for n in (1..80)] # Peter Luschny, Feb 01 2012
  • SageMath
    [sloane.A001221(n) for n in (1..111)] # Giuseppe Coppoletta, Jan 19 2015
  • SageMath
    [gp.omega(n) for n in range(1,101)] # G. C. Greubel, Jul 13 2024

Formula

G.f.: Sum_{k>=1} x^prime(k)/(1-x^prime(k)). - Benoit Cloitre, Apr 21 2003; corrected by Franklin T. Adams-Watters, Sep 01 2009
Dirichlet generating function: zeta(s)*primezeta(s). - Franklin T. Adams-Watters, Sep 11 2005
Additive with a(p^e) = 1.
a(1) = 0, a(p) = 1, a(pq) = 2, a(pq...z) = k, a(p^k) = 1, where p, q, ..., z are k distinct primes and k natural numbers. - Jaroslav Krizek, May 04 2009
a(n) = log_2(Sum_{d|n} mu(d)^2). - Enrique Pérez Herrero, Jul 09 2012
a(A002110(n)) = n, i.e., a(prime(n)#) = n. - Jean-Marc Rebert, Jul 23 2015
a(n) = A091221(A091202(n)) = A069010(A156552(n)). - Antti Karttunen, circa 2004 & Mar 06 2017
L.g.f.: -log(Product_{k>=1} (1 - x^prime(k))^(1/prime(k))) = Sum_{n>=1} a(n)*x^n/n. - Ilya Gutkovskiy, Jul 30 2018
a(n) = log_2(Sum_{k=1..n} mu(gcd(n,k))^2/phi(n/gcd(n,k))) = log_2(Sum_{k=1..n} mu(n/gcd(n,k))^2/phi(n/gcd(n,k))), where phi = A000010 and mu = A008683. - Richard L. Ollerton, May 13 2021
Sum_{k=1..n} 2^(-a(gcd(n,k)) - A001222(n/gcd(n,k)))/phi(n/gcd(n,k)) = Sum_{k=1..n} 2^(-A001222(gcd(n,k)) - a(n/gcd(n,k)))/phi(n/gcd(n,k)) = 1, where phi = A000010. - Richard L. Ollerton, May 13 2021
a(n) = A005089(n) + A005091(n) + A059841(n) = A005088(n) +A005090(n) +A079978(n). - R. J. Mathar, Jul 22 2021
From Wesley Ivan Hurt, Jun 22 2024: (Start)
a(n) = Sum_{p|n, p prime} 1.
a(n) = Sum_{d|n} c(d), where c = A010051. (End)

A013939 Partial sums of sequence A001221 (number of distinct primes dividing n).

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 14, 15, 17, 19, 20, 21, 23, 24, 26, 28, 30, 31, 33, 34, 36, 37, 39, 40, 43, 44, 45, 47, 49, 51, 53, 54, 56, 58, 60, 61, 64, 65, 67, 69, 71, 72, 74, 75, 77, 79, 81, 82, 84, 86, 88, 90, 92, 93, 96, 97, 99, 101, 102, 104, 107, 108, 110, 112
Offset: 1

Views

Author

N. J. A. Sloane, Henri Lifchitz

Keywords

Links

Crossrefs

Cf. A005187, A006218, A011371, A013936.
Cf. A093614, A048865, A006218.
Cf. A027748, A000040, A082287.
Cf. A022559.
Cf. A077761.
Cf. A346617.
Cf. A001222, A048803.

Programs

  • Haskell
    a013939 n = a013939_list !! (n-1)
a013939_list = scanl1 (+) $ map a001221 [1..]
-- Reinhard Zumkeller, Feb 16 2012
  • Magma
    [(&+[Floor(n/NthPrime(k)): k in [1..n]]): n in [1..70]]; // G. C. Greubel, Nov 24 2018
  • Maple
    A013939 := proc(n) option remember;  `if`(n = 1, 0, a(n) + iquo(n+1, ithprime(n+1))) end:
seq(A013939(i), i = 1..69);  # Peter Luschny, Jul 16 2011
  • Mathematica
    a[n_] := Sum[Floor[n/Prime[k]], {k, 1, n}]; Table[a[n], {n, 1, 69}] (* Jean-François Alcover, Jun 11 2012, from 2nd formula *)
Accumulate[PrimeNu[Range[120]]] (* Harvey P. Dale, Jun 05 2015 *)
  • PARI
    t=0;vector(99,n,t+=omega(n)) \\ Charles R Greathouse IV, Jan 11 2012
  • PARI
    a(n)=my(s);forprime(p=2,n,s+=n\p);s \\ Charles R Greathouse IV, Jan 11 2012
  • PARI
    a(n) = sum(k=1, sqrtint(n), k * (primepi(n\k) - primepi(n\(k+1)))) + sum(k=1, n\(sqrtint(n)+1), if(isprime(k), n\k, 0)); \\ Daniel Suteu, Nov 24 2018
  • Python
    from sympy.ntheory import primefactors
print([sum(len(primefactors(k)) for k in range(1,n+1)) for n in range(1, 121)]) # Indranil Ghosh, Mar 19 2017
  • Python
    from sympy import primerange
def A013939(n): return sum(n//p for p in primerange(n+1)) # Chai Wah Wu, Oct 06 2024
  • Sage
    [sum(floor(n/nth_prime(k)) for k in (1..n)) for n in (1..70)] # G. C. Greubel, Nov 24 2018

Formula

a(n) = Sum_{k <= n} omega(k).
a(n) = Sum_{k = 1..n} floor( n/prime(k) ).
a(n) = a(n-1) + A001221(n).
a(n) = A093614(n) - A048865(n); see also A006218.
A027748(a(A000040(n))+1) = A000040(n), A082287(a(n)+1) = n.
a(n) = Sum_{k=1..n} pi(floor(n/k)). - Vladeta Jovovic, Jun 18 2006
a(n) = n log log n + O(n). - Charles R Greathouse IV, Jan 11 2012
a(n) = n*(log log n + B) + o(n), where B = 0.261497... is the Mertens constant A077761. - Arkadiusz Wesolowski, Oct 18 2013
G.f.: (1/(1 - x))*Sum_{k>=1} x^prime(k)/(1 - x^prime(k)). - Ilya Gutkovskiy, Jan 02 2017
a(n) = Sum_{k=1..floor(sqrt(n))} k * (pi(floor(n/k)) - pi(floor(n/(k+1)))) + Sum_{p prime <= floor(n/(1+floor(sqrt(n))))} floor(n/p). - Daniel Suteu, Nov 24 2018
a(n) = Sum_{k>=1} k * A346617(n,k). - Alois P. Heinz, Aug 19 2021
a(n) = A001222(A048803(n+1)). - Flávio V. Fernandes, Jan 14 2025

Extensions

More terms from Henry Bottomley, Jul 03 2001

A174863 Little omega analog to Liouville's function L(n).

Original entry on oeis.org

1, 0, -1, -2, -3, -2, -3, -4, -5, -4, -5, -4, -5, -4, -3, -4, -5, -4, -5, -4, -3, -2, -3, -2, -3, -2, -3, -2, -3, -4, -5, -6, -5, -4, -3, -2, -3, -2, -1, 0, -1, -2, -3, -2, -1, 0, -1, 0, -1, 0, 1, 2, 1, 2, 3, 4, 5, 6, 5, 4, 3, 4, 5, 4, 5, 4, 3, 4, 5, 4, 3, 4, 3, 4, 5, 6, 7
Offset: 1

Views

Author

Alonso del Arte, Dec 01 2010

Keywords

Comments

Instead of using the Omega function, number of prime factors counted with multiplicity, this is using the omega function, number of distinct prime factors.
Except for the two zeros and the intervening foray into negative territory shown here, the first thousand terms are all positive. The next zero occurs at term 7960. After the zero at term 12100, the function stays negative until term 22395666.
This sequence and the Liouville sequence have some terms up to a(43) exactly the same. I don't know at what higher point (if any) that is the case again. [del Arte]
It appears certain that this sequence and the Liouville sequence are equal infinitely often. Because they have the same parity and always change by one, they cannot cross without meeting. Both change signs infinitely often, and at apparently unrelated points. - Franklin T. Adams-Watters, Aug 05 2011

Examples

			a(4) = -2 because: a(1) = 1, as 1 has an even number of prime factors; then 2 and 3 being prime, bring the running sum down to -1; and then 4, which has one distinct prime factor, brings the sum down to -2. (This is the first term that differs from the Mertens function and Liouville's function.)

Links

Crossrefs

Partial sums of A076479. - Reinhard Zumkeller, Jun 01 2013
Cf. A002819 (Liouville's function), A002321 (Mertens's function), A275547 (where a(n) is zero).
Cf. A346617.

Programs

  • Haskell
    a174863 n = a174863_list !! (n-1)
a174863_list = scanl1 (+) a076479_list
-- Reinhard Zumkeller, Jun 01 2013
  • Mathematica
    s=0; Table[s=s+(-1)^PrimeNu[n]; s, {n, 100}] (* PrimeNu is new in Mathematica 7.0 *)
  • PARI
    a(n)=sum(k=1,n,(-1)^omega(k)) \\ Charles R Greathouse IV, Mar 27 2012
  • PARI
    a(n)=my(v=vectorsmall(n, i, 1)); forprime(p=2, n, forstep(i=p, n, p, v[i]*=-1)); sum(i=1, #v, v[i]) \\ Charles R Greathouse IV, Aug 21 2016
  • Python
    from sympy import primefactors
def omega(n): return 0 if n==1 else len(primefactors(n))
def a(n): return sum([(-1)**omega(i) for i in range(1, n + 1)]) # Indranil Ghosh, May 20 2017

Formula

a(n) = Sum_{i = 1..n} (-1)^omega(i).
A275547(a(n)) = 0. - Alois P. Heinz, Aug 03 2016
From Ridouane Oudra, Dec 31 2020: (Start)
a(n) = Sum_{i=1..n} Sum_{j=1..n} mu(i*j)*floor(n/(i*j));
a(n) = Sum_{i=1..n} mu(i)*tau(i)*floor(n/i);
a(n) = Sum_{i=1..n} 2^Omega(i)*mu(i)*floor(n/i), where Omega = A001222. (End)
From Amiram Eldar, Mar 05 2021: (Start)
a(n) ~ O(n * exp(-c*sqrt(log(n)))) (Schwarz, 1972).
a(n) ~ o(n) (van de Lune and Dressler, 1975). (End)
a(n) = 1 + Sum_{k>=1} (-1)^k * A346617(n,k). - Alois P. Heinz, Aug 19 2021

A123066 (Number of numbers <= n with an odd number of distinct prime factors) - (number of numbers <= n with an even number of distinct prime factors).

Original entry on oeis.org

0, 1, 2, 3, 4, 3, 4, 5, 6, 5, 6, 5, 6, 5, 4, 5, 6, 5, 6, 5, 4, 3, 4, 3, 4, 3, 4, 3, 4, 5, 6, 7, 6, 5, 4, 3, 4, 3, 2, 1, 2, 3, 4, 3, 2, 1, 2, 1, 2, 1, 0, -1, 0, -1, -2, -3, -4, -5, -4, -3, -2, -3, -4, -3, -4, -3, -2, -3, -4, -3, -2, -3, -2, -3, -4, -5, -6, -5, -4, -5, -4, -5, -4, -3, -4, -5, -6, -7, -6, -5, -6, -7, -8, -9, -10
Offset: 1

Views

Author

Franklin T. Adams-Watters, Sep 26 2006

Keywords

Comments

Analog of A072203 for number of distinct factors. Conjecture that sequence changes sign infinitely often, although the next sign change is probably large.
The signs first change at n = 52 and then change again at n = 7954. - Harvey P. Dale, Jul 04 2012

Links

Crossrefs

Cf. A030230, A030231.
Cf. A072203, A001221.
Cf. A346617.

Programs

  • Maple
    a:= proc(n) option remember; `if`(n<2, 0, a(n-1)+
      `if`(nops(ifactors(n)[2])::odd, 1, -1))
    end:
seq(a(n), n=1..120);  # Alois P. Heinz, Dec 21 2018
  • Mathematica
    dpf[n_] := Module[{df = PrimeNu[n]}, If[OddQ[df], 1, -1]]; Join[{0}, Accumulate[ Array[dpf, 100, 2]]] (* Harvey P. Dale, Jul 04 2012 *)
  • Python
    from sympy import primenu
def A123066(n): return 1+sum(1 if primenu(i)&1 else -1 for i in range(1,n+1)) # Chai Wah Wu, Dec 31 2022

Formula

a(n) = Sum_{k>=1} (-1)^(k-1) * A346617(n,k). - Alois P. Heinz, Aug 19 2021

A285577 Irregular triangle T(n,m) read by rows (n >= 1, 0 <= m <= Max(A001221([1..n]))), giving the number of integers in [1,n] with m distinct prime factors.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 1, 4, 1, 4, 1, 1, 5, 1, 1, 6, 1, 1, 7, 1, 1, 7, 2, 1, 8, 2, 1, 8, 3, 1, 9, 3, 1, 9, 4, 1, 9, 5, 1, 10, 5, 1, 11, 5, 1, 11, 6, 1, 12, 6, 1, 12, 7, 1, 12, 8, 1, 12, 9, 1, 13, 9, 1, 13, 10, 1, 14, 10, 1, 14, 11, 1, 15, 11, 1, 15, 12, 1, 16, 12
Offset: 1

Views

Author

Michel Marcus, Apr 22 2017

Keywords

Comments

A346617 is a similar triangle, except that the first column (corresponding to m = 0) has been omitted.

Examples

			First few rows are:
1;
1, 1;
1, 2;
1, 3;
1, 4;
1, 4, 1;
1, 5, 1;
1, 6, 1;
1, 7, 1;
1, 7, 2;
1, 8, 2;
...

Links

Crossrefs

Cf. A001221, A146289, A346617.

Programs

  • Maple
    omega := proc(n) nops(numtheory[factorset](n)) end proc: # # A001221
A:=Array(0..20,0);
ans:=[];
mx:=0;
for n from 1 to 20 do
k:=omega(n);
if k>mx then mx:=k; fi;
A[k]:=A[k]+1;
ans:=[op(ans),[seq(A[i],i=0..mx)]];
od:
ans; # N. J. A. Sloane, Aug 19 2021
  • Mathematica
    With[{nn = 29}, Function[s, Array[Function[t, Count[t, #] & /@ Range[0, Max@ t]]@ Take[s, #] &, nn]]@ PrimeNu@ Range@ nn] // Flatten (* Michael De Vlieger, Apr 23 2017 *)
  • PARI
    tabf(nn) = {for (n=1, nn, vo = vector(n, k, omega(k)); for (k=0, vecmax(vo), print1(#select(x->x==k, vo), ", ");); print(););}
  • PARI
    upto(n) = {my(res = [1], v=[1], i=2); while(#res#v, v=concat(v,[1]), v[o]++); res=concat(res,v); i++); res} \\ David A. Corneth, Apr 22 2017

Formula

See A346617 for the asymptotic distribution of the rows. - N. J. A. Sloane, Aug 19 2021

A069811 a(n) = Sum_{k=1..n} omega(k)^2.

Original entry on oeis.org

0, 1, 2, 3, 4, 8, 9, 10, 11, 15, 16, 20, 21, 25, 29, 30, 31, 35, 36, 40, 44, 48, 49, 53, 54, 58, 59, 63, 64, 73, 74, 75, 79, 83, 87, 91, 92, 96, 100, 104, 105, 114, 115, 119, 123, 127, 128, 132, 133, 137, 141, 145, 146, 150, 154, 158, 162, 166, 167, 176, 177, 181
Offset: 1

Views

Author

Benoit Cloitre, Apr 30 2002

Keywords

References

  • G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, Fifth edition, Oxford University Press, Chap. XXII, p. 357.

Links

Crossrefs

Equals (A074787(n)-1)/4 for n <= 29.
Cf. A001221, A346617.

Programs

  • Mathematica
    Accumulate@((PrimeNu@Range@62)^2) (* Ivan Neretin, Mar 16 2017 *)
  • PARI
    a(n) = sum(k=1, n, omega(k)^2); \\ Michel Marcus, Mar 16 2017

Formula

a(n) = Sum_{k=1..n} A001221(k)^2.
a(n) = n*log(log(n))^2 + O(n*log(log(n))) (Turán, 1934).
a(n) = Sum_{k>=1} k^2 * A346617(n,k). - Alois P. Heinz, Aug 19 2021

A358677 Irregular triangle where row n gives the columns of A340316 whose minimum value is in row n of A340316. The lists of column indices are given in abbreviated form, using pairs (x, y) to mean the range [x..y].

Original entry on oeis.org

1, 16, 18, 18, 21, 21, 17, 17, 19, 20, 22, 265549, 265604, 265605, 265608, 265681, 265683, 265829, 265831, 265831, 265835, 265836, 265850, 265850, 265853, 265853, 265862, 265873, 265550, 265603, 265606, 265607, 265682, 265682, 265830, 265830, 265832, 265834, 265837, 265849, 265851, 265852, 265854, 265861
Offset: 1

Views

Author

Michel Marcus, Dec 12 2022

Keywords

Comments

This sequence is a spin-off from old comments of A340316 (see history there).
Pending availability of tighter constraints, we assume that there are no more values in row n here only after we reach a column of A340316 where the value in A340316 row n is greater than the value in A340316 row n+2.
Presumably, using the results from Landau as they apply to A276176, it can similarly be shown that every row here is finite. - Peter Munn, Dec 20 2022

Examples

			First 2 rows are:
 {1..16, 18..18, 21..21} for [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,21];
 {17..17, 19..20, 22..265549, 265604..265605, 265608..265681, 265683..265829, 265831..265831, 265835..265836, 265850..265850, 265853..265853, 265862..265873}.
The A340316 first 2 rows being:
   1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
  -----------------------------------------------------------------
   2  3  5  7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79
   6 10 14 15 21 22 26 33 34 35 38 39 46 51 55 57 58 62 65 69 74 77
     the first columns that give row 2:           ^^    ^^ ^^    ^^
Row 3 begins: {265550..265603, 265606..265607, 265682..265682, 265830..265830, 265832..265834, ...

Crossrefs

Cf. A276176, A340316, A346617.

Programs

  • PARI
    showlist(list) = {my(slist = List()); listput(slist, list[1]); for (i=2, #list, if (list[i] != list[i-1]+1, listput(slist, list[i-1]); listput(slist, list[i]););); listput(slist, list[#list]); Vec(slist);}
primo(i) = factorback(primes(i));
ubound(nL, n) = {if (nL == 1, return(n*log(n) + n*log(log(n)))); if (nL == 2, return(n*log(n)/log(log(n)))); if (nL == 3, return(2*n*log(n)/log(log(n))^2)); if (nL == 4, return(3*n*log(n)/log(log(n))^3)); if (nL == 5, return(4*n*log(n)/log(log(n))^4));}
out(list1, list2, list3) = print(showlist(list1)); print(showlist(list2)); print(showlist(list3));
rows() = {my(nL = 3, nC = 1000000, nB=5); my(m=vector(nL, i, vector(nC))); my(vfirst = vector(nL, i, primo(i))); my(list1 = List(), list2 = List(), list3 = List()); for (nn=1, nB, my(ok=1); print("nn=", nn); for (i=1, nL, my(list = List()); my(na = vfirst[i]); my(ns = 1); if (nn==1, m[i][ns] = na; ns++); forsquarefree (k=na+1, 100*round(ubound(i,nn*nC)), if (omega(k[2]) == i, m[i][ns] = k[1]; ns++); if (ns > nC, break)); if (ns < nC, print("not enough"); out(list1, list2, list3); return;);); N = 1; for (j=1, nC, if (m[N][j] == vecmin (vector(nL, r, m[r][j])), listput(list1, j+(nn-1)*nC));); N = 2; for (j=1, nC, if (m[N][j] == vecmin (vector(nL, r, m[r][j])), listput(list2, j+(nn-1)*nC));); N = 3; for (j=1, nC, if (m[N][j] == vecmin (vector(nL, r, m[r][j])), listput(list3, j+(nn-1)*nC));); vfirst = vector(nL, i, m[i][nC]); for (i=1, nL, m[i] = vector(nC));); out(list1, list2, list3);}

Extensions

Provisional rule for calculating that row n is full added by Peter Munn, Jan 03 2023

A368210 Irregular triangle T(n,k) read by rows (n >= 1, 0 <= k <= max(A001222([1..n]))), giving the number of k-almost primes in [1,n].

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 1, 1, 3, 1, 1, 3, 2, 1, 4, 2, 1, 4, 2, 1, 1, 4, 3, 1, 1, 4, 4, 1, 1, 5, 4, 1, 1, 5, 4, 2, 1, 6, 4, 2, 1, 6, 5, 2, 1, 6, 6, 2, 1, 6, 6, 2, 1, 1, 7, 6, 2, 1, 1, 7, 6, 3, 1, 1, 8, 6, 3, 1, 1, 8, 6, 4, 1, 1, 8, 7, 4, 1, 1, 8, 8, 4, 1, 1, 9, 8, 4, 1
Offset: 1

Views

Author

Daniel Suteu, Dec 17 2023

Keywords

Comments

The smallest k-almost prime is 2^k, therefore the n-th row has 1+floor(log_2(n)) terms.

Examples

			First few rows are:
1;
1, 1;
1, 2;
1, 2, 1;
1, 3, 1;
1, 3, 2;
1, 4, 2;
1, 4, 2, 1;
1, 4, 3, 1;
1, 4, 4, 1;
...

Links

Crossrefs

Cf. A001222, A285577, A346617.

Programs

  • PARI
    tabf(nn) = for(n=1, nn, my(v=vector(n, j, bigomega(j))); for(k=0, vecmax(v), print1(#select(x->x==k, v), ", ")); print());
  • PARI
    almost_prime_count(n,k) = if(k==0, return(n>=1)); if(k==1, return(primepi(n))); (f(m, p, k, j=0)=my(s=sqrtnint(n\m, k), count=0); if(k==2, forprime(q=p, s, count += primepi(n\(m*q)) - j; j+=1); return(count)); forprime(q=p, s, count += f(m*q, q, k-1, j); j+=1); count); f(1, 2, k);
nth_row(n) = for(k=0, logint(n, 2), print1(almost_prime_count(n, k), ", "));
tabf(nn) = for(n=1, nn, nth_row(n); print());
upto(nn) = for(n=1, nn, nth_row(n));
  • Python
    from math import prod, isqrt
from sympy import primerange, integer_nthroot, primepi
def A368210_T(n,k):
    if k==0: return int(n>=1)
    def g(x,a,b,c,m): yield from (((d,) for d in enumerate(primerange(b,isqrt(x//c)+1),a)) if m==2 else (((a2,b2),)+d for a2,b2 in enumerate(primerange(b,integer_nthroot(x//c,m)[0]+1),a) for d in g(x,a2,b2,c*b2,m-1)))
    return int(sum(primepi(n//prod(c[1] for c in a))-a[-1][0] for a in g(n,0,1,1,k)) if k>1 else primepi(n)) # Chai Wah Wu, Sep 02 2024
Showing 1-8 of 8 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.