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

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

Offset

1,4

Comments

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.

Links

Antti Karttunen, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)

Index entries for sequences computed from exponents in factorization of n

Index entries for sequences related to lcm's

Formula

a(n) = Sum_{ d divides n } mu(n/d)*2^(tau(d)-1). - Vladeta Jovovic, Jul 07 2003

a(n) >= A286518, a(n) >= A318670. - Antti Karttunen, Feb 17 2024

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

Example

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}.
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}.
From Antti Karttunen, Feb 18 2024: (Start)
a(1) = 1 as there is only one set that satisfies the criteria, namely, an empty set {}, whose lcm is 1.
a(2) = 1 as the only set that satisfies the criteria is a singleton set {2}.
(End)

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

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 *)

Prog

(Haskell)  -- following Vladeta Jovovic's formula.
a069626 n = sum $
   map (\d -> (a008683 (n `div` d)) * 2 ^ (a000005 d - 1)) $ a027750_row n
-- Reinhard Zumkeller, Jun 12 2015, Feb 07 2011
(APL, Dyalog dialect)
divisors ← {ð←⍵{(0=⍵|⍺)/⍵}⍳⌊⍵*÷2 ⋄ 1=⍵:ð ⋄ ð, (⍵∘÷)¨(⍵=(⌊⍵*÷2)*2)↓⌽ð}
A069626 ← { D←1↓divisors(⍵) ⋄ T←(⍴D)⍴2 ⋄ +/⍵⍷{∧/D/⍨T⊤⍵}¨(-∘1)⍳2*⍴D } ⍝ (quite taxing on memory) - Antti Karttunen, Feb 18 2024
(PARI) A069626(n) = sumdiv(n, d, moebius(n/d)*2^(numdiv(d)-1)); \\ Antti Karttunen, Feb 18 2024

Crossrefs

A000005, A008683, A286518, A318670.

Möbius transform of A100577.

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

Cf. A076078.

Sequence in context: A369038 A161686 A289621 * A348495 A249274 A205443

Adjacent sequences: A069623 A069624 A069625 * A069627 A069628 A069629

Keyword

nonn,nice,easy

Author

Amarnath Murthy, Mar 27 2002

Extensions

Corrected and extended by Naohiro Nomoto, Apr 25 2002

Definition and examples clarified by Antti Karttunen, Feb 18 2024

Status

approved