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
Examples
8 = 1000 and 9 = 1001 have prefix overlap of 3, so a(8)=3.
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.
Programs
-
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
-
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 *) -
PARI
a(n)=my(v=valuation(n+1,2)); logint(n+1,2) - v + (n+1==1<
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
Comments