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
Martin Fuller, Table of n, a(n) for n = 1..300
Martin Fuller, Python program
FORMULA
a(p^e) = a(p^e-1). - Robert G. Wilson v, Sep 23 2006
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}]
(* Robert G. Wilson v, Sep 23 2006 *)
(* 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]]];
Table[Print[n, " ", a[n] // Timing]; a[n], {n, 1, 25}] (* Jean-François Alcover, Aug 11 2022 *)
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
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Aug 11 2022
CROSSREFS
KEYWORD
nonn,hard
AUTHOR
John W. Layman, Oct 28 2005
EXTENSIONS
More terms from Robert G. Wilson v, Sep 23 2006
a(44) onwards from Martin Fuller, Sep 09 2023
STATUS
approved