OFFSET
1,3
COMMENTS
This is the number of ways to sew on a button having n holes arranged in a regular polygon. A button with no stitches would fall off, which is why we require that the subset be nonempty (cf. A192332).
A. Kolmogorov posed the problem for n=4 at the age of 6.
REFERENCES
A. N. Shiryaev 'Andrei Nikolaevich Kolmogorov: A Biographical Sketch of His Life and Creative Paths' in Harold H. McFaden (translator), Kolmogorov in Perspective, American Mathematical Society (2000), page 4.
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 1..80
FORMULA
a(p) = ((2^(p*(p-1)/2) - 2^((p-1)/2)) / p) + (2^((p-1)/2)) - 1 if p is prime.
Comment from N. J. A. Sloane, Jun 28 2011: More generally, a(n) = (1/n)*(Sum_{d|n, d odd} phi(d)*2^(n*(n-1)/(2*d)) + Sum_{d|n, d even} phi(d)*2^(n^2/(2*d))) - 1.
MAPLE
with(numtheory); f:=proc(n) local t0, t1, d; t0:=0; t1:=divisors(n);
for d in t1 do
if d mod 2 = 0 then t0:=t0+phi(d)*2^(n^2/(2*d))
else t0:=t0+phi(d)*2^(n*(n-1)/(2*d)); fi; od; t0/n; end;
[seq(f(n)-1, n=1..30)];
# N. J. A. Sloane, Jun 28 2011
MATHEMATICA
Table[ -1 + 1/n * Plus @@ Map[Function[d, EulerPhi[d]*2^((n*(n - Mod[d, 2])/2)/d)], Divisors[n]], {n, 1, 20}] (* Olivier Gérard, Aug 27 2011 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
David N Lumsden, Jun 27 2011
EXTENSIONS
Terms from a(8) onwards from N. J. A. Sloane, Jun 28 2011
STATUS
approved