login
A272851
Number of distinct nonzero Fibonacci numbers among the contiguous substrings of the binary digits of n.
4
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,2
EXAMPLE
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.
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 *)
PROG
(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
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Marko Riedel, May 07 2016
STATUS
approved