|
%I #38 Sep 10 2023 10:18:04
%S 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,
%T 255,255,449,449,449,895,895,1407,2111,2111,2111,2111,4159,4159,8319,
%U 8319,8319,16639,16639,16639,33279,33279,33279,33279,66559,66559,122019
%N Number of nonempty subsets of {1, 1/2, 1/3, ..., 1/n} that sum to an integer.
%C 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
%H Martin Fuller, <a href="/A111233/b111233.txt">Table of n, a(n) for n = 1..300</a>
%H Martin Fuller, <a href="/A111233/a111233.txt">Python program</a>
%F a(p^e) = a(p^e-1). - _Robert G. Wilson v_, Sep 23 2006
%e 1, 1/2 + 1/3 + 1/6 = 1 and 1 + 1/2 + 1/3 + 1/6 = 2 are integers, so a(6)=3.
%t Needs["DiscreteMath`Combinatorica`"]
%t 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];
%t Do[Print[{n, f[n] // Timing}], {n, 40}]
%t (* _Robert G. Wilson v_, Sep 23 2006 *)
%t (* Second program (not needing Combinatorica): *)
%t 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]]];
%t Table[Print[n, " ", a[n] // Timing]; a[n], {n, 1, 25}] (* _Jean-François Alcover_, Aug 11 2022 *)
%o (Python)
%o from fractions import Fraction
%o from functools import lru_cache
%o @lru_cache(maxsize=None)
%o def b(n, soh, c):
%o if n == 0: return int(soh.denominator == 1)
%o return b(n-1, soh, c) + b(n-1, soh+Fraction(1, n), c+1)
%o a = lambda n: b(n, 0, 0) - 1 # subtract empty set
%o print([a(n) for n in range(1, 21)]) # _Michael S. Branicky_, Aug 11 2022
%Y Cf. A101877, A217693
%K nonn,hard
%O 1,6
%A _John W. Layman_, Oct 28 2005
%E More terms from _Robert G. Wilson v_, Sep 23 2006
%E a(44) onwards from _Martin Fuller_, Sep 09 2023
|
