login
Number of divisible pairs of positive integers up to n with no binary carries.
7

%I #12 Jul 27 2019 14:57:51

%S 0,0,1,1,3,3,4,4,7,7,9,9,12,12,13,13,17,17,19,19,22,22,23,23,28,28,29,

%T 29,31,31,32,32,37,37,39,39,44,44,45,45,50,50,52,52,54,54,55,55,62,62,

%U 64,64,66,66,68,68,72,72,73,73,76,76,77,77,83,83,85,85

%N Number of divisible pairs of positive integers up to n with no binary carries.

%C Two positive integers are divisible if the first divides the second, and they have a binary carry if the positions of 1's in their reversed binary expansion overlap.

%C a(2k+1) = a(2k), since an odd number and any divisor will overlap in the last digit. Additionally, a(2k+2) > a(2k+1) because the pair {1,2k+2} is always valid. Therefore, every term appears exactly twice. - _Charlie Neder_, Apr 02 2019

%e The a(2) = 1 through a(11) = 9 pairs:

%e {1,2} {1,2} {1,2} {1,2} {1,2} {1,2} {1,2} {1,2} {1,2} {1,2}

%e {1,4} {1,4} {1,4} {1,4} {1,4} {1,4} {1,4} {1,4}

%e {2,4} {2,4} {1,6} {1,6} {1,6} {1,6} {1,6} {1,6}

%e {2,4} {2,4} {1,8} {1,8} {1,8} {1,8}

%e {2,4} {2,4} {2,4} {2,4}

%e {2,8} {2,8} {2,8} {2,8}

%e {4,8} {4,8} {4,8} {4,8}

%e {1,10} {1,10}

%e {5,10} {5,10}

%t Table[Length[Select[Tuples[Range[n],2],Divisible@@Reverse[#]&&Intersection[Position[Reverse[IntegerDigits[#[[1]],2]],1],Position[Reverse[IntegerDigits[#[[2]],2]],1]]=={}&]],{n,0,20}]

%Y Cf. A006218, A019565, A050315, A070939, A080572, A247935, A267610.

%Y Cf. A325095, A325096, A325101, A325103, A325104, A325105, A325106, A325124.

%K nonn

%O 0,5

%A _Gus Wiseman_, Mar 29 2019