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,4

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

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

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

Example

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

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

Prog

(Haskell)
a062799 = sum . map a001221 . a027750_row
-- Reinhard Zumkeller, Dec 02 2014
(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

Crossrefs

Cf. A001221, A001248, A027750.

Sequence in context: A341308 A353359 A113901 * A063647 A353379 A263653

Adjacent sequences: A062796 A062797 A062798 * A062800 A062801 A062802

Keyword

nonn

Author

Labos Elemer, Jul 19 2001

Status

approved