cp's OEIS Frontend

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.

%I A256220 #23 Feb 15 2022 11:38:22
%S A256220 1,3,5,9,11,22,28,37,45,62,70,125,133,172,330,421,450,840,901,1710,
%T A256220 2356,2724,2824,5367,6022,7142,8072,18771,19204,35739,36453,42853,
%U A256220 82094,88574,155642,264869
%N 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.
%C A256220 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.
%e A256220 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.
%t A256220 <<"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]]
%o A256220 (Python)
%o A256220 from math import gcd, lcm
%o A256220 from itertools import combinations
%o A256220 def A256220(n):
%o A256220     m = lcm(*range(1,n+1))
%o A256220     fibset, mlist = set(), tuple(m//i for i in range(1,n+1))
%o A256220     a, b, c, k = 0, 1, 0, sum(mlist)
%o A256220     while b <= k:
%o A256220         fibset.add(b)
%o A256220         a, b = b, a+b
%o A256220     for l in range(1,n//2+1):
%o A256220         for p in combinations(mlist,l):
%o A256220             s = sum(p)
%o A256220             if s//gcd(s,m) in fibset:
%o A256220                 c += 1
%o A256220             if 2*l != n and (k-s)//gcd(k-s,m) in fibset:
%o A256220                 c += 1
%o A256220     return c+int(k//gcd(k,m) in fibset) # _Chai Wah Wu_, Feb 15 2022
%Y A256220 Cf. A000045, A075188, A010056, A256221, A256222, A256223.
%K A256220 nonn,more
%O A256220 1,2
%A A256220 _Michel Lagneau_, Mar 19 2015
%E A256220 a(23)-a(36) from _Lars Blomberg_, May 06 2015