|
|
A111233
|
|
Number of nonempty subsets of {1, 1/2, 1/3, ..., 1/n} that sum to an integer.
|
|
3
|
|
|
1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 3, 5, 5, 5, 11, 11, 11, 21, 21, 43, 43, 43, 43, 83, 83, 83, 83, 255, 255, 449, 449, 449, 895, 895, 1407, 2111, 2111, 2111, 2111, 4159, 4159, 8319, 8319, 8319, 16639, 16639, 16639, 33279, 33279, 33279, 33279, 66559, 66559, 122019
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,6
|
|
COMMENTS
|
If the set was {1/2, 1/3, 1/4, ..., 1/n}, that is, the set is lacking the element 1, then the sequence would be (a(n)-1)/2. - Robert G. Wilson v, Sep 23 2006
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
1, 1/2 + 1/3 + 1/6 = 1 and 1 + 1/2 + 1/3 + 1/6 = 2 are integers, so a(6)=3.
|
|
MATHEMATICA
|
Needs["DiscreteMath`Combinatorica`"]
f[1] = 1; f[n_] := Block[{c = 0, k = 2, lmt = 2^n/2, int = Range[2, n]}, While[k < lmt, If[IntegerQ[Plus @@ (1/NthSubset[k, int])], c++ ]; k++ ]; 2c+1];
Do[Print[{n, f[n] // Timing}], {n, 40}]
(* Second program (not needing Combinatorica): *)
a[n_] := a[n] = If[n == 1, 1, If[PrimePowerQ[n], a[n-1], Count[Total /@ Subsets[1/Range[n], {1, 2^(n-1)}], _?IntegerQ]]];
|
|
PROG
|
(Python)
from fractions import Fraction
from functools import lru_cache
@lru_cache(maxsize=None)
def b(n, soh, c):
if n == 0: return int(soh.denominator == 1)
return b(n-1, soh, c) + b(n-1, soh+Fraction(1, n), c+1)
a = lambda n: b(n, 0, 0) - 1 # subtract empty set
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,hard
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|