A062799 Inverse Möbius transform of the numbers of distinct prime factors (A001221).

0, 1, 1, 2, 1, 4, 1, 3, 2, 4, 1, 7, 1, 4, 4, 4, 1, 7, 1, 7, 4, 4, 1, 10, 2, 4, 3, 7, 1, 12, 1, 5, 4, 4, 4, 12, 1, 4, 4, 10, 1, 12, 1, 7, 7, 4, 1, 13, 2, 7, 4, 7, 1, 10, 4, 10, 4, 4, 1, 20, 1, 4, 7, 6, 4, 12, 1, 7, 4, 12, 1, 17, 1, 4, 7, 7, 4, 12, 1, 13, 4, 4

Offset: 1

Author

Labos Elemer, Jul 19 2001

Keywords

• nonn

Comments

Let us say that two divisors d_1 and d_2 of n are adjacent divisors if d_1/d_2 or d_2/d_1 is a prime. Then a(n) is the number of all pairs of adjacent divisors of n. - Vladimir Shevelev, Aug 16 2010

Equivalent to the preceding comment: a(n) is the number of edges in the directed multigraph on tau(n) vertices, vertices labeled by the divisors d_i of n, where edges connect vertex(d_i) and vertex(d_j) if the ratio of the labels is a prime. - R. J. Mathar, Sep 23 2011

a(A001248(n)) = 2. - Reinhard Zumkeller, Dec 02 2014

Depends on the prime signature of n as follows: a(A025487(n)) = 0, 1, 2, 4, 3, 7, 4, 10, 12, 5, 12, 13, 20, 6, 17, 16, 28, 7, 22, 33, 19 ,32, 24, 36, 8, 27, 46, ... (n>=1). - R. J. Mathar, May 28 2017

Examples

			n = 255: divisors = {1, 3, 5, 15, 17, 51, 85, 255}, a(255) = 0+1+1+2+1+2+2+3 = 12.
		

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• S.-H. Cha, E. G. DuCasse, and L. V. Quintas, Graph Invariants Based on the Divides Relation and Ordered by Prime Signatures, arXiv:1405.5283 [math.NT], 2014.
• E. Pérez Herrero, Psychedelic Geometry Blogspot, CURIOUS SERIES-002

Crossrefs

Cf. A001221, A001248, A027750.

Programs

Haskell

a062799 = sum . map a001221 . a027750_row
-- Reinhard Zumkeller, Dec 02 2014

Maple

read("transforms") ;
A001221 := proc(n)
        nops(numtheory[factorset](n)) ;
end proc:
omega := [seq(A001221(n),n=1..80)] ;
ones := [seq(1,n=1..80)] ;
DIRICHLET(ones,omega) ; # R. J. Mathar, Sep 23 2011
N:= 1000: # to get a(1) to a(N)
B:= Vector(N,t-> nops(numtheory:-factorset(t))):
A:= Vector(N):
for d from 1 to N do
  md:= d*[$1..floor(N/d)];
  A[md]:= map(`+`,A[md],B[d])
od:
convert(A,list); # Robert Israel, Oct 21 2015

Mathematica

f[n_] := Block[{d = Divisors[n], c = l = 0, k = 2}, l = Length[d]; While[k < l + 1, c = c + Length[ FactorInteger[ d[[k]] ]]; k++ ]; Return[c]]; Table[f[n], {n, 1, 100} ]
omega[n_] := Length[FactorInteger[n]]; SetAttributes[omega, Listable]; omega[1] := 0; A062799[n_] := Plus @@ omega[Divisors[n]] (* Enrique Pérez Herrero, Sep 08 2009 *)

PARI

a(n)=my(f=factor(n)[,2],s);forvec(v=vector(#f,i,[0,f[i]]),s+=sum(i=1,#f,v[i]>0));s \\ Charles R Greathouse IV, Oct 15 2015

PARI

vector(100, n, sumdiv(n, k, omega(k))) \\ Altug Alkan, Oct 15 2015

Formula

a(n) = Sum_{d|n} A001221(d), that is, where d runs over divisors of n.

For squarefree s (i.e., s in A005117), a(s) = omega(s)*2^(omega(s)-1), where omega(n) = A001221(n). Also, for n>1, a(n) <= omega(n)*A000005(n) - 1. - Enrique Pérez Herrero, Sep 08 2009

Let n=Product_{i=1..omega(n)} p(i)^e(i). a(n) = d[Product_{i=1..omega(n)} (1 + e(i)*x)]/dx|x=1. In other words, a(n) = Sum_{m>=1} A146289(n,m)*m. - Geoffrey Critzer, Feb 10 2015

a(A000040(n)) = 1; a(A001248(n)) = 2; a(A030078(n)) = 3; a(A030514(n)) = 4; a(A050997(n)) = 5. - Altug Alkan, Oct 17 2015

a(n) = Sum_{prime p|n} A000005(n/p). - Max Alekseyev, Aug 11 2016

G.f.: Sum_{k>=1} omega(k)*x^k/(1 - x^k), where omega(k) is the number of distinct primes dividing k (A001221). - Ilya Gutkovskiy, Jan 16 2017

Dirichlet g.f.: zeta(s)^2*primezeta(s) where primezeta(s) = Sum_{prime p} p^(-s). - Benedict W. J. Irwin, Jul 16 2018