Binary disjoints of an integer

Binary disjoints

James Tanton

James Tanton (@jamestanton) tweeted on April 14, 2018:

“The disjoints of a number N are all the k<N such that the binary representations of k and N have no 1s in common positions. eg The disjoints of 10 are 1, 4 and 5. (Binary: 1010 and 1, 100, 101). If N is a multiple of each of its disjoints, must N be two less than a power of 2?”

To distinguish the base 2 case from other possible bases we will call the binary disjoints of a positive integer n the set of integers $1 \leq k < n$ for which binary representations of k and n have no 1s in common positions.

Here’s a naive and probably inefficient way of calculating the binary disjoints of a positive integer using Mathematica, with the saving grace that it works:

binarydisjoints[n0_] := Module[{n = n0, func, gunc, A1, A2, A3},

func[L_] := Flatten[Prepend[L, Table[0, Length[IntegerDigits[n, 2]] – Length[L]]]];
gunc[L_] := L + IntegerDigits[n, 2];
A1 = IntegerDigits[Range[n – 1], 2]; A2 = Map[func, A1];
A3 = Map[gunc, A2];
Complement[Range[Length[A3]], Flatten[Position[A3, x_ /; MemberQ[x, 2]]]]]

and here’s a table for the sets of binary disjoints of 1 through 25:

Binary disjoint friends

Note that 9 and 25 have the same set of binary disjoints: {2, 4, 6}.

Let’s call such a pair “binary disjoint friends”.

What other pairs of binary disjoint friends can you find?

Sum of binary disjoints

Notice that 10 is the sum of the set of its binary disjoints {1, 4, 5} : 1+4+5 = 10.

Is 10 the only positive integer that is equal to the sum of its set of binary disjoints?

The sum of the binary disjoints of n has irregular behavior as a function of n:

However, the average of binary disjoints of n behaves somewhat more regularly as a function of n:

Numbers that are multiples of all their binary disjoints

To begin to get some data on James Tanton’s question about which numbers are multiples of each of their binary disjoints we can carry out a search using Mathematica:

L = {};
n = 1;
While[n <= 2000, If[Union[Mod[n, disjoints[n]]] == {0}, L = {L, n}];
n++]
L = Flatten[L]

with the result {2, 6, 12, 14, 30, 60, 62, 126, 252, 254, 510, 1020, 1022} for n up to 2000.

First, we see that there are numbers not 1 or 2 away from a power of 2: 12, 60, 252, 1020.

Second , we note that all the numbers in this list are even. Is this always true? That is, can an odd number never be a multiple of all its binary disjoints?

Third, we note that neither this sequence, nor this sequence divided by 2, is – yet – in the Online Encyclopedia of Integer Sequences.

Below is a plot of the $k^{th}$ positive integer $n_k$ such that $n_k$ is divisible by all its binary disjoints, for $k=1,\ldots$ versus $k$ :