OFFSET
1,2
COMMENTS
a(n) is asymptotic to 2^(n+1)/n. More precisely, I conjecture for any m > 0, a(n) = 2^(n+1)/n * Sum_{k=0..m} A000670(k)/n^k + o(1/n^(m+1)) (A000670 = preferential arrangements of n labeled elements) which can be written a(n) = 2^n/n * 2 + Sum_{k=1..m} A000629(k)/n^k + o(1/n^(m+1)) (A000629 = necklaces of sets of labeled beads). In fact I conjecture that a(n) = 2^(n+1)/n * (1 + 1/n + 3/n^2 + 13/n^3 + 75/n^4 + 541/n^5 + o(1/n^5)). - Benoit Cloitre, Oct 20 2002
A082550(n) = a(n+1) - a(n). - Reinhard Zumkeller, Feb 19 2006
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..3332 (first 300 terms from T. D. Noe)
63rd Annual William Lowell Putnam Mathematical Competition, Problem A3, Mathematics Magazine 76 (2003), 76-80.
FORMULA
a(n) = Sum_{i=1..n} (A063776(i) - 1).
EXAMPLE
a(4) = 8 because each of the 8 subsets {1}, {2}, {3}, {4}, {1,3}, {2,4}, {1,2,3}, {2,3,4} has an integer average.
MAPLE
with(numtheory):
b:= n-> add(2^(n/d)*phi(d), d=select(x-> x::odd, divisors(n)))/n:
a:= proc(n) option remember; `if`(n<1, 0, b(n)-1+a(n-1)) end:
seq(a(n), n=1..40); # Alois P. Heinz, Jul 15 2019
MATHEMATICA
Table[ Sum[a = Select[Divisors[i], OddQ[ # ] & ]; Apply[Plus, 2^(i/a)*EulerPhi[a]]/i, {i, n}] - n, {n, 34}]
Table[Count[Subsets[Range[n]], _?(IntegerQ[Mean[#]]&)], {n, 35}] (* Harvey P. Dale, Apr 14 2018 *)
PROG
(PARI) a(n)=sum(k=1, n, sumdiv(k, d, d%2*2^(k/d)*eulerphi(d))/k-1)
(Python)
from sympy import totient, divisors
def A051293(n): return sum((sum(totient(d)<<k//d-1 for d in divisors(k>>(~k&k-1).bit_length(), generator=True))<<1)//k for k in range(1, n+1))-n # Chai Wah Wu, Feb 22 2023
CROSSREFS
KEYWORD
nonn,nice
AUTHOR
John W. Layman, Oct 30 1999
EXTENSIONS
Extended by Robert G. Wilson v, Oct 16 2002
STATUS
approved