cp's OEIS Frontend

A238845 Prefix overlap between binary expansions of n and n+1.

%I A238845 #49 Jun 12 2020 13:36:12
%S A238845 0,1,1,1,2,1,2,1,3,2,3,1,3,2,3,1,4,3,4,2,4,3,4,1,4,3,4,2,4,3,4,1,5,4,
%T A238845 5,3,5,4,5,2,5,4,5,3,5,4,5,1,5,4,5,3,5,4,5,2,5,4,5,3,5,4,5,1,6,5,6,4,
%U A238845 6,5,6,3,6,5,6,4,6,5,6,2,6,5,6,4,6,5,6,3,6,5,6
%N A238845 Prefix overlap between binary expansions of n and n+1.
%C A238845 The prefix overlap between two words is the length of their longest common prefix.
%H A238845 Reinhard Zumkeller, <a href="/A238845/b238845.txt">Table of n, a(n) for n = 0..10000</a>
%H A238845 Luc Rousseau, <a href="/A238845/a238845.png">Proof of the formula</a>
%H A238845 Rémy Sigrist, <a href="/A238845/a238845_1.png">Colored scatterplot of the ordinal transform of the first 10000 terms</a>
%H A238845 Rodica Simion and Herbert S. Wilf, <a href="https://doi.org/10.1137/0607054">The distribution of prefix overlap in consecutive dictionary entries</a>, SIAM J. Algebraic Discrete Methods, 7(1986), no. 3, 470--475. MR0844051.
%F A238845 For all n > 0, a(n-1) = A000523(n) - A007814(n) + A209229(n) - A063524(n) = floor(log_2(n)) - v_2(n) + [exists(k,n==2^k)] - [n==1]. (see link) - _Luc Rousseau_, Dec 29 2017
%e A238845 8 = 1000 and 9 = 1001 have prefix overlap of 3, so a(8)=3.
%p A238845 # prefix overlap between n and n+1 in base b:
%p A238845 po:=proc(n,b) local t1,t2,l1,l2,c,L,i;
%p A238845 t1:=convert(n,base,b); l1:=nops(t1);
%p A238845 t2:=convert(n+1,base,b); l2:=nops(t2);
%p A238845 c:=0; L:=min(l1,l2);
%p A238845 for i from 1 to L do
%p A238845 if t1[l1+1-i] = t2[l2+1-i] then c:=c+1; else break; fi; od:
%p A238845 c;
%p A238845 end;
%p A238845 [seq(po(n,2),n=0..120)];
%t A238845 a[n_] := With[{v = IntegerExponent[n+1, 2]}, Floor[Log[2, n+1]] - v + Boole[n+1 == 2^v] - Boole[n == 0]]; Table[a[n], {n, 0, 90}] (* _Jean-François Alcover_, Feb 03 2018, after _Charles R Greathouse IV_ *)
%t A238845 pol[n_]:=Module[{c1=IntegerDigits[n,2],c2=IntegerDigits[n+1,2]},Total[ Split[ If[#[[1]]==#[[2]],1,0]&/@Thread[{c1,Take[c2,Length[c1]]}]][[1]]]];Array[pol,100,0] (* _Harvey P. Dale_, Jun 12 2020 *)
%o A238845 (Haskell)
%o A238845 import Data.List (unfoldr); import Data.Tuple (swap)
%o A238845 a238845 n = length $ takeWhile (== 0) $ zipWith (-) (bin n) (bin (n+1))
%o A238845 where bin = reverse . unfoldr
%o A238845 (\x -> if x == 0 then Nothing else Just $ swap $ divMod x 2)
%o A238845 -- _Reinhard Zumkeller_, Mar 22 2014
%o A238845 (PARI) a(n)=my(v=valuation(n+1,2)); logint(n+1,2) - v + (n+1==1<<v) - (n==0) ; \\ _Charles R Greathouse IV_, Dec 29 2017
%Y A238845 Cf. A076489, A239091.
%K A238845 nonn,base
%O A238845 0,5
%A A238845 _N. J. A. Sloane_, Mar 22 2014