A272851 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

LINKS

Table of n, a(n) for n=1..80.

Marko Riedel, Maple program to compute sequence.

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

Cf. A000045, A078822, A272852, A272886.

Sequence in context: A361088 A165924 A212628 * A242258 A232615 A257177

Adjacent sequences: A272848 A272849 A272850 * A272852 A272853 A272854

KEYWORD

nonn,base

AUTHOR

Marko Riedel, May 07 2016

STATUS

approved