login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
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
Sequence in context: A333819 A216944 A178832 * A210746 A283986 A343515
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 20:05 EDT 2024. Contains 371254 sequences. (Running on oeis4.)