A272851 Number of distinct nonzero Fibonacci numbers among the contiguous substrings of the binary digits of n.
1, 2, 2, 2, 3, 3, 2, 3, 2, 3, 4, 3, 5, 3, 2, 3, 3, 2, 3, 3, 4, 4, 4, 4, 3, 5, 5, 3, 5, 3, 2, 3, 3, 4, 4, 2, 3, 3, 3, 4, 3, 4, 5, 4, 5, 4, 4, 4, 4, 3, 3, 5, 6, 5, 6, 4, 3, 5, 5, 3, 5, 3, 2, 3, 3, 3, 4, 4, 5, 4, 4, 3, 2, 3, 4, 3, 5, 3, 3, 4
Offset: 1
Examples
a(53) = 6 because 53=(110101)_2 which contains (1)_2 = 1, (10)_2 = 2, (11)_2 = 3, (101)_2 = 5, (1101)_2 = 13 and (10101)_2 = 21. The one digit only contributes once.
Links
- Marko Riedel, Maple program to compute sequence.
Programs
-
Mathematica
s = Fibonacci@ Range@ 30; Table[Length@ Select[Union@ Flatten@ Function[k, Map[FromDigits[#, 2] & /@ Partition[k, #, 1] &, Range@ Length@ k]]@IntegerDigits[#, 2] &@ n, MemberQ[s, #] &], {n, 120}] (* Michael De Vlieger, May 08 2016 *) -
PARI
isfib(n) = my(k=n^2); k+=(k+1)<<2; issquare(k) || (n>0 && issquare(k-8)) ; a(n) = {vb = binary(n); vf = []; for (i=1, #vb, for (j=1, #vb - i + 1, pvb = vector(j, k, vb[i+k-1]); f = subst(Pol(pvb), x, 2); if (f && isfib(f), vf = Set(concat(vf, f))););); #vf;} \\ Michel Marcus, May 08 2016