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

Numbers that, base 2, are blindingly obviously divisible by 3

August 9, 2018 By Gary Ernest Davis

James Tanton ( @jamestanton ) asked, on Twitter:

“For which N is there a multiple of N with N 1s and N 0s when written in binary?”

Computationally we can come up with a simple procedure to test if a number n has k 0s and k 1s in its base 2 representation:

BinaryTestQ[k0_, n0_] := Module[{k = k0, n = n0, A}, A = IntegerDigits[n, 2]; Count[A, 0] == k && Count[A, 1] == k]

Then we can take, for example, k=3 and let n run through multiples of 3 until we, hopefully, get a multiple of 3 with 3 0s and 3 1s in its binary represenation:

k = 3;
n = k;
While[BinaryTestQ[k, n] == False, n = n + k]
n

with the result: 42

How might we think about getting the result 42 without running through this blind computation?

It’s sort of clear that there aren’t too may choices for a number n that is a multiple of 3 and has 3 0s and 3 1s in its base 2 representation. Since the base 2 representation begins with 1, this allows us 5 places to fill with 3 0s and 2 1s: \binom{5}{3} = 10 possibilities. Of course not all these will be divisible by 3, and in fact only one of them – 42 – is divisible by 3.

Is there some obvious way to “see” that 42 is divisible by 3, just by looking at their respective base 2 digits?

IntegerDigits[3,2]

IntegerDigits[42,2]

{1, 1}

{1, 0, 1, 0, 1, 0}

Not blindingly obviously – we don’t immediately “see” a {1,1} sitting in the base 2 digits of 42.

We could think of this as an exploding dots division problem in a 1\leftarrow 2 machine:

 

Stare as we might, we do not see the dot pattern for 3 (base 2) in the dot pattern for 42 (base 2).

However , by some cunning unexploding of dots – thanks to James Tanton for this – we can begin to see the dot pattern for 3 occurring in various  numbers that add to 42:

so we have written 42 as the sum 24 + 12 +6 and each of the three terms in this sum has a base 2 representation in which is it blindingly obvious – just by looking – that it is divisible by 3.

In fact the largest multiple of 3 less than 42, for which one can immediately see, by spotting the pattern for the base 2 representation of 3, is 30, which has base 2 digits {1, 1, 1, 1, 0}.

Then 40 – 32 = 12, which as we have seen, is a number that is blindingly obviously divisible by 3.

This suggests there might be a greedy algorithm to decide, by just looking, whether a number is a multiple of 3.

Such an algorithm would depend on knowing a list of numbers that are blindingly obviously divisible by 3.

One way to find such numbers is to look for obstructions to even length runs of 1s in the base 2 representation.

The piece of code below does this by prepending a symbol “a”  to the integer digits of n, base 2, and appending a “b” similarly.  Then the excluded patterns are those of the form {a,1,0}, {0,1,0} and {0,1,b}:

TestItQ[n_] := MemberQ[Partition[Append[Prepend[IntegerDigits[n, 2], a], b], 3, 1], L_ /; L == {a, 1, 0} || L == {0, 1, 0} || L == {0, 1, b}] == False

Cases[Range[260], n_ /; Mod[n, 3] == 0 && TestItQ[n]]

with the result

{3,  6,  12,  15,  24,  27,  30,  48,  51,  54,  60,  63,  96,  99,  102,  108,  111,  120,  123,  126,  192,  195,  198,  204,  207,  216,  219,  222,  231,  240,  243,  246,  252,  255}

These numbers are all, by choice, divisible by 3. Let’s divide them all by 3 and see if the resulting list:

{1,  2,  4,  5,  8,  9,  10,  16,  17,  18,  20,  21,  32,  33,  34,  36,  37,  40,  41,  42,  64,  65,  66,  68,  69,  72,  73,  74,  77,  80,  81,  82,  84,  85}

is on OEIS.

Indeed it is!

OEIS identifies this as the list of Fibbinary numbers – those numbers whose base 3 representation contains no consecutive 1s.

So it looks like, but we have not yet proven, that the numbers that are blindingly obviously divisible by 3 are just 3 times Fibbinary numbers: 3 times those numbers that have no consecutive 1s in their base 2 representation. And of course we can generate those at will. An alternative characterization of the Fibbinary numbers is they are those n for which \binom{3n}{n} is odd.

This allows us to easily calculate the blindingly obviously multiples of 3 up to, for exanmple, 5,000:

 3*Cases[Range[5000], n_ /; OddQ[Binomial[3*n, n]]]

with the result

{3, 6, 12, 15, 24, 27, 30, 48, 51, 54, 60, 63, 96, 99, 102, 108, 111, 120, 123, 126, 192, 195, 198, 204, 207, 216, 219, 222, 240, 243, 246, 252, 255, 384, 387, 390, 396, 399, 408, 411, 414, 432, 435, 438, 444, 447, 480, 483, 486, 492, 495, 504, 507, 510, 768, 771, 774, 780, 783, 792, 795, 798, 816, 819, 822, 828, 831, 864, 867, 870, 876, 879, 888, 891, 894, 960, 963, 966, 972, 975, 984, 987, 990, 1008, 1011, 1014, 1020, 1023, 1536, 1539, 1542, 1548, 1551, 1560, 1563, 1566, 1584, 1587, 1590, 1596, 1599, 1632, 1635, 1638, 1644, 1647, 1656, 1659, 1662, 1728, 1731, 1734, 1740, 1743, 1752, 1755, 1758, 1776, 1779, 1782, 1788, 1791, 1920, 1923, 1926, 1932, 1935, 1944, 1947, 1950, 1968, 1971, 1974, 1980, 1983, 2016, 2019, 2022, 2028, 2031, 2040, 2043, 2046, 3072, 3075, 3078, 3084, 3087, 3096, 3099, 3102, 3120, 3123, 3126, 3132, 3135, 3168, 3171, 3174, 3180, 3183, 3192, 3195, 3198, 3264, 3267, 3270, 3276, 3279, 3288, 3291, 3294, 3312, 3315, 3318, 3324, 3327, 3456, 3459, 3462, 3468, 3471, 3480, 3483, 3486, 3504, 3507, 3510, 3516, 3519, 3552, 3555, 3558, 3564, 3567, 3576, 3579, 3582, 3840, 3843, 3846, 3852, 3855, 3864, 3867, 3870, 3888, 3891, 3894, 3900, 3903, 3936, 3939, 3942, 3948, 3951, 3960, 3963, 3966, 4032, 4035, 4038, 4044, 4047, 4056, 4059, 4062, 4080, 4083, 4086, 4092, 4095, 6144, 6147, 6150, 6156, 6159, 6168, 6171, 6174, 6192, 6195, 6198, 6204, 6207, 6240, 6243, 6246, 6252, 6255, 6264, 6267, 6270, 6336, 6339, 6342, 6348, 6351, 6360, 6363, 6366, 6384, 6387, 6390, 6396, 6399, 6528, 6531, 6534, 6540, 6543, 6552, 6555, 6558, 6576, 6579, 6582, 6588, 6591, 6624, 6627, 6630, 6636, 6639, 6648, 6651, 6654, 6912, 6915, 6918, 6924, 6927, 6936, 6939, 6942, 6960, 6963, 6966, 6972, 6975, 7008, 7011, 7014, 7020, 7023, 7032, 7035, 7038, 7104, 7107, 7110, 7116, 7119, 7128, 7131, 7134, 7152, 7155, 7158, 7164, 7167, 7680, 7683, 7686, 7692, 7695, 7704, 7707, 7710, 7728, 7731, 7734, 7740, 7743, 7776, 7779, 7782, 7788, 7791, 7800, 7803, 7806, 7872, 7875, 7878, 7884, 7887, 7896, 7899, 7902, 7920, 7923, 7926, 7932, 7935, 8064, 8067, 8070, 8076, 8079, 8088, 8091, 8094, 8112, 8115, 8118, 8124, 8127, 8160, 8163, 8166, 8172, 8175, 8184, 8187, 8190, 12288, 12291, 12294, 12300, 12303, 12312, 12315, 12318, 12336, 12339, 12342, 12348, 12351, 12384, 12387, 12390, 12396, 12399, 12408, 12411, 12414, 12480, 12483, 12486, 12492, 12495, 12504, 12507, 12510, 12528, 12531, 12534, 12540, 12543, 12672, 12675, 12678, 12684, 12687, 12696, 12699, 12702, 12720, 12723, 12726, 12732, 12735, 12768, 12771, 12774, 12780, 12783, 12792, 12795, 12798, 13056, 13059, 13062, 13068, 13071, 13080, 13083, 13086, 13104, 13107, 13110, 13116, 13119, 13152, 13155, 13158, 13164, 13167, 13176, 13179, 13182, 13248, 13251, 13254, 13260, 13263, 13272, 13275, 13278, 13296, 13299, 13302, 13308, 13311, 13824, 13827, 13830, 13836, 13839, 13848, 13851, 13854, 13872, 13875, 13878, 13884, 13887, 13920, 13923, 13926, 13932, 13935, 13944, 13947, 13950, 14016, 14019, 14022, 14028, 14031, 14040, 14043, 14046, 14064, 14067, 14070, 14076, 14079, 14208, 14211, 14214, 14220, 14223, 14232, 14235, 14238, 14256, 14259, 14262, 14268, 14271, 14304, 14307, 14310, 14316, 14319, 14328, 14331, 14334}

How could we use such a table to check if a number – 13917 for example – is divisible by 3 ( in a blindingly obvious way)?

We look for the largest blindingly obviously multiple of 3 less than 13917, which is 13887. We subtract 13887 from 13917 to get 30, which is itself blindingly obviously a multiple of 3. So 13917 is a multiple of 3 , in a blindingly obvious way.


This excursion in how to tell in a blindingly obvious way – just by looking – that a number is a multiple of 3, was all in aid of checking which numbers whose base 2 digits have 3 0s and 3 1s and are multiples of 3.

We could course have adopted a simpler approach of listing the 10 possible numbers with 3 0s and 3 1s in their base 2 representation and reduced mod 3, but then we wouldn’t have understood why 42 is blindingly obviously divisible by 3, base 2.

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