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

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, 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, 6, 5, 6, 3, 6, 5, 6, 4, 6, 5, 6, 2, 6, 5, 6, 4, 6, 5, 6, 3, 6, 5, 6

Offset

0,5

Comments

The prefix overlap between two words is the length of their longest common prefix.

Links

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Luc Rousseau, Proof of the formula

Rémy Sigrist, Colored scatterplot of the ordinal transform of the first 10000 terms

Rodica Simion and Herbert S. Wilf, The distribution of prefix overlap in consecutive dictionary entries, SIAM J. Algebraic Discrete Methods, 7(1986), no. 3, 470--475. MR0844051.

Formula

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

Example

8 = 1000 and 9 = 1001 have prefix overlap of 3, so a(8)=3.

Maple

# prefix overlap between n and n+1 in base b:
po:=proc(n, b) local t1, t2, l1, l2, c, L, i;
t1:=convert(n, base, b); l1:=nops(t1);
t2:=convert(n+1, base, b); l2:=nops(t2);
c:=0; L:=min(l1, l2);
for i from 1 to L do
if t1[l1+1-i] = t2[l2+1-i] then c:=c+1; else break; fi; od:
c;
end;
[seq(po(n, 2), n=0..120)];

Mathematica

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

Prog

(Haskell)
import Data.List (unfoldr); import Data.Tuple (swap)
a238845 n = length $ takeWhile (== 0) $ zipWith (-) (bin n) (bin (n+1))
where bin = reverse . unfoldr
(\x -> if x == 0 then Nothing else Just $ swap $ divMod x 2)
-- Reinhard Zumkeller, Mar 22 2014
(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

Crossrefs

Cf. A076489, A239091.

Sequence in context: A352897 A280363 A217743 * A093873 A353371 A353334

Adjacent sequences: A238842 A238843 A238844 * A238846 A238847 A238848

Keyword

nonn,base

Author

N. J. A. Sloane, Mar 22 2014

Status

approved