Crikey Math

Having fun exploring mathematics

  • Home
  • About
  • Blog
  • Contribute
en English
af Afrikaanssq Albanianam Amharicar Arabichy Armenianaz Azerbaijanieu Basquebe Belarusianbn Bengalibs Bosnianbg Bulgarianca Catalanceb Cebuanony Chichewazh-CN Chinese (Simplified)zh-TW Chinese (Traditional)co Corsicanhr Croatiancs Czechda Danishnl Dutchen Englisheo Esperantoet Estoniantl Filipinofi Finnishfr Frenchfy Frisiangl Galicianka Georgiande Germanel Greekgu Gujaratiht Haitian Creoleha Hausahaw Hawaiianiw Hebrewhi Hindihmn Hmonghu Hungarianis Icelandicig Igboid Indonesianga Irishit Italianja Japanesejw Javanesekn Kannadakk Kazakhkm Khmerko Koreanku Kurdish (Kurmanji)ky Kyrgyzlo Laola Latinlv Latvianlt Lithuanianlb Luxembourgishmk Macedonianmg Malagasyms Malayml Malayalammt Maltesemi Maorimr Marathimn Mongolianmy Myanmar (Burmese)ne Nepalino Norwegianps Pashtofa Persianpl Polishpt Portuguesepa Punjabiro Romanianru Russiansm Samoangd Scottish Gaelicsr Serbianst Sesothosn Shonasd Sindhisi Sinhalask Slovaksl Slovenianso Somalies Spanishsu Sudanesesw Swahilisv Swedishtg Tajikta Tamilte Teluguth Thaitr Turkishuk Ukrainianur Urduuz Uzbekvi Vietnamesecy Welshxh Xhosayi Yiddishyo Yorubazu Zulu

Binary disjoints of an integer

April 15, 2018 By Gary Ernest Davis

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:

and then here’s a plot of the natural logarithm \log(n_k) of n_k versusk:

 

http://www.crikeymath.com/wp-content/uploads/2017/09/crikey.wav

Filed Under: Uncategorized

Recent Posts

  • Does the DNA test say guilty or not guilty?
  • The Turtleback Diagram for Conditional Probability
  • Numbers that, base 2, are blindingly obviously divisible by 3
  • A mysterious sequence of 1s and 2s
  • Does one have to be a genius to do mathematics? Neither necessary nor sufficient.
  • Alexander Bogomolny
  • Binary disjoints of an integer
  • A cycle of length 5 for iterated squaring modulo a prime
  • The diagonal of the Wythoff array
  • Leonardo Bigollo, accountant, son of Bill Bonacci

Archives

Copyright © 2023 · Dynamik Website Builder on Genesis Framework · WordPress · Log in