A013939 -id:A013939 - cp's OEIS frontend

A063971 Values of n for which A013939(n)/n is an integer.

1, 6, 7, 8, 9, 455, 457, 458, 459, 461, 8167302, 8167314, 8167315, 8167316, 8167328, 8167330, 8167335, 8167336, 8167346, 8167347, 8167348, 8167350, 8167351, 8167352, 8167410, 8167413

Offset: 1

Labos Elemer, Sep 05 2001

nonn

For 455, 457, 458, 459, 461 the quotient is 2. The cause of "step-like" appearance of terms is that the next integer is reached slowly with the summatory function A013939. Next "island" is expected above 500000. Similar phenomenon is observable in the analogous A050226 sequence too.
The quotients for "3rd island" after 8160000 equal 3. (Sep 21 2001)
a(27) > 10^13. - Giovanni Resta, Apr 24 2017

Cf. A013939, A050226, A001221, A064612.

s = 0; Do[s = s + Length[FactorInteger[n]]; If[IntegerQ[s/n], Print[n]], {n, 1, 10000000}]

More terms from Robert G. Wilson v, Sep 19 2001

A092604 Complement of A013939.

Original entry on oeis.org

5, 10, 13, 16, 18, 22, 25, 27, 29, 32, 35, 38, 41, 42, 46, 48, 50, 52, 55, 57, 59, 62, 63, 66, 68, 70, 73, 76, 78, 80, 83, 85, 87, 89, 91, 94, 95, 98, 100, 103, 105, 106, 109, 111, 113, 114, 117, 120, 122, 124, 126, 128, 129, 132, 135, 138, 139, 141, 143, 145, 147, 150

Offset: 1

Ali A. Tanara (tanara(AT)khayam.ut.ac.ir), Apr 10 2004

			a(6)=13 because 22 is the 6th smallest number that does not occur in A013939.

Georg Fischer, Table of n, a(n) for n = 1..14301 [first 3148 terms from _G. C. Greubel_]

Cf. A013939, A001221.

f[n_] := Sum[ Length[ FactorInteger[i]], {i, n}]; Complement[ Range[133], Table[ f[n] -1, {n, 70}]] (* Robert G. Wilson v, Apr 13 2004 *)

s=0;for(n=1,90,a=omega(n);for(j=1,a-1,print1(s,",");s++);s++) \\ Klaus Brockhaus, Apr 12 2004

More terms from Klaus Brockhaus, Apr 12 2004

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

N. J. A. Sloane

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

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).

N. J. A. Sloane and Daniel Forgues, Table of n, a(n) for n = 1..100000 (first 10000 from NJAS)
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Henry Bottomley, Prime factors calculator
J. Brennen, Prime Factoring Applet
J. Britton, Prime Factorization Machine
A. Dendane, Prime Factors Calculator
Robert E. Dressler and Jan van de Lune, Some remarks concerning the number theoretic functions omega and Omega, Proc. Amer. Math. Soc. 41 (1973), 403-406
J. Flament, Decomposition d'un nombre en facteurs premiers
G. H. Hardy and S. Ramanujan, The normal number of prime factors of a number, Quart. J. Math. 48 (1917), 76-92. Also Collected papers of Srinivasa Ramanujan, AMS Chelsea Publ., Providence, RI (2000): 262-275.
A. Hodges, Java Applet for Factorisation
M. Kac, Statistical Independence in Probability, Analysis and Number Theory, Carus Monograph 12, Math. Assoc. Amer., 1959, see p. 64.
S. O. S. Math, Prime factorization of the first 1000 integers
K. Matthews, Factorization and calculating phi(n),omega(n),d(n),sigma(n) and mu(n)
J. Moyer, "Prime Factors of Integers" server for numbers up to 10^36
Primefan, The First 2500 Integers,Factored
Primefan, Factorer
F. Richman, Factoring into Primes
Eric Weisstein's World of Mathematics, Distinct Prime Factors
Eric Weisstein's World of Mathematics, Moebius Transform
Eric Weisstein's World of Mathematics, Prime Factor
Eric Weisstein's World of Mathematics, Prime zeta function primezeta(s).
Wikipedia, Prime factor
Wikipedia, Table of prime factors
G. Xiao, WIMS server, Factoris
Index entries for "core" sequences
Index entries for sequences computed from exponents in factorization of n

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).

import Math.NumberTheory.Primes.Factorisation (factorise)
a001221 = length . snd . unzip . factorise
-- Reinhard Zumkeller, Nov 28 2015

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

[#PrimeDivisors(n): n in [1..120]]; // Bruno Berselli, Oct 15 2021

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

Array[ Length[ FactorInteger[ # ] ]&, 100 ]
PrimeNu[Range[120]]  (* Harvey P. Dale, Apr 26 2011 *)

func(nops(numlib::primedivisors(n)), n):

numlib::omega(n)$ n=1..110 // Zerinvary Lajos, May 13 2008

PARI
```
a(n)=omega(n)
```

from sympy.ntheory import primefactors
print([len(primefactors(n)) for n in range(1, 1001)])  # Indranil Ghosh, Mar 19 2017

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

[sloane.A001221(n) for n in (1..111)] # Giuseppe Coppoletta, Jan 19 2015

[gp.omega(n) for n in range(1,101)] # G. C. Greubel, Jul 13 2024

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)

A027748 Irregular triangle in which first row is 1, n-th row (n > 1) lists distinct prime factors of n.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane

Number of terms in n-th row is A001221(n) for n > 1.
From Reinhard Zumkeller, Aug 27 2011: (Start)
A008472(n) = Sum_{k=1..A001221(n)} T(n,k), n>1;
A007947(n) = Product_{k=1..A001221(n)} T(n,k);
A006530(n) = Max_{k=1..A001221(n)} T(n,k).
A020639(n) = Min_{k=1..A001221(n)} T(n,k).
(End)
Subsequence of A027750 that lists the divisors of n. - Michel Marcus, Oct 17 2015

			Triangle begins:
   1;
   2;
   3;
   2;
   5;
   2, 3;
   7;
   2;
   3;
   2, 5;
  11;
   2, 3;
  13;
   2, 7;
  ...

T. D. Noe, Rows n=1..2048 of triangle, flattened
Eric Weisstein's World of Mathematics, Distinct Prime Factors.

Cf. A000027, A001221, A001222 (with repetition), A027746, A141809, A141810.
a(A013939(A000040(n))+1) = A000040(n).
Cf. A020639, A027750.
A284411 gives column medians.

import Data.List (unfoldr)
a027748 n k = a027748_tabl !! (n-1) !! (k-1)
a027748_tabl = map a027748_row [1..]
a027748_row 1 = [1]
a027748_row n = unfoldr fact n where
   fact 1 = Nothing
   fact x = Just (p, until ((> 0) . (`mod` p)) (`div` p) x)
            where p = a020639 x  -- smallest prime factor of x
-- Reinhard Zumkeller, Aug 27 2011

with(numtheory): [ seq(factorset(n), n=1..100) ];

Flatten[ Table[ FactorInteger[n][[All, 1]], {n, 1, 62}]](* Jean-François Alcover, Oct 10 2011 *)

print1(1);for(n=2,20,f=factor(n)[,1];for(i=1,#f,print1(", "f[i]))) \\ Charles R Greathouse IV, Mar 20 2013

from sympy import primefactors
for n in range(2, 101):
    print([i for i in primefactors(n)]) # Indranil Ghosh, Mar 31 2017

More terms from Scott Lindhurst (ScottL(AT)alumni.princeton.edu)

A022559 Sum of exponents in prime-power factorization of n!.

Original entry on oeis.org

0, 0, 1, 2, 4, 5, 7, 8, 11, 13, 15, 16, 19, 20, 22, 24, 28, 29, 32, 33, 36, 38, 40, 41, 45, 47, 49, 52, 55, 56, 59, 60, 65, 67, 69, 71, 75, 76, 78, 80, 84, 85, 88, 89, 92, 95, 97, 98, 103, 105, 108, 110, 113, 114, 118, 120, 124, 126, 128, 129, 133, 134, 136, 139

Offset: 0

Karen E. Wandel (kw29(AT)evansville.edu)

Partial sums of Omega(n) (A001222). - N. J. A. Sloane, Feb 06 2022

			For n=5, 5! = 120 = 2^3*3^1*5^1 so a(5) = 3+1+1 = 5. - _N. J. A. Sloane_, May 26 2018

Daniel Forgues, Table of n, a(n) for n = 0..100000
Mehdi Hassani, On the decomposition of n! into primes, arXiv:math/0606316 [math.NT], 2006-2007.
Keith Matthews, Computing the prime-power factorization of n!
Daniel Suteu, Perl program

Cf. A001222, A013939, A046660, A144494, A115627, A238002, A069513.

a022559 n = a022559_list !! n
a022559_list = scanl (+) 0 $ map a001222 [1..]
-- Reinhard Zumkeller, Feb 16 2012

with(numtheory):with(combinat):a:=proc(n) if n=0 then 0 else bigomega(numbperm(n)) fi end: seq(a(n), n=0..63); # Zerinvary Lajos, Apr 11 2008
# Alternative:
ListTools:-PartialSums(map(numtheory:-bigomega, [$0..200])); # Robert Israel, Dec 21 2018

Array[Plus@@Last/@FactorInteger[ #! ] &, 5!, 0] (* Vladimir Joseph Stephan Orlovsky, Nov 10 2009 *)
f[n_] := If[n <= 1, 0, Total[FactorInteger[n]][[2]]]; Accumulate[Array[f, 100, 0]] (* T. D. Noe, Apr 11 2011 *)
Table[PrimeOmega[n!], {n, 0, 70}] (* Jean-François Alcover, Jun 08 2013 *)
Join[{0}, Accumulate[PrimeOmega[Range[70]]]] (* Harvey P. Dale, Jul 23 2013 *)

PARI
```
a(n)=bigomega(n!)
```

first(n)={my(k=0); vector(n, i, k+=bigomega(i))}

a(n) = sum(k=1, primepi(n), (n - sumdigits(n, prime(k))) / (prime(k)-1)); \\ Daniel Suteu, Apr 18 2018

a(n) = my(res = 0); forprime(p = 2, n, cn = n; while(cn > 0, res += (cn \= p))); res \\ David A. Corneth, Apr 27 2018

from sympy import factorint as pf
def aupton(nn):
    alst = [0]
    for n in range(1, nn+1): alst.append(alst[-1] + sum(pf(n).values()))
    return alst
print(aupton(63)) # Michael S. Branicky, Aug 01 2021

a(n) = a(n-1) + A001222(n).
A027746(a(A000040(n))+1) = A000040(n). A082288(a(n)+1) = n.
A001221(n!) = omega(n!) = pi(n) = A000720(n).
a(n) = Sum_{i = 1..n} A001222(i). - Jonathan Vos Post, Feb 10 2010
a(n) = n log log n + B_2 * n + o(n), with B_2 = A083342. - Charles R Greathouse IV, Jan 11 2012
a(n) = A210241(n) - n for n > 0. - Reinhard Zumkeller, Mar 23 2012
G.f.: (1/(1 - x))*Sum_{p prime, k>=1} x^(p^k)/(1 - x^(p^k)). - Ilya Gutkovskiy, Mar 15 2017
a(n) = Sum_{k=1..floor(sqrt(n))} k * (A025528(floor(n/k)) - A025528(floor(n/(k+1)))) + Sum_{k=1..floor(n/(floor(sqrt(n))+1))} floor(n/k) * A069513(k). - Daniel Suteu, Dec 21 2018
a(n) = Sum_{prime p<=n} Sum_{k=1..floor(log_p(n))} floor(n/p^k). - Ridouane Oudra, Nov 04 2022
a(n) = Sum_{k=1..n} A069513(k)*floor(n/k). - Ridouane Oudra, Oct 04 2024

Typo corrected by Daniel Forgues, Nov 16 2009

A048865 a(n) is the number of primes in the reduced residue system mod n.

Original entry on oeis.org

0, 0, 1, 1, 2, 1, 3, 3, 3, 2, 4, 3, 5, 4, 4, 5, 6, 5, 7, 6, 6, 6, 8, 7, 8, 7, 8, 7, 9, 7, 10, 10, 9, 9, 9, 9, 11, 10, 10, 10, 12, 10, 13, 12, 12, 12, 14, 13, 14, 13, 13, 13, 15, 14, 14, 14, 14, 14, 16, 14, 17, 16, 16, 17, 16, 15, 18, 17, 17, 16, 19, 18, 20, 19, 19, 19, 19, 18, 21, 20, 21

Offset: 1

Labos Elemer

nonn

The number of primes p <= n with p coprime to n. - Enrique Pérez Herrero, Jul 23 2011

			At n=30 all but 1 element in reduced residue system of 30 are primes (see A048597) so a(30) = Phi(30) - 1 = 7.
n=100: a(100) = Pi(100) - A001221(100) = 25 - 2 = 23.

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

Cf. A000010, A000720, A001221, A010051, A048597, A070296, A368616, A368641.

a048865 n = sum $ map a010051 [t | t <- [1..n], gcd n t == 1]
-- Reinhard Zumkeller, Sep 16 2011

A048865 := n ->  nops(select(isprime, select(k -> igcd(n,k) = 1, [$1..n]))):
seq(A048865(n), n = 1..81); # Peter Luschny, Jul 23 2011

p=Prime[Range[1000]]; q=Table[PrimePi[i], {i, 1, 1000}]; t=Table[c=0; Do[If[GCD[p[[j]], i]==1, c++ ], {j, 1, q[[i-1]]}]; c, {i, 2, 950}]
Table[Count[Select[Range@ n, CoprimeQ[#, n] &], p_ /; PrimeQ@ p], {n, 81}] (* Michael De Vlieger, Apr 27 2016 *)
Table[PrimePi[n] - PrimeNu[n], {n, 50}] (* G. C. Greubel, May 16 2017 *)

PARI
```
A048865(n)=primepi(n)-omega(n)
```

a(n) = A000720(n) - A001221(n).
From Reinhard Zumkeller, Apr 05 2004: (Start)
a(n) = Sum_{p prime and p<=n} (ceiling(n/p) - floor(n/p)).
a(n) = A093614(n) - A013939(n). (End)
a(n) = A001221(A001783(n)). - Enrique Pérez Herrero, Jul 23 2011
a(n) = A368616(n) - A368641(n). - Wesley Ivan Hurt, Jan 01 2024

A024934 Sum of remainders n mod p, over all primes p < n.

Original entry on oeis.org

0, 0, 0, 1, 1, 3, 1, 4, 6, 7, 4, 8, 8, 13, 10, 8, 12, 18, 20, 27, 28, 26, 21, 29, 33, 37, 31, 37, 37, 46, 46, 56, 65, 62, 54, 53, 59, 70, 61, 57, 62, 74, 75, 88, 89, 95, 84, 98, 108, 116, 124, 119, 119, 134, 145, 145, 152, 146, 131, 147, 154, 171, 156, 164, 180, 180, 182, 200, 200, 193, 198, 217

Offset: 0

Clark Kimberling

nonn

			a(5) = 3. The remainder when 5 is divided by primes 2, 3 respectively is 1, 2, and their sum = 3.
10 = 2*5+0 = 3*3+1 = 5*2+0 = 7*1+3: a(10) = 0+1+0+3 = 4.

Alois P. Heinz, Table of n, a(n) for n = 0..10000

Cf. A004125, A067435, A067436, A013939, A101336.

a[n_] := Sum[Mod[n, Prime[i]], {i, PrimePi@ n}]; Array[a, 72, 0] (* Giovanni Resta, Jun 24 2016 *)
Table[Total[Mod[n,Prime[Range[PrimePi[n]]]]],{n,0,80}] (* Harvey P. Dale, Jul 02 2025 *)

a(n)=my(r=0);forprime(p=2,n,r+=n%p); r; \\ Joerg Arndt, Nov 05 2016

a(n) = n*A000720(n) - A024924(n). - Max Alekseyev, Feb 10 2012

a(n) = a(n-1) + A000720(n-1) - A105221(n). - Max Alekseyev, Nov 28 2017

Edited by Max Alekseyev, Jan 30 2012

a(0)=0 prepended by Max Alekseyev, Dec 10 2013

A346009 a(n) is the numerator of the average number of distinct prime factors of the divisors of n.

Original entry on oeis.org

0, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 7, 1, 1, 1, 4, 1, 7, 1, 7, 1, 1, 1, 5, 2, 1, 3, 7, 1, 3, 1, 5, 1, 1, 1, 4, 1, 1, 1, 5, 1, 3, 1, 7, 7, 1, 1, 13, 2, 7, 1, 7, 1, 5, 1, 5, 1, 1, 1, 5, 1, 1, 7, 6, 1, 3, 1, 7, 1, 3, 1, 17, 1, 1, 7, 7, 1, 3, 1, 13, 4, 1, 1, 5, 1, 1

Offset: 1

Amiram Eldar, Jul 01 2021

			The fractions begin with 0, 1/2, 1/2, 2/3, 1/2, 1, 1/2, 3/4, 2/3, 1, 1/2, 7/6, ...
f(2) = 1/2 since 2 has 2 divisors, 1 and 2, and (omega(1) + omega(2))/2 = (0 + 1)/2 = 1/2.
f(6) = 1 since 6 has 4 divisors, 1, 2, 3 and 6 and (omega(1) + omega(2) + omega(3) + omega(6))/4 = (0 + 1 + 1 + 2)/4 = 1.

James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, Exercise 3.3.21 on page 100.

Amiram Eldar, Table of n, a(n) for n = 1..10000
R. L. Duncan, Note on the divisors of a number, The American Mathematical Monthly, Vol. 68, No. 4 (1961), pp. 356-359.
Sébastien Gaboury, Sur les convolutions de fonctions arithmétiques, M.Sc. thesis, Laval University, Quebec, 2007.

Cf. A000005, A001221, A006881, A013939, A062799, A077761, A346010 (denominators), A346011.

a[n_] := Numerator[DivisorSum[n, PrimeNu[#] &]/DivisorSigma[0, n]]; Array[a, 100]
(* or *)
f[p_, e_] := e/(e+1); a[1] = 0; a[n_] := Numerator[Plus @@ f @@@ FactorInteger[n]]; Array[a, 100]

Let f(n) = a(n)/A346010(n) be the sequence of fractions. Then:
f(n) = A062799(n)/A000005(n).
f(n) = (Sum_{p prime, p|n} d(n/p))/d(n), where d(n) is the number of divisors of n (A000005).
f(n) depends only on the prime signature of n: If n = Product_{i} p_i^e_i, then a(n) = Sum_{i} e_i/(e_i + 1).
f(p) = 1/2 for prime p.
f(n) = 1 for squarefree semiprimes n (A006881).
Sum_{k=1..n} f(k) ~ (1/2) * A013939(n) + C*n + O(n/log(n)) ~ n*log(log(n))/2 + (B/2 + C)*n + O(n/log(n)), where B is Mertens's constant (A077761) and C = A346011 (Duncan, 1961).

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

Original entry on oeis.org

0, 1, 2, 3, 4, 4, 1, 5, 1, 6, 1, 7, 1, 7, 2, 8, 2, 8, 3, 9, 3, 9, 4, 9, 5, 10, 5, 11, 5, 11, 6, 12, 6, 12, 7, 12, 8, 12, 9, 13, 9, 13, 10, 14, 10, 14, 11, 15, 11, 15, 12, 16, 12, 16, 12, 1, 17, 12, 1, 18, 12, 1, 18, 13, 1, 18, 14, 1, 18, 15, 1, 18, 16, 1, 19, 16, 1, 19, 17, 1

Offset: 1

N. J. A. Sloane, Aug 19 2021

Column k >= 1 of the triangle gives the number of numbers i in the range 1 <= i <= n with omega(i) = A001221(i) = k.

A285577 is a similar triangle which has an extra column on the left for k = 0.

			Rows 1 through 12 are:
1 [0]
2 [1]
3 [2]
4 [3]
5 [4]
6 [4, 1]
7 [5, 1]
8 [6, 1]
9 [7, 1]
10 [7, 2]
11 [8, 2]
12 [8, 3]
13 [9, 3]

G. H. Hardy, Ramanujan: twelve lectures on subjects suggested by his life and work, Cambridge, University Press, 1940, pp. 52-56.
Edmund Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Chelsea Publishing, NY 1953, Vol. 1, p. 211, Eq. (5).

Alois P. Heinz, Rows n = 1..10000, flattened
N. J. A. Sloane, The first 100 rows.

Cf. A001221, A013939, A069811, A123066, A174863, A285577.

Row lengths give A111972 (for n>1).

omega := proc(n) nops(numtheory[factorset](n)) end proc: # # A001221
A:=Array(1..20,0);
ans:=[[0]];
mx:=0;
for n from 2 to 100 do
k:=omega(n);
if k>mx then mx:=k; fi;
A[k]:=A[k]+1;
ans:=[op(ans),[seq(A[i],i=1..mx)]];
od:
ans;
# second Maple program:
b:= proc(n) option remember; `if`(n=0, 0,
      b(n-1)+x^nops(ifactors(n)[2]))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..max(1, degree(p))))(b(n)):
seq(T(n), n=1..40);  # Alois P. Heinz, Aug 19 2021

T[n_] := If[n == 1, {0},
     Range[n] // PrimeNu // Tally // Rest // #[[All, 2]]&];
Array[T, 40] // Flatten (* Jean-François Alcover, Mar 08 2022 *)

For fixed k, T(n,k) ~ (1/(k-1)!) * n * (log log n)^(k-1) / log n [Landau].
From Alois P. Heinz, Aug 19 2021: (Start)
Sum_{k>=1} k * T(n,k) = A013939(n).
Sum_{k>=1} k^2 * T(n,k) = A069811(n).
Sum_{k>=1} (-1)^(k-1) * T(n,k) = A123066(n).
Sum_{k>=1} (-1)^k * T(n,k) = -1 + A174863(n).
Sum_{k>=1} T(n,k) = n - 1. (End)

A013937 a(n) = Sum_{k=1..n} floor(n/k^3).

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 23, 24, 25, 27, 28, 29, 31, 32, 33, 34, 35, 37, 38, 39, 40, 41, 42, 43, 44, 46, 47, 48, 49, 50, 51, 52, 53, 55, 56, 57, 58, 59, 60, 62, 63, 65, 66, 67, 68, 69, 70, 71, 72, 75, 76, 77, 78, 79, 80, 81, 82

Offset: 0

N. J. A. Sloane, Henri Lifchitz

nonn

			a(36) = [36/1]+[36/8]+[36/27]+[36/64]+... = 36+4+1+0+... = 41.

Seiichi Manyama, Table of n, a(n) for n = 0..10000
Benoit Cloitre, Plot of (a(n)-zeta(3)*n)/n^(1/3)-zeta(1/3)

Cf. A005187, A006218, A011371, A013936, A013939 for similar sequences.

A013937:=n->add(floor(n/k^3), k=1..n); seq(A013937(n), n=0..100); # Wesley Ivan Hurt, Feb 15 2014

Table[Sum[Floor[n/k^3], {k, n}], {n, 0, 100}] (* Wesley Ivan Hurt, Feb 15 2014 *)

a(n)=sum(k=1,ceil(n^(1/3)),n\k^3) /*Benoit Cloitre, Nov 05 2012 */

a(n) = a(n-1)+A061704(n). a(n) = Sum_{k=1..n} floor((n/k)^(1/3)) with asymptotic formula: a(n) = zeta(3)*n+zeta(1/3)*n^(1/3)+O(n^theta) where theta<1/3 and we conjecture that theta=1/4+epsilon is the best possible choice. - Benoit Cloitre, Nov 05 2012

G.f.: (1/(1 - x))*Sum_{k>=1} x^(k^3)/(1 - x^(k^3)). - Ilya Gutkovskiy, Feb 11 2017

More terms from Henry Bottomley, Jul 03 2001

cp's OEIS Frontend

A063971 Values of n for which A013939(n)/n is an integer.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Extensions

A092604 Complement of A013939.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Julia

Magma

Maple

Mathematica

MuPAD

MuPAD

PARI

Python

Sage

SageMath

SageMath

Formula

A027748 Irregular triangle in which first row is 1, n-th row (n > 1) lists distinct prime factors of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Extensions

A022559 Sum of exponents in prime-power factorization of n!.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Formula

Extensions

A048865 a(n) is the number of primes in the reduced residue system mod n.

Views

Author