A064355 - OEIS

A064355

Number of subsets of {1,2,..n} that sum to 1 mod n.

2, 2, 2, 4, 6, 10, 18, 32, 56, 102, 186, 340, 630, 1170, 2182, 4096, 7710, 14560, 27594, 52428, 99858, 190650, 364722, 699040, 1342176, 2581110, 4971008, 9586980, 18512790, 35791358, 69273666, 134217728, 260300986, 505290270, 981706806, 1908874240, 3714566310

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

OFFSET

1,1

LINKS

Table of n, a(n) for n=1..37.

Index entries for sequences related to subset sums modulo m.

FORMULA

a(n) = 2*A000048(n).

a(n) = (1/n) * sum_{d divides n and d is odd} 2^(n/d) * mu(d); (mu(d) is the Moebius function, sequence A008683).

EXAMPLE

a(7) = 18 because there are 18 subsets of {1,2,3,4,5,6,7} which sum to 1 mod 7:{1}, {1,7}, {2,6}, {3,5}, {1,2,5}, {1,3,4}, {2,6,7}, {3,5,7}, {4,5,6}, {1,2,5,7}, {1,3,4,7}, {1,3,5,6}, {2,3,4,6}, {4,5,6,7}, {1,2,3,4,5}, {1,3,5,6,7}, {2,3,4,6,7}, {1,2,3,4,5,7}.

MATHEMATICA

a[n_] := Block[{d = Select[Divisors@n, OddQ@ # &]}, Plus @@ (2^(n/d)*MoebiusMu@d)/n]; Array[a, 35] (* Robert G. Wilson v, Feb 20 2006 *)

PROG

(PARI) a(n) = sumdiv(n, d, (d % 2) * 2^(n/d) * moebius(d)) / n; \\ Amiram Eldar, Jun 05 2025

CROSSREFS

Cf. A000048, A008683, A063776.

Sequence in context: A365717 A060827 A188288 * A000799 A185030 A063823

Adjacent sequences: A064352 A064353 A064354 * A064356 A064357 A064358

KEYWORD

nonn

AUTHOR

Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Sep 25 2001

EXTENSIONS

More terms from Vladeta Jovovic, Sep 27 2001

STATUS

approved