Scenario

A young boy has been found murdered in England and crime scene investigators obtain a DNA sample on the boy’s body that belongs to someone else – another male person.

The police set up a wide network and collect the DNA of three-quarters of a million volunteers.

After a long period of massive testing they find no match to the DNA on the body.

Then, as the police scan their records, they notice a man who was living near where the body was found is not on their DNA volunteer list.

The man is eventually located in Portugal and his DNA tested. A positive match results.

Solely on the basis of the DNA testing, is the man more or less likely to be guilty?

Some assumptions

• The accuracy of the DNA test is 1 in one- million. That is, the probability the test returns a false positive is 0.000001
• The testing of volunteers is independent: that is, the results of the test of any one person is independent of the results of the test for any other person.

Calculation

Each DNA test is correct with probability 0.99999.

The probability that each of the 750,001 independent tests is correct is .

That is, it is more likely than not, that at least one of the DNA tests will prove to be a match, irrespective of whether any one of those tested committed the crime.

In other words the DNA evidence alone is insufficient to determine guilt to even likelihood, let alone to a high degree of probability.

Suspicions

Of course we are suspicious that the DNA of the man who was found, after he had not volunteered, matched that on the body. And we are suspicious because the man was found in Portugal after having left England.

But the totality of the DNA tests is not sufficient, of and by itself, to convict with a high degree of probability.

The paradox of testing less often

One of the medical examiners involved in the case reflected that the evidence might have worked better in favor of the prosecution  if they had tested fewer people.

For example, if the medical examiner had tested only 30,000 volunteers there would be a  chance that each of the DNA tests was correct.

At the other extreme – of only testing the suspect in Portugal – there would be a chance of being correct.

The moral, of course, is that even with very small probabilities of being wrong, when large numbers are tested it can quickly become more likely than not that a testing error – that is, a false positive –  is made.

Acknowledgments

I concocted this story from scenarios borrowed from Heather Dallas and David Mumford, and Tim Gowers (problem 45)

 

 

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: 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 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 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.

James Tanton (@jamestanton ) asked the folllowing question on Twitter, Wednesday, August 8, 2018

Which N have a factor k<N so that N and k have the same number of 1s in binary? (Each power of two: Yes. Each odd prime: No.)

To investigate this computationally (in the absence of any other thoughts) I defined a function, TantonQ, in Mathematica that would tell me if an integer was one of those sought by James’ question:

TantonQ[n_] := Length[Cases[IntegerDigits[Divisors[n], 2], L_ /; Count[L, 1] == Count[IntegerDigits[n, 2], 1]]] > 1 

This just takes all the base 2 representations of the divisors of an integer n, and selects those with the same number of 1s as in the base 2 representation of n. Of course there’s always at least one of these, coming from n itself, so n is of the type to fulfill James’ criterion if, and only if, there at least two such.

With this function in hand we can select from the first 500 integers, for example, those for which TantonQ is true:

T = Cases[Range[500], n_ /; TantonQ[n]]

with the result

{2, 4, 6, 8, 9, 10, 12, 14, 16, 18, 20, 21, 22, 24, 26, 28, 30, 32, 33, 34, 35, 36, 38, 40, 42, 44, 45, 46, 48, 49, 50, 52, 54, 56, 58, 60, 62, 64, 65, 66, 68, 70, 72, 74, 75, 76, 78, 80, 82, 84, 86, 88, 90, 92, 93, 94, 96, 98, 100, 102, 104, 105, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126, 128, 129, 130, 132, 133, 134, 135, 136, 138, 140, 142, 144, 146, 148, 150, 152, 153, 154, 155, 156, 158, 160, 161, 162, 164, 165, 166, 168, 170, 172, 174, 176, 178, 180, 182, 184, 186, 188, 189, 190, 192, 194, 195, 196, 198, 200, 202, 204, 206, 208, 210, 212, 214, 216, 217, 218, 220, 222, 224, 225, 226, 228, 230, 232, 234, 236, 238, 240, 242, 244, 246, 248, 250, 252, 254, 256, 258, 259, 260, 262, 264, 266, 267, 268, 270, 272, 273, 274, 276, 278, 279, 280, 282, 284, 286, 288, 290, 292, 294, 295, 296, 297, 298, 300, 302, 304, 306, 308, 309, 310, 312, 314, 315, 316, 318, 320, 322, 324, 326, 327, 328, 330, 332, 334, 336, 338, 340, 341, 342, 344, 345, 346, 348, 350, 352, 354, 356, 358, 360, 362, 364, 366, 368, 370, 372, 374, 376, 378, 380, 381, 382, 384, 385, 386, 387, 388, 390, 392, 394, 395, 396, 398, 400, 402, 403, 404, 406, 408, 410, 412, 414, 416, 417, 418, 420, 422, 424, 426, 428, 430, 432, 434, 436, 438, 440, 441, 442, 444, 446, 448, 450, 452, 453, 454, 456, 458, 460, 462, 464, 465, 466, 468, 470, 472, 474, 476, 478, 480, 482, 484, 486, 488, 490, 492, 494, 496, 498, 500}

This sequence of numbers is not – at the time of writing – in the Online Encyclopedia of Integer Sequences (OEIS).

A cursory glance indicates that these numbers jump about by 1s and 2s: each integer in the list, beyond the first, is either 1 or 2 greater then the integer before it.

To check this we can form a list of successive differences:

diffs = T[[2 ;; -1]] – T[[1 ;; -2]]

with the result

{2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2}

and – as we would expect – this sequence is also not in OEIS.

A plot of the sequence of 2s and 1s shows no obvious pattern in their arrangement:

 

Thinking that the running means of the sequence of 2s and 1s might converge I plotted the running mean, increasing n from 500 to 10,000:

N[Table[Mean[diffs[[1 ;; k]]], {k, 1, Length[diffs]}]];
ListPlot[%]

Not much indication of convergence there!

In summary, the numbers James Tanton seeks in his question can be obtained by starting with 2 and successively adding the terms of the sequence of 2s and 1s, above.

But to date, I have no real idea of the behavior of this sequence of 2s and 1s.

Postscript

August 9, 2018

What about runs of 2s and 1s? How long can runs be?

Pushing n to 10,000,000 we can calculate the values of the number of runs of 2s and 1s:

T = Cases[Range[10000000], n_ /; TantonQ[n]];
diffs = T[[2 ;; -1]] – T[[1 ;; -2]];
S = Split[diffs];
CountRunsOnes = Map[Length, Cases[S, L_ /; MemberQ[L, 1]]];
CountRunsTwos = Map[Length, Cases[S, L_ /; MemberQ[L, 2]]];
Union[CountRunsOnes]
Union[CountRunsTwos]

with the result:

{2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22}

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 139, 141, 142, 143, 144, 145, 146, 149, 151, 153, 154, 155, 156, 158, 159, 160, 161, 162, 163, 164, 167, 169, 171, 173, 174, 175, 179, 183, 185, 187, 188, 190, 191, 192, 193, 194, 195, 201, 204, 207, 215, 217, 219, 221, 223, 224, 225, 227, 232, 240, 243, 247, 249, 251, 252, 253, 254, 255, 256, 257, 258, 261, 265, 287, 289, 290, 293, 295, 303, 309, 316, 319, 338, 349, 351, 367, 379, 381, 382, 383, 384, 399, 403, 412, 413, 415, 421, 431, 449, 507, 509, 515, 539, 557, 560, 575, 751, 759, 891, 951, 981, 1403, 1887, 2047}

so, to hazard a guess, I would imagine:

• the runs of 1s have even length, and there are runs of 1s of any given even length;
• there are runs of 2s of any given length.

How often do 1s and 2s appear in the list of differences?

Print[“1s occur about “, N[Count[diffs, 1]/Length[diffs], 3]*100, “% of the time”]
Print[“2s occur about “, N[Count[diffs, 2]/Length[diffs], 3]*100, “% of the time”]

1s occur about 34.7% of the time
2s occur about 65.3% of the time

So, an approximate ratio of 2:1 in favor of the 2s.

Terry Tao has given a clear argument for the case that it is indeed not necessary to be a genius to do mathematics:

“The answer is an emphatic NO. In order to make good and useful contributions to mathematics, one does need to work hard, learn one’s field well, learn other fields and tools, ask questions, talk to other mathematicians, and think about the “big picture”. And yes, a reasonable amount of intelligence, patience, and maturity is also required. But one does not need some sort of magic “genius gene” that spontaneously generates ex nihilo deep insights, unexpected solutions to problems, or other supernatural abilities.”

 

 

And as to sufficiency, Randy Rainbow gives a compelling argument that being a very stable genius is not sufficient to ensure one has the reasonable amount of intelligence, patience, and maturity that Terry Tao sees as a requisite to be good at mathematics (or pretty much anything else, in fact):

 

 

Alexander Bogomolny passed away on  July 7, 2018.

I learned of his passing via a tweet from his colleague and friend Nassim Taleb.

Alexander’s passing has left a huge hole in my heart.

Every day I would check what new problem he had posted on Twitter, or what Twitter conversation he was conducting with people about problems he had posted.

In recent time Alexander had become very engaged with his followers. He did not suffer fools and would tell people if he thought they were being foolish, yet he was very encouraging to one and all, no matter with what little expertise or naïveté we might tackle a problem.

I recall how he was delighted when I illustrated some his inequalities with Mathematica contour plots, soon to be surpassed in that regard by Nassim Taleb.

When I was making daily posting of chapters of a novel I was writing, Alexander was one of my closest followers. He cheered me on each and every day and supported me for many months. In the end the title of the book was his suggestion.

Twitter does not, I imagine lead to many genuine love affairs. I loved Alexander Bogomolny. I still do.

Rest in peace dear friend.

---

Addendum:

Svetlana Bogomolny (@SvetlanaBogom13) sent the following message about Alexander:

 

Binary disjoints

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 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 positive integer such that  is divisible by all its binary disjoints, for versus :

and then here’s a plot of the natural logarithm of versus:

 

My colleague Mercedes McGowen has been experimenting with iterated squaring modulo a prime and has, to date, been unable to find a pure cycle of length 5.

Mercedes was originally inspired by A. K.  Dewdney’s article “Computer recreations: A computer microscope zooms in for a look at the most complex object in mathematics;”, Scientific American. August, 1985. pp. 16-24 :

“Confronted with infinite complexity it is comforting to take refuge in the finite. Iterating a squaring process on a finite set of ordinary integers also gives rise to interesting structures. The structures are not geometric but combinatorial.”

A clue came unexpectedly from a recent arxiv paper of Roger Heath-Brown.

Recall that if is prime then the multiplicative order of in the field of integers modulo is the least integer such that .

Heath-Brown remarks (p. 2) that if is the squaring map then for , with odd multiplicative order , there is a pure cycle of length for the iterates of where is the multiplicative order of .

So if we want a pure cycle for iterated squaring of length 5 then we choose and seek a prime for which has an element of multiplicative order 31.

As one readily checks, through a computational search, the prime 311 has this property: namely 265 has multiplicative order 31 in .

The pure cycle of order 5 for the squaring map in   is

meaning that and .

A further search indicates the same is true for the prime 373: a 5-cycle for the squaring map in  is .

In fact there are 6 such 5-cycles for :

---

Here’s a short list of primes for which has a 5-cycle in :

311, 373, 683, 1117, 1303, 1427, 1489, 1613, 1861, 2357, 2543, 2729, 2791, 3163, 3659, 3907, 4093, 4217, 4651, 5023, 5147, 5209, 5333, 5519, 5581, 5953, 6263, 6449, 6883, 7069, 7193, 7937, 8123, 8681, 8867, 8929, 9239, 9859, 10169, 10789, 11161, 11471, 11657, 11719, 12277, 12401, 12959, 13331, 14323, 14447, 14633, 15377, 15439, 15749, 16183, 16369, 16493, 16741, 16927, 17299, …

and these are just primes congruent to 1 mod 31 (OEIS).

Is this, in fact, true: the squaring map  has a 5-cycle in , for if and only if ?

 

Of course when one reflects on it there is nothing special about the number 5: we can find a d-cycle for iterated squaring (mod q), q prime, when has an element of order

 

New delights and unexpected connections

The late, great, Bill Thurston once wrote:

William Thurston

“Mathematics has a remarkable beauty, power, and coherence, more than we could have ever expected. It is always changing, as we turn new corners and discover new delights and unexpected connections with old familiar grounds.”

 

In the hope of capturing a small glimpse of Thurston’s vision of turning new corners and discovering new delights, I want to talk a little about an interesting sequence of whole numbers.  So enchanting is this sequence that it holds numerous opportunities for investigation by school students, and challenges for research mathematicians.

 

The Wythoff array

The sequence I want to discuss comes from the so-called Wythoff array.

This is an infinite array of whole numbers, the beginning of which looks as follows:

The first row might look familiar: it is, apart from a missing “1”, just the sequence of Fibonacci numbers. As we know, the Fibonacci numbers are determined by the recurrence and the initial conditions for and .

As you can check from the beginning of the array, shown above, the numbers in each row, are, after the first two, just the sum of the two preceding numbers in the row.  Each row, in other words, is just a variant of the Fibonacci sequence: what changes is the pair of initial conditions – the first two numbers – in each row.

This infinite array was named after the Dutch mathematician Willem Abraham Wythoff (1865 – 1939), although Wythoff himself did not write down the array:  D. R.Morrison, in a 1980 article, “A Stolarsky Array of Wythoff Pairs”,  named the array after Wythoff because of Wythoff’s investigations of Wythoff’s game.

The entries in the Wythoff array are easily describable in terms of a recurrence for the entry in the row and column:

where and where , for a real number is the floor of : the greatest integer .

There is a way to write the entries of the Wythoff array directly in terms of the Fibonacci numbers, detailed in 1994 by Clarke Kimberling:

The Wythoff array has several interesting features, not the least of which is that every positive integer occurs exactly once in exactly one row of the array.

Question: Can you devise a method (an algorithm?) which, given a positive integer , finds the position – the row and column – of .

The diagonal elements

We will denote the diagonal entry  of the Wythoff array by . The recurrence for the general entries of the Wythoff array then gives the following formula to calculate the diagonal entries:

The diagonal entries  can also be written in terms of a Fibonacci-like recurrence, but with variable coefficients:

where the coefficients are rational numbers dependent on .

To see that this possible and to get an explicit formula for  and for   we simply substitute  into , use the relation and equate coefficients of and.

The result is:

The  and are rational numbers and their first few values are:

A plot of  and shows irregular oscillatory behavior around the number 1 ( in blue and in red):

Computations

It is easy enough to implement the Wythoff array in a spreadsheet.

Here’s the result of calculating the first entries of the Wythoff array in Excel, using the built-in Excel floor(- ,1) function:

and here are the Excel formulas for the first 4 rows and columns:

Calculations for the diagonal entries are also easy to implement in Excel:

 

 

Bill Bonacci represented the commercial interests of the merchants of Pisa in Bejaia, a Mediterranean port in northeastern Algeria. In that capacity he introduced his son Leonardo, while still a child, to principles of accounting with an eye to Leonardo’s future employment.

Leonardo was introduced to teachers of accounting and soon learned the practices of a wide variety of regions including Egypt, Syria, Greece, Sicily and Provence. He was especially attracted to the numerical notational systems of the Hindus and Arabs and in his early 30’s, when he had returned to Pisa, he wrote a book on the art of calculation.

This book “Liber Abaci” influenced the accounting practices of business in Italy and Europe in general and the numerical notation system Leonardo introduced gradually become the de facto standard for book keeping and accounting.

In his book there are many contrived scenarios whose function seems mainly to introduce a variety of numerical calculations so that readers could practice the novel numeration systems.

One problem in Leonardo’s book so intrigued people that it has become a favorite of almost all people who think even a little about mathematics.

Leonardo was enchanted by the fact that male drone bees are born from a queen bee’s unfertilized egg, so a male drone bee has no father. Female bees have both a mother and a father. So if one looks at the family tree of a male drone bee one sees something like this:

Parents	1
Grandparents	2
Great grandparents	3
Great-great grandparents	5
Great-great-great grandparents	8

 

Leonardo said to himself: “Un giorno questi numeri sbloccheranno il segreto della natura e spiegheranno perché un drone non ha un padre”

(“Someday these numbers will unlock the secret of nature and will explain why a drone does not have a father”)

In his book he continued this backward calculation of the number of drone ancestors, but changed the setting of the problem. Maybe because it was getting difficult to name the ancestors beyond great-great-great-grandparents, or perhaps for some other reason, Leonardo changed this real scenario into an imaginary one of rabbits breeding, and counted the number of rabbits alive at discrete units of time, so inventing (but not for the first time in history) the famous Fi-bonacci sequence.