A069626 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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.