|
%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
|
