A256221 Number of distinct nonzero Fibonacci numbers in the numerator of the 2^n sums generated from the set 1, 1/2, 1/3, ..., 1/n.

1, 2, 3, 4, 5, 6, 8, 8, 8, 12, 12, 13, 13, 13, 13, 15, 15, 15, 17, 17, 17, 19, 21, 21, 23, 24, 25, 25, 25, 25, 25, 27

Offset

1,2

Comments

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..32.

Example

a(4) = 4 because 4 sums yield distinct Fibonacci numerators: 1, 1 + 1/2 = 3/2, 1/2 + 1/3 = 5/6 and 1/2 + 1/3 + 1/4 = 13/12.

Maple

S:= {0, 1}: N:= {1}:
nfibs:= 10:
fibs:= {seq(combinat:-fibonacci(n), n=1..nfibs)}:
A[1]:= 1:
fibnums:= {1}:
for n from 2 to 24 do
    Sp:= map(`+`, S, 1/n);
    N:= N union map(numer, Sp);
  Nmax:= max(N);
  S:= S union Sp;
  while combinat:-fibonacci(nfibs) < Nmax do nfibs:= nfibs+1; fibs:= fibs union {combinat:-fibonacci(nfibs)} od;
  newfibnums:= N intersect fibs;
  fibnums:= newfibnums;
  A[n]:= nops(fibnums);
od:
seq(A[n], n=1..24); # Robert Israel, Dec 09 2016

Mathematica

<<"DiscreteMath`Combinatorica`"; maxN=23; For[prms={}; 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]], prms=Union[prms, {k}]]]; Print[Length[prms]]]

Prog

(Python)
from math import gcd, lcm
from itertools import combinations
def A256221(n):
    m = lcm(*range(1, n+1))
    fset, fibset, mlist = set(), set(), tuple(m//i for i in range(1, n+1))
    a, b, k = 0, 1, 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 (t := s//gcd(s, m)) in fibset:
                fset.add(t)
            if 2*l != n and (t := (k-s)//gcd(k-s, m)) in fibset:
                fset.add(t)
    if (t:= k//gcd(k, m)) in fibset: fset.add(t)
    return len(fset) # Chai Wah Wu, Feb 15 2022

Crossrefs

Cf. A000045, A075189, A010056, A256220, A256222, A256223.

Sequence in context: A299440 A330401 A145518 * A359099 A210253 A130916

Adjacent sequences: A256218 A256219 A256220 * A256222 A256223 A256224

Keyword

nonn,more

Author

Michel Lagneau, Mar 19 2015

Extensions

Corrected and more terms added by Robert Israel, Dec 09 2016

a(29)-a(31) from Chai Wah Wu, Feb 15 2022

a(32) from Chai Wah Wu, Feb 16 2022

Status

approved