%I #51 Mar 15 2024 06:19:16

%S 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 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 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 Number of sets of integers larger than one whose least common multiple is n.

%C 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 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 <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>

%H <a href="/index/Lc#lcm">Index entries for sequences related to lcm's</a>

%F a(n) = Sum_{ d divides n } mu(n/d)*2^(tau(d)-1). - _Vladeta Jovovic_, Jul 07 2003

%F a(n) >= A286518, a(n) >= A318670. - _Antti Karttunen_, Feb 17 2024

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

%e 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 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 From _Antti Karttunen_, Feb 18 2024: (Start)

%e a(1) = 1 as there is only one set that satisfies the criteria, namely, an empty set {}, whose lcm is 1.

%e a(2) = 1 as the only set that satisfies the criteria is a singleton set {2}.

%e (End)

%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 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 (Haskell) -- following _Vladeta Jovovic_'s formula.

%o a069626 n = sum $

%o map (\d -> (a008683 (n `div` d)) * 2 ^ (a000005 d - 1)) $ a027750_row n

%o -- _Reinhard Zumkeller_, Jun 12 2015, Feb 07 2011

%o (APL, Dyalog dialect)

%o divisors ← {ð←⍵{(0=⍵|⍺)/⍵}⍳⌊⍵*÷2 ⋄ 1=⍵:ð ⋄ ð,(⍵∘÷)¨(⍵=(⌊⍵*÷2)*2)↓⌽ð}

%o A069626 ← { D←1↓divisors(⍵) ⋄ T←(⍴D)⍴2 ⋄ +/⍵⍷{∧/D/⍨T⊤⍵}¨(-∘1)⍳2*⍴D } ⍝ (quite taxing on memory) - _Antti Karttunen_, Feb 18 2024

%o (PARI) A069626(n) = sumdiv(n,d,moebius(n/d)*2^(numdiv(d)-1)); \\ _Antti Karttunen_, Feb 18 2024

%Y A000005, A008683, A286518, A318670.

%Y Möbius transform of A100577.

%Y Cf. also A045778 (number of sets of integers > 1 whose product is n).

%Y Cf. A076078.

%K nonn,nice,easy

%O 1,4

%A _Amarnath Murthy_, Mar 27 2002

%E Corrected and extended by _Naohiro Nomoto_, Apr 25 2002

%E Definition and examples clarified by _Antti Karttunen_, Feb 18 2024