|
|
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.
|
|
4
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
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
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|