A101877 -id:A101877 - cp's OEIS frontend

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

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

Offset: 1

John W. Layman, Oct 28 2005

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

			1, 1/2 + 1/3 + 1/6 = 1 and 1 + 1/2 + 1/3 + 1/6 = 2 are integers, so a(6)=3.

Martin Fuller, Table of n, a(n) for n = 1..300
Martin Fuller, Python program

Cf. A101877, A217693

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 *)

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

a(p^e) = a(p^e-1). - Robert G. Wilson v, Sep 23 2006

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

a(44) onwards from Martin Fuller, Sep 09 2023

A157716 One-eighth of triangular numbers (integers only).

Original entry on oeis.org

0, 15, 17, 62, 66, 141, 147, 252, 260, 395, 405, 570, 582, 777, 791, 1016, 1032, 1287, 1305, 1590, 1610, 1925, 1947, 2292, 2316, 2691, 2717, 3122, 3150, 3585, 3615, 4080, 4112, 4607, 4641, 5166, 5202, 5757, 5795, 6380, 6420, 7035, 7077, 7722, 7766, 8441

Offset: 1

Vladimir Joseph Stephan Orlovsky, Mar 04 2009

From Lamine Ngom, Oct 27 2020: (Start)
Numbers of the form (4*k)^2-k (A157446) or (4*k)^2+k (A157474).
Also numbers k such that 1+64*k is a square. (End)
The sequence terms are the exponents in the expansion of Product_{n >= 1} (1 - q^(32*n))*(1 - q^(32*n-15))*(1 - q^(32*n-17)) = 1 - q^15 - q^17 + q^62 + q^66 - q^141 - q^147 + + - - .... - Peter Bala, Dec 24 2024

			The first three members of A000217 that are divisible by 8 are A000217(0), A000217(15) and A000217(16), so a(1) = A000217(0)/8 = 0, a(2) = A000217(15)/8 = 15, a(3) = A000217(16)/8 = 17.

Robert Israel, Table of n, a(n) for n = 1..10000
Index entries for linear recurrences with constant coefficients, signature (1,2,-2,-1,1).

Cf. A000217, A101877, A219257.

seq((2*n-1 + 7/8*(-1)^n)^2 - 1/64, n = 1 .. 1000); # Robert Israel, Apr 20 2014

Array[(2 # - 1 + 7/8*(-1)^#)^2 - 1/64 &, 46] (* or *)
Rest@ CoefficientList[Series[x^2*(15 + 2 x + 15 x^2)/((1 + x)^2*(1 - x)^3), {x, 0, 46}], x] (* Michael De Vlieger, Nov 05 2020 *)

G.f.: x^2*(15+2*x+15*x^2)/((1+x)^2*(1-x)^3 ). [Maksym Voznyy (voznyy(AT)mail.ru), Jul 26 2009; checked and corrected by R. J. Mathar, Sep 16 2009]
a(n) =  (2*n-1 + 7/8*(-1)^n)^2 -1/64. - Robert Israel, Apr 20 2014
a(n) = a(n-1) + 2*a(n-2) - 2*a(n-3) - a(n-4) + a(n-5). - Wesley Ivan Hurt, Nov 10 2020
Sum_{n>=2} 1/a(n) = 16 - (sqrt(2*(2+sqrt(2))) + sqrt(2) + 1)*Pi. - Amiram Eldar, Mar 17 2022

Definition edited by N. J. A. Sloane, Mar 08 2009

A217693 Numbers of distinct integers obtained from summing up subsets of {1, 1/2, 1/3, ..., 1/n}.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4

Offset: 1

Michel Marcus, Oct 11 2012

nonn

a(n) <= A111233(n).
a(n) <= floor(Sum_{k=1..n} 1/k) = A055980(n). - Joerg Arndt, Oct 13 2012
a(n) <= 4 for n <= 94, a(n) <= 5 for n <= 257, a(n) <= 6 for n <= 689. That is because if there is a term 1/a with p dividing a for a prime p, then there must be another term 1/b with p dividing b. Hence, not all terms from 1/1 to 1/n can be summed up. Cf. the "filter" function in my Sage script. - Manfred Scheucher, Aug 17 2015
a(k) = n for all k such that A101877(n) <= k < A101877(n+1). - Jon E. Schoenfield, May 12 2017

			1, 1/2 + 1/3 + 1/6 = 1 and 1 + 1/2 + 1/3 + 1/6 = 2 are integers, but only 2 of them are distinct, so a(6)=2.
a(24)=3 because 1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/8 + 1/9 + 1/10 + 1/15 + 1/18 + 1/20 + 1/24 = 3 and Sum_{k=1..n} 1/k < 4 for all n <= 30.
a(65)=4 because the sum of the reciprocals of the integers in { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 22, 24, 26, 27, 28, 30, 33, 35, 36, 40, 42, 45, 48, 52, 54, 56, 60, 63, 65 } is 4 and Sum_{k=1..n} 1/k < 5 for all n <= 82. - _Jon E. Schoenfield_, Apr 30 2018

P. Erdos and R. L. Graham, Old and new problems and results in combinatorial number theory, Université de Genève, 1980.

Manfred Scheucher, Sage Script
H. Yokota, On number of integers representable as sums of unit fractions, Canad. Math. Bull. Vol. 33 (2), 1990.
H. Yokota, On Number of Integers Representable as a Sum of Unit Fractions, II, Journal of Number Theory 67, 162-169, 1997.

Cf. A101877, A111233.

ufr(n) = {tab = []; for (i=1, 2^n - 1, vb = binary(i); while(length(vb) < n, vb = concat(0, vb););; val = sum(j=1, length(vb), vb[j]/j); if (denominator(val) == 1, tab = concat(tab, val); ); ); return (length(Set(tab))); }

a(25)-a(46) from Manfred Scheucher, Aug 17 2015

a(47)-a(87) from Jon E. Schoenfield, Apr 30 2018

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A157716 One-eighth of triangular numbers (integers only).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A217693 Numbers of distinct integers obtained from summing up subsets of {1, 1/2, 1/3, ..., 1/n}.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Extensions