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

Offset: 1

Author

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

Keywords

• nonn

Examples

			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}.
		

Links

• Index entries for sequences related to subset sums modulo m.

Crossrefs

Cf. A000048, A008683, A063776.

Programs

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 *)

PARI

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

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).

Extensions

More terms from Vladeta Jovovic, Sep 27 2001