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

Author

Marko Riedel, May 07 2016

Keywords

• nonn
• base

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.

Crossrefs

Cf. A000045, A078822, A272852, A272886.

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