A272851 - OEIS

%I #25 Nov 08 2016 21:03:53

%S 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,

%T 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,

%U 5,4,4,3,2,3,4,3,5,3,3,4

%N Number of distinct nonzero Fibonacci numbers among the contiguous substrings of the binary digits of n.

%H Marko Riedel, <a href="/A272851/a272851.maple.txt">Maple program to compute sequence.</a>

%e 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.

%t 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 *)

%o (PARI) isfib(n) = my(k=n^2); k+=(k+1)<<2; issquare(k) || (n>0 && issquare(k-8)) ;

%o 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

%Y Cf. A000045, A078822, A272852, A272886.

%K nonn,base

%O 1,2

%A _Marko Riedel_, May 07 2016