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

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, 29, 31, 31, 32, 32, 37, 37, 39, 39, 44, 44, 45, 45, 50, 50, 52, 52, 54, 54, 55, 55, 62, 62, 64, 64, 66, 66, 68, 68, 72, 72, 73, 73, 76, 76, 77, 77, 83, 83, 85, 85

Offset: 0

Author

Gus Wiseman, Mar 29 2019

Keywords

• nonn

Comments

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.

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

Examples

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

Crossrefs

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

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

Programs

Mathematica

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}]