cp's OEIS Frontend

A069626 Number of sets of integers larger than one whose least common multiple is n.

%I A069626 #51 Mar 15 2024 06:19:16
%S A069626 1,1,1,2,1,5,1,4,2,5,1,22,1,5,5,8,1,22,1,22,5,5,1,92,2,5,4,22,1,109,1,
%T A069626 16,5,5,5,200,1,5,5,92,1,109,1,22,22,5,1,376,2,22,5,22,1,92,5,92,5,5,
%U A069626 1,1874,1,5,22,32,5,109,1,22,5,109,1,1696,1,5,22,22,5,109,1,376,8,5,1,1874,5,5,5,92,1,1874,5,22
%N A069626 Number of sets of integers larger than one whose least common multiple is n.
%C A069626 a(p) = 1, a(p*q) = 5, a(p^2*q) = 13, a(p^3) = 4, a(p^4) = 8 etc. where p and q are primes. It can be shown that a(p^k) = 2^(k-1). Problem: find an expression for a(N) when N = p^a*q^b*r^c*..., p,q,r are primes.
%H A069626 Antti Karttunen, <a href="/A069626/b069626.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from T. D. Noe)
%H A069626 <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>
%H A069626 <a href="/index/Lc#lcm">Index entries for sequences related to lcm's</a>
%F A069626 a(n) = Sum_{ d divides n } mu(n/d)*2^(tau(d)-1). - _Vladeta Jovovic_, Jul 07 2003
%F A069626 a(n) >= A286518, a(n) >= A318670. - _Antti Karttunen_, Feb 17 2024
%F A069626 a(n) = A076078(n)/2, for n > 1. - _Ridouane Oudra_, Mar 12 2024
%e A069626 a(6) = 5 as there are five such sets of natural numbers larger than one whose least common multiple is six: {6}, {2, 6}, {3, 6}, {2, 3} and {2, 3, 6}.
%e A069626 a(12) = 22 from {12}, {4,3}, {2,4,3}, {4,6}, {2,4,6}, {4,3,6}, {2,4,3,6}, {2,12}, {4,12}, {2,4,12}, {3,12}, {2,3,12}, {4,3,12}, {2,4,3,12}, {6,12}, {2,6,12}, {4,6,12}, {2,4,6,12}, {3,6,12}, {2,3,6,12}, {4,3,6,12}, {2,4,3,6,12}.
%e A069626 From _Antti Karttunen_, Feb 18 2024: (Start)
%e A069626 a(1) = 1 as there is only one set that satisfies the criteria, namely, an empty set {}, whose lcm is 1.
%e A069626 a(2) = 1 as the only set that satisfies the criteria is a singleton set {2}.
%e A069626 (End)
%p A069626 with(numtheory): seq(add(mobius(n/d)*2^(tau(d)-1), d in divisors(n)), n=1..80); # _Ridouane Oudra_, Mar 12 2024
%t A069626 a[n_] := Sum[ MoebiusMu[n/d] * 2^(DivisorSigma[0, d] - 1), {d, Divisors[n]}]; Table[a[n], {n, 1, 92}](* _Jean-François Alcover_, Nov 30 2011, after _Vladeta Jovovic_ *)
%o A069626 (Haskell)  -- following _Vladeta Jovovic_'s formula.
%o A069626 a069626 n = sum $
%o A069626    map (\d -> (a008683 (n `div` d)) * 2 ^ (a000005 d - 1)) $ a027750_row n
%o A069626 -- _Reinhard Zumkeller_, Jun 12 2015, Feb 07 2011
%o A069626 (APL, Dyalog dialect)
%o A069626 divisors ← {ð←⍵{(0=⍵|⍺)/⍵}⍳⌊⍵*÷2 ⋄ 1=⍵:ð ⋄ ð,(⍵∘÷)¨(⍵=(⌊⍵*÷2)*2)↓⌽ð}
%o A069626 A069626 ← { D←1↓divisors(⍵) ⋄ T←(⍴D)⍴2 ⋄ +/⍵⍷{∧/D/⍨T⊤⍵}¨(-∘1)⍳2*⍴D } ⍝ (quite taxing on memory) - _Antti Karttunen_, Feb 18 2024
%o A069626 (PARI) A069626(n) = sumdiv(n,d,moebius(n/d)*2^(numdiv(d)-1)); \\ _Antti Karttunen_, Feb 18 2024
%Y A069626 A000005, A008683, A286518, A318670.
%Y A069626 Möbius transform of A100577.
%Y A069626 Cf. also A045778 (number of sets of integers > 1 whose product is n).
%Y A069626 Cf. A076078.
%K A069626 nonn,nice,easy
%O A069626 1,4
%A A069626 _Amarnath Murthy_, Mar 27 2002
%E A069626 Corrected and extended by _Naohiro Nomoto_, Apr 25 2002
%E A069626 Definition and examples clarified by _Antti Karttunen_, Feb 18 2024