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)
FORMULA
a(n) = Sum_{ d divides n } mu(n/d)*2^(tau(d)-1). - Vladeta Jovovic, Jul 07 2003
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
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