A256220 Number of times that the numerator of a sum generated from the set 1, 1/2, 1/3,..., 1/n is a Fibonacci number.

1, 3, 5, 9, 11, 22, 28, 37, 45, 62, 70, 125, 133, 172, 330, 421, 450, 840, 901, 1710, 2356, 2724, 2824, 5367, 6022, 7142, 8072, 18771, 19204, 35739, 36453, 42853, 82094, 88574, 155642, 264869

Offset

1,2

Comments

Note that for each n there are only 2^(n-1) new sums to consider. For the number of distinct Fibonacci numbers, see A256221. For the largest generated Fibonacci number, see A256222. For the smallest Fibonacci number not generated, see A256223.

Links

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

Example

a(3) = 5 because we obtain 5 following subsets {1}, {1/2}, {1/3}, {1,1/2} and {1/2, 1/3} having 5 sums with Fibonacci numerators: 1, 1, 1, 1+1/2 = 3/2 and 1/2+1/3 = 5/6.

Mathematica

<<"DiscreteMath`Combinatorica`"; maxN=22; For[cnt=0; i=0; n=1, n<=maxN, n++, While[i<2^n-1, i++; s=NthSubset[i, Range[n]]; k=Numerator[Plus@@(1/s)]; If[IntegerQ[Sqrt[5*k^2+4]]||IntegerQ[Sqrt[5*k^2-4]], cnt++ ]]; Print[cnt]]

Prog

(Python)
from math import gcd, lcm
from itertools import combinations
def A256220(n):
    m = lcm(*range(1, n+1))
    fibset, mlist = set(), tuple(m//i for i in range(1, n+1))
    a, b, c, k = 0, 1, 0, sum(mlist)
    while b <= k:
        fibset.add(b)
        a, b = b, a+b
    for l in range(1, n//2+1):
        for p in combinations(mlist, l):
            s = sum(p)
            if s//gcd(s, m) in fibset:
                c += 1
            if 2*l != n and (k-s)//gcd(k-s, m) in fibset:
                c += 1
    return c+int(k//gcd(k, m) in fibset) # Chai Wah Wu, Feb 15 2022

Crossrefs

Cf. A000045, A075188, A010056, A256221, A256222, A256223.

Sequence in context: A231716 A113488 A092917 * A163778 A328643 A160358

Adjacent sequences: A256217 A256218 A256219 * A256221 A256222 A256223

Keyword

nonn,more

Author

Michel Lagneau, Mar 19 2015

Extensions

a(23)-a(36) from Lars Blomberg, May 06 2015

Status

approved