A076078 - OEIS

%I #49 Mar 15 2024 06:19:41

%S 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,

%T 44,2,218,2,32,10,10,10,400,2,10,10,184,2,218,2,44,44,10,2,752,4,44,

%U 10,44,2,184,10,184,10,10,2,3748,2,10,44,64,10,218,2,44,10,218,2,3392,2,10

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

%C 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_

%C If m has more divisors than n, then a(m) > a(n). - _Matthew Vandermast_, Aug 22 2004

%C 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

%C 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

%C 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

%H David Wasserman, <a href="/A076078/b076078.txt">Table of n, a(n) for n = 1..1000</a>

%H <a href="/index/Pri#prime_signature">Index entries for sequences related to prime signature</a>

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

%F a(n) = 2*A069626(n), for n > 1. - _Ridouane Oudra_, Mar 12 2024

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

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

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

%o (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

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

%Y Cf. A069626.

%K easy,nonn,nice

%O 1,2

%A _Amarnath Murthy_, Oct 05 2002

%E Edited by _Dean Hickerson_, Oct 08 2002

%E Definition corrected by _David Wasserman_, Dec 26 2007

%E Edited by _Charles R Greathouse IV_, Aug 02 2010

%E Edited by _Max Alekseyev_, Nov 18 2010