The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A238845 Prefix overlap between binary expansions of n and n+1. 4
 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 (list; graph; refs; listen; history; text; internal format)
 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<

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified August 10 15:59 EDT 2024. Contains 375057 sequences. (Running on oeis4.)