A076078 a(n) is the number of nonempty sets of distinct positive integers that have a least common multiple of n.

1, 2, 2, 4, 2, 10, 2, 8, 4, 10, 2, 44, 2, 10, 10, 16, 2, 44, 2, 44, 10, 10, 2, 184, 4, 10, 8, 44, 2, 218, 2, 32, 10, 10, 10, 400, 2, 10, 10, 184, 2, 218, 2, 44, 44, 10, 2, 752, 4, 44, 10, 44, 2, 184, 10, 184, 10, 10, 2, 3748, 2, 10, 44, 64, 10, 218, 2, 44, 10, 218, 2, 3392, 2, 10

Offset

1,2

Comments

a(n)=1 iff n=1, a(p^k)=2^k, a(p*q)=10; where p & q are unique primes. a(n) cannot equal an odd number >1. - Robert G. Wilson v

If m has more divisors than n, then a(m) > a(n). - Matthew Vandermast, Aug 22 2004

If n is of the form p^r*q^s where p & q are distinct primes and r & s are nonnegative integers then a(n)=2^(rs)*(2^(r+s+1) -2^r-2^s+1); for example f(1400846643)=f(3^5*7^8)=2^(5*8)*(2^ (5+8+1)-2^5-2^8+1)=17698838672310272. Also if n=p_1^r_1*p_2^r_2*...*p_k^r_k where p_1,p_2,...,p_k are distinct primes and r_1,r_2,...,r_k are natural numbers then 2^(r_1*r_2*...*r_k)||a(n). - Farideh Firoozbakht, Aug 06 2005

None of terms is divisible by Mersenne numbers 3 or 7. For any n, a(n) is congruent to A008836(n) mod 3. Since A008836(n) is always 1 or -1, this implies that A000225(2)=3 never divides a(n). - Matthew Vandermast, Oct 12 2010

There are terms divisible by larger Mersenne numbers. For example, a(2*3*5*7*11*13*19*23^3) is divisible by 31. - Max Alekseyev, Nov 18 2010

Links

David Wasserman, Table of n, a(n) for n = 1..1000

Index entries for sequences related to prime signature

Formula

2^d(n) - 1 = Sum_{m|n} a(m), where d(n) = A000005(n) is the number of divisors of n, so a(n) = Sum_{m|n} mu(n/m)*(2^d(m) - 1).

a(n) = 2*A069626(n), for n > 1. - Ridouane Oudra, Mar 12 2024

Example

a(6) = 10. The sets with LCM 6 are {6}, {1,6}, {2,3}, {2,6}, {3,6}, {1,2,3}, {1,2,6}, {1,3,6}, {2,3,6}, {1,2,3,6}.

Maple

with(numtheory): seq(add(mobius(n/d)*(2^tau(d)-1), d in divisors(n)), n=1..80); # Ridouane Oudra, Mar 12 2024

Mathematica

f[n_] := Block[{d = Divisors[n]}, Plus @@ (MoebiusMu[n/d](2^DivisorSigma[0, d] - 1))]; Table[ f[n], {n, 75}] (* Robert G. Wilson v *)

Prog

(PARI) a(n) = local(f, l, s, t, q); f = factor(n); l = matsize(f)[1]; s = 0; forvec(v = vector(l, i, [0, 1]), q = sum(i = 1, l, v[i]); t = (-1)^(l - q)*2^prod(i = 1, l, f[i, 2] + v[i]); s += t); s; \\ Definition corrected by David Wasserman, Dec 26 2007

Crossrefs

Cf. A076413, A097210-A097218, A097416, A002235.

Cf. A069626.

Sequence in context: A280684 A322671 A087909 * A292786 A326486 A357817

Adjacent sequences: A076075 A076076 A076077 * A076079 A076080 A076081

Keyword

easy,nonn,nice

Author

Amarnath Murthy, Oct 05 2002

Extensions

Edited by Dean Hickerson, Oct 08 2002

Definition corrected by David Wasserman, Dec 26 2007

Edited by Charles R Greathouse IV, Aug 02 2010

Edited by Max Alekseyev, Nov 18 2010

Status

approved