login
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