A307230 Number of divisible pairs of distinct positive integers up to n with at least one binary carry.

0, 0, 0, 1, 1, 2, 4, 5, 5, 7, 8, 9, 11, 12, 14, 17, 17, 18, 21, 22, 24, 27, 29, 30, 32, 34, 36, 39, 42, 43, 49, 50, 50, 53, 54, 57, 60, 61, 63, 66, 68, 69, 74, 75, 78, 83, 85, 86, 88, 90, 93, 96, 99, 100, 105, 108, 111, 114, 116, 117, 125, 126, 128, 133, 133

Offset: 0

Author

Gus Wiseman, Mar 29 2019

Keywords

• nonn

Comments

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

Examples

			The a(3) = 1 through a(12) = 11 pairs:
  {1,3}  {1,3}  {1,3}  {1,3}  {1,3}  {1,3}  {1,3}  {1,3}   {1,3}   {1,3}
                {1,5}  {1,5}  {1,5}  {1,5}  {1,5}  {1,5}   {1,5}   {1,5}
                       {2,6}  {1,7}  {1,7}  {1,7}  {1,7}   {1,7}   {1,7}
                       {3,6}  {2,6}  {2,6}  {1,9}  {1,9}   {1,9}   {1,9}
                              {3,6}  {3,6}  {2,6}  {2,6}   {2,6}   {2,6}
                                            {3,6}  {3,6}   {3,6}   {3,6}
                                            {3,9}  {3,9}   {3,9}   {3,9}
                                                   {2,10}  {1,11}  {1,11}
                                                           {2,10}  {2,10}
                                                                   {4,12}
                                                                   {6,12}
		

Crossrefs

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

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

Programs

Mathematica

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

Formula

a(n) = A325124(n) - n.