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

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.