

A076078


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


42



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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^r2^s+1); for example f(1400846643)=f(3^5*7^8)=2^(5*8)*(2^ (5+8+1)2^52^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 A000255(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(a(m), m divides n), where d(n)=A000005(n) is the number of divisors of n, so a(n) = sum(mu(n/m)*(2^d(m)1), m divides n).


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


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, A097210A097218, A097416, A002235.
Sequence in context: A280684 A322671 A087909 * A292786 A326486 A053204
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



