

A111233


Number of nonempty subsets of {1, 1/2, 1/3, ..., 1/n} that sum to an integer.


2



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
(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

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


FORMULA

a(p^e) = a(p^e1).  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[n1], Count[Total /@ Subsets[1/Range[n], {1, 2^(n1)}], _?IntegerQ]]];
Table[Print[n, " ", a[n] // Timing]; a[n], {n, 1, 25}] (* JeanFranç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(n1, soh, c) + b(n1, 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
Adjacent sequences: A111230 A111231 A111232 * A111234 A111235 A111236


KEYWORD

nonn,hard,more


AUTHOR

John W. Layman, Oct 28 2005


EXTENSIONS

More terms from Robert G. Wilson v, Sep 23 2006


STATUS

approved



