login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Length of the longest common substring in binary representations of n and n^2.
2

%I #19 Mar 31 2019 09:30:48

%S 1,2,1,3,2,2,2,4,3,3,2,3,3,3,3,5,4,4,4,4,3,3,2,4,4,4,5,4,4,4,4,6,5,5,

%T 4,5,4,4,4,5,6,3,3,4,4,2,3,5,5,4,4,5,5,6,5,5,5,5,5,5,5,5,5,7,6,6,5,6,

%U 5,5,5,6,5,5,5,4,4,4,4

%N Length of the longest common substring in binary representations of n and n^2.

%H Robert Israel, <a href="/A177062/b177062.txt">Table of n, a(n) for n = 1..10000</a>

%p f:= n -> length(StringTools:-LongestCommonSubString(convert(convert(n,binary),string),convert(convert(n^2,binary),string))):

%p map(f, [$ 1..100]); # _Robert Israel_, Sep 13 2016

%t longestRun[pairs_] := Split[pairs, Equal @@ #1 && Equal @@ #2 &] // Sort[#, Length[#1] < Length[#2] &] & // Last; a[n_] := (bits1 = IntegerDigits[n, 2]; bits2 = IntegerDigits[n^2, 2]; longestRun /@ ListConvolve[ Reverse[bits1], bits2, {1, -1}, -1, List, List] // Sort[#, Length[#1] < Length[#2] &] & // Last // Length); a /@ Range[79] (* _Jean-François Alcover_, Jun 05 2013 *)

%t Table[Length[LongestCommonSubsequence[IntegerDigits[n^2, 2], IntegerDigits[ n, 2]]], {n, 1, 100}] (* _Vladimir Reshetnikov_, Apr 26 2016 *)

%o (Haskell)

%o import Data.List

%o toBinary 0 = []

%o toBinary n = toBinary (n `div` 2) ++ [odd n]

%o lcstr xs ys = maximum . concat $ [f xs' ys | xs' <- tails xs] ++ [f xs ys' | ys' <- drop 1 $ tails ys] where f xs ys = scanl g 0 $ zip xs ys; g z (x, y) = if x == y then z + 1 else 0

%o a = [lcstr (toBinary $ n) (toBinary $ n^2) | n <- [1..]]

%Y Cf. A276692

%K base,easy,nonn

%O 1,2

%A _Vladimir Reshetnikov_, May 02 2010