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

Author

Amarnath Murthy, Mar 27 2002

Keywords

• nonn
• nice
• easy

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.

Examples

			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)
		

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

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.

Programs

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

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

PARI

A069626(n) = sumdiv(n,d,moebius(n/d)*2^(numdiv(d)-1)); \\ Antti Karttunen, Feb 18 2024

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

Extensions

Corrected and extended by Naohiro Nomoto, Apr 25 2002

Definition and examples clarified by Antti Karttunen, Feb 18 2024