Gary Ernest Davis

Random walks with memory: Background

February 7, 2018 By Gary Ernest Davis

A simple random walk on a graph (finite or infinite) is a sequence of transitions from a vertex to a neighboring vertex where the transition to a neighboring vertex is given by a probability distribution.

Commonly, in a so-called symmetric simple random walk, the probability of making a transition from a vertex v to a neighboring vertex is 1/p where p is the number of neighboring vertices for v: in other words the random walk transitions from vertex v to each of the neighboring vertices with equal probability. This assumes, of course, that the graph is locally finite: each vertex has only a finite number of neighboring vertices.

No backtracking

Simple random walks do not have memory: a random walk may transition from a vertex $v_0$ to a neighboring vertex $v_1$ and then make a next transition from $v_1$ back to $v_0$ .

Random walks that never do this – that is, have a memory of the previous vertex last visited and do not immediately re-visit it – are called random walks with no-backtracking. They are, in an obvious sense of the phrase, random walks with memory 1.

Random walks with memory 1 generally cover all, or a significant portion, of the graph faster then random walks with no memory. This takes some work to prove in particular cases, yet is sort of obvious in that a random walk with memory 1 is prohibited from going back to whence it immediately came, and so will spread to its other neighbors with slightly greater probability.

Yet a random walk pays a price for memory. On the graph $\mathbb{Z}$ consisting of the integers with an edge joining successive integers, a random walk with memory 1 must head off entirely in one direction after the first step:

Total recall

Random walks with total recall – also known, for obvious reasons, as self-avoiding walks – have an additional issue in that they commonly become trapped: because such a random walk remembers every place it has ever been, and typically gets stuck in a cul-de-sac where each of the possible next transition vertices have been visited already.

A self-avoiding walk that has not – yet – got stuck

Recent memory

This getting-stuck phenomenon can happen for a random walk on the infinite lattice $\mathbb{Z}\times \mathbb{Z}$ – where there is an edge from vertex (m,n) to vertex (p,q) if and only if $\vert m-p\vert + \vert n-q\vert = 1$ – when the random walk has memory 7:

Basic questions

So … for random walks with memory of the previous m sites visited where $1 \leq m \leq \infty$ there are a number of issues to settle:

With what probability will the random walk get trapped?
Will the walk be transient or recurrent? (A random walk is recurrent if it visits its starting position infinitely often with probability one and transient if it visits its starting position finitely often with probability one.)
At what rate will the random walk cover the graph (if at all)?

We know, for example, that for a simple random walk with memory 0 on the integer lattice $\mathbb{Z}^d$ that the walk is recurrent for d = 1 or 2 and transient for $d \geq 3$ . This is a basic result of George Polya. Recently, Mark Kempton has proved that a simple random walk with memory 1 (i.e. no backtracking) on the integer lattice $\mathbb{Z}^d$ is recurrent only for $d=2$ .

And then there’s Levy flights …

A Levy flight is a random walk in which step lengths are not discrete but are given by some – usually heavy-tailed- probability distribution.

One can think of foragers, such as birds pecking in a region and then flying off in a uniformly random direction for a random distance and pecking around that region before repeating the action.

Steps in a 2-dimensional Levy flight

A Levy flight, by definition, has memory 0. What, however, if we introduce a small $\epsilon > 0$ amount of memory, in that the Levy walk could not return to a region of radius $\epsilon > 0$ around its last transition point? What would such Levy flights with memory look like?

Fawn Nguyen’s grading question

February 6, 2018 By Gary Ernest Davis

Fawn Nguyen

Fawn Nguyen, a middle school math teacher, (@fawnpnguyen ‏on Twitter) has a post on her website about a grading issue that leads to some interesting mathematics.

Fawn writes:

Put these numbers in order from least to greatest: 5, 7, 2, 3, 1, 4, 6, 8
The correct order is 1, 2, 3, 4, 5, 6, 7, 8 (you’re welcome) — for a possible score of 8 points. How many points would this response earn?

1, 2, 4, 5, 3, 7, 8, 6

and she then discusses various methods for scoring different answers.

What metrics might we devise to measure the discrepancy between an answer and the correct answer, and assign a grade – perhaps a % – to any given answer?

I guess one question that comes to mind is how do we give a measure to the notion of just how different the arrangement 1, 2, 4, 5, 3, 7, 8, 6 is from the correct arrangement 1, 2, 3, 4, 5, 6, 7, 8 ?

Perhaps it helps to visualize these two different arrangements – the student answer versus the correct arrangement:

We can see directly from this plot that the total numerical size of the “error” – the sum of the absolute value of the difference between each place of the correct arrangement and the student arrangement – is 1+1+2+1+1+2 = 8.

If we think of this number as the discrepancy of the student arrangement, a discrepancy of 0 would indicate a correct arrangement.

How good, or bad, is a discrepancy of 8?

One way we might think about this is to note that any student arrangement will be a permutation of the numbers 1, 2, 3, 4, 5, 6, 7, 8.

There are 8! = 40320 permutations of the numbers 1 through 8.

What is the maximum possible discrepancy of a permutation of the numbers 1 through 8, and how does a discrepancy of 8 compare with that?

We can do a calculation in Mathematica as follows:

A = Permutations[Range[8]];

B = Table[Abs[A[[i]] – Range[8]], {i, 1, Length[A]}]

B = Map[Total, B]

Max[B]

with the result: 32

So the maximum possible discrepancy is 32 (and the minimum is 0).

One way we might score the student arrangement with discrepancy 8 is to give it a grade of (32-8)/32 = 3/4 = 75%, which would correspond to 6 points out of a possible 8 in Fawn’s points system.

What other arrangements might earn an identical score?

There are 327 permutations of the numbers 1 through 8 that have a discrepancy of 8: click here to see a list of the whole 327 permutations with discrepancy 8.

The possible values for the discrepancy of a permutation of the numbers 1 through 8 are just the even numbers from 0 through 32.

There are just 7 permutations wth discrepancy 2:

Using the grade assignment scheme above, each of these 7 arrangements would score (32-2)/32 = 15/16 which rounds to 94%, giving a score of 7.5 points out of 8.

There are 576 arrangements of the numbers 1 through 8 with discrepancy 32. An example is 5, 6, 8, 7, 2, 4, 1, 3. The scoring scheme would give this arrangement a score of (32-32)/32 = 0%.

An arrangement with discrepancy 10 would get a score of 69% (5.5 points out of 8), and one with discrepancy 9 would get a score of 72% (5.75 points out of 8).

There are 765 arrangements with discrepancy 10, and an example is {6, 2, 3, 4, 5, 1, 7, 8}. Compare the score of 69% for this arrangement with the simpler method of counting how many numbers are in the right place: 6/8 = 75%.

Does any of this make any sense? Is it of any use?

That depends, of course, on what the aim was of constructing a scoring method to assess student arrangements.

I think it would be a neat study to look at young children’s efforts to see what arrangements they actually made, and why, and how that matched with this method of scoring arrangements via the discrepancy.

BTW, it’s easy enough to automate this procedure for arrangements of numbers 1 through n, using a tool such as Mathematica, or the free computational language Sage (or Python).

Thanks to Fawn for a most interesting question!

Probability of an odd number of 6’s when tossing a bunch of dice

January 16, 2018 By Gary Ernest Davis

Alexander Bogomolny (@CutTheKnotMath) has a post on his website Cut The Knot dealing with the probability of an odd (or of an even) number of 6’s when tossing a bunch of fair dice:

The answer, at least to this bear with a small brain, was initially confusing: there is, at least for a small number of dice – say 7 or so – a somewhat greater chance of getting an even number of 6’s than an odd number.

My confusion lifted when I plotted the result and remembered that, for the purposes of this problem, 0 is a perfectly good even number.

Here is the solution given on Alexander’s post prior to my tweeting him a plot (now shown on his web page):

Here’s the plot for P (in blue) and Q (in red):

So throwing no die does give us an even number of 6’s, namely 0 6’s, with probability 1.

We might, in a somewhat devilish mood, ask: what is the probability of getting a number of 6’s that leaves a remainder of 0 (or 1 or 2) mod 3 when we toss n dice?

When k = 3p is a multiple of 3 the probability of k 6s when tossing n dice is

$P_0(n) =\sum_{k\equiv 0(\textrm{mod }3)}{n\choose k}(\frac{5}{6})^{n-k}(\frac{1}{6})^k$

= sum of every $3^{rd}$ term in the binomial expansion of $(a+b)^n$ where $a=\frac{5}{6}, b=\frac{1}{6}$

= $\sum_{p=0}^{\lfloor n/3\rfloor}{n\choose 3p}(\frac{5}{6})^{n-3p}(\frac{1}{6})^{3p}$

We can compute these probabilities in Mathematica as follows:

Prob[0,n_]:=Total[Table[Binomial[n,3*p]*(5/6)^(n-3*p)*(1/6)^(3*p),{p,0,Floor[n/3]}]]

with the result (for $0\leq n \leq 40$ :

Unlike the odd/even cases, these probabilities are not a monotone function of n, and decrease until n =12 in which case they then converge, as we expect, to 1/3 (but not monotonically).

The value of Prob(0,500), accurate to 60 decimal places, is

0.333333333333333333333333333333333333333333333333333333333347

Here are more details:

We can calculate the probability that the number of 6s is of the form 3p+1 or 3p+2 similarly, and here is a plot of those probabilities for n ranging from 0 though 30:

The probabilities converge, as we expect, on 1/3 as n increases.

Complex numbers satisfying Fermat’s identity

January 14, 2018 By Gary Ernest Davis

Alexander Bogomolny (@CutTheKnotMath) has a post on his website Cut The Knot dealing with proofs of the following fact:

The proofs rely, among other things, on the fact that prime numbers $p>3$ are of the form $6m\pm 1$ , which is clear since a prime greater than 3 cannot leave a remainder of 0, 2, 3 or 4 upon division by 6.

I want to consider a slight extension of this fact – basically replacing $z=2$ by an arbitrary non-zero complex number – by considering something relevant to the first solution offered at Cut the Knot.

In that solution the facts $x+y=z, \frac{1}{x}+\frac{1}{y}=\frac{1}{z}$ are utilized.

Suppose we choose $z\neq 0$ arbitrarily as a complex number.

Can we find complex numbers $x, y$ such that $x+y=z, \frac{1}{x}+\frac{1}{y}=\frac{1}{z}$ ?

Yes, we can, notably & uniquely:

$x = e^{-i\pi/3}z, y= e^{i\pi/3}z$

$x = e^{i\pi/3}z, y= e^{-i\pi/3}z$

So, we now have the following:

Let $z \neq 0$ be a complex number and let either

$x = e^{-i\pi/3}z, y= e^{i\pi/3}z$

$x = e^{i\pi/3}z, y= e^{-i\pi/3}z$ .

If $n=6m\pm1$ then $x^n+y^n = z^n$ .

For $n =6m+1$ this follows directly from the fact that

$( e^{i\pi/3})^{6m+1} + (e^{-i\pi/3})^{6m+1} =e^{i\pi/3} +e^{-i\pi/3} = 1$ .

A similar argument holds when $n=6m-1$ .

Since primes $p>3$ are of the form $6m\pm1$ we have the following:

Let $z \neq 0$ be a complex number and let either

$x = e^{-i\pi/3}z, y= e^{i\pi/3}z$

$x = e^{i\pi/3}z, y= e^{-i\pi/3}z$ .

If $p>3$ is prime then $x^p+y^n = z^p$ .

Another collection of positive integers that are necessarily of the form $n=6m\pm1$ are those $n$ for which $\phi(n)>2n/3$ , where $\phi(n)$ is Euler’s phi function: the number of $k<n$ that are coprime with $n$ . See the Online Encyclopedia of Integer Sequences, for example.

2017 and other prime years

January 8, 2018 By Gary Ernest Davis

Alexander Bogomolny (@CutTheKnotMath) has a nice post “A Farewell Problem for the Year 2017” on his website Cut The Knot.

The problem is to find the least positive integer $n$ for which $n(n+2017)$ is a perfect square.

The proof on the Cut The Knot webpage shows also shows that there is, in fact, only one such $n$ .

A key part of the proof is that 2017 is a prime number.

What would happen if 2017 were replaced by an arbitrary prime number $p$ ?

Could we still prove that there is exactly one positive integer $n$ for which $n(n+p)$ is a perfect square?

Well, no, because $n(n+2)$ can never be a perfect square: if $n(n+2)=k^2$ for some integer $k$ then $n=\sqrt{k^2+1}-1$ which is not an integer when $k$ is an integer.

We can see that the primes 3 and 5 are OK because $1\times(1+3)$ is a perfect square, as is $4\times(4+5)$ .

On the assumption that for all odd primes $p$ we can find a positive integer $n$ for which $n(n+p)$ is a perfect square, we can write a Mathematica code snippet to find the least such $n$ given the $k^{\textrm{th}}$ prime:

primefunc[k0_] := Module[{k = k0, n}, n = 1; While[IntegerQ[Sqrt[n*(n + Prime[k])]] == False, n++]; n]

This tells us what works for $p=3$ and $p=5$

primefunc[2]

primefunc[3]

So, assuming the Mathematica code halts for odd primes we can create a table of pairs

(primes p, least n such that n(n+p) is a perfect square):

T = Table[{Prime[n], primefunc[n]}, {n, 2, 100}]
ListPlot[T]

{{3,1},{5,4},{7,9},{11,25},{13,36},{17,64},{19,81},{23,121},{29,196},{31,225},{37,324},{41,400},{43,441},{47,529},{53,676},{59,841},{61,900},{67,1089},{71,1225},{73,1296},{79,1521},{83,1681},{89,1936},{97,2304},{101,2500},{103,2601},{107,2809},{109,2916},{113,3136},{127,3969},{131,4225},{137,4624},{139,4761},{149,5476},{151,5625},{157,6084},{163,6561},{167,6889},{173,7396},{179,7921},{181,8100},{191,9025},{193,9216},{197,9604},{199,9801},{211,11025},{223,12321},{227,12769},{229,12996},{233,13456},{239,14161},{241,14400},{251,15625},{257,16384},{263,17161},{269,17956},{271,18225},{277,19044},{281,19600},{283,19881},{293,21316},{307,23409},{311,24025},{313,24336},{317,24964},{331,27225},{337,28224},{347,29929},{349,30276},{353,30976},{359,32041},{367,33489},{373,34596},{379,35721},{383,36481},{389,37636},{397,39204},{401,40000},{409,41616},{419,43681},{421,44100},{431,46225},{433,46656},{439,47961},{443,48841},{449,50176},{457,51984},{461,52900},{463,53361},{467,54289},{479,57121},{487,59049},{491,60025},{499,62001},{503,63001},{509,64516},{521,67600},{523,68121},{541,72900}}

We can notice fairly readily, that the values for $n$ we got, for a given odd prime $p$ , are themselves all perfect squares, and, in fact, $n= (\frac{p-1}{2})^2$ .

Could this be correct for all odd primes $p$ ?

Sure!

The first thing to notice is that if $p \geq 3$ is odd then $n= (\frac{p-1}{2})^2$ is a positive integer and $n(n+p) = (\frac{p^2-1}{2})^2$ is a perfect square.

This bit doesn’t depend on $p$ being prime.

That this is the only positive integer $n$ for which $n(n+p)$ is a perfect square, does rely on $p\geq 3$ being prime and odd.

In fact, we can simply modify the argument at the post “A Farewell Problem for the Year 2017“:

if $n(n+p)$ is a perfect square and $n$ is not a perfect square, then $n$ has a factor that is shared with $n+p$ and, hence, with $p$ . But $p$ is prime so the only possibility is $n=s^2p$ , implying $n(n+p)=(ps)^2(s^2+1)$ which can not be a perfect square unless $s=0$ .

So both $n$ and $n+p$ are perfect squares, say $n=a^2, n+p=b^2$ . From this we have $(b-a)(b+a)=p$ , which is prime, so $b-a=1, b+a=p$ which means $a =\frac{p-1}{2}, b=\frac{p+1}{2}$ .

In other words, if $p \geq 3$ is an odd prime then $n= (\frac{p-1}{2})^2$ is the unique positive integer for which $n(n+p)$ is a perfect square.

The dots are still exploding! A message from James Tanton

January 7, 2018 By Gary Ernest Davis

James Tanton sent the email reproduced below to all Global Math Project Ambassadors, January 7, 2018.

I feel the message is so positive in terms of what Global Math Week 2018 might be that I asked James if I could reproduce it here. Of course, he agreed!

From James Tanton:

G’Day Global Math Ambassadors and Ambassadors-to-be:

Happiest of Happiest and Bestus Mathiest New Year Wishes to one and all!

Global Math Week 2017 was a tremendous success and has set the stage for for GMW2018 to be even more successful. Let’s go for 10 million students and teachers this October!

To this end it is now time to start getting back into gear and taking action.

* In October 2018 teachers will have new students and we’ve received the message that many folk would indeed like to do Exploding Dots again. That’s great! So let’s do that and let’s now have each person bring on 10 colleagues!

* Let’s get back into recruiting additional ambassadors.

* Let’s get back into catching the typos and slips in the written materials and web materials.

* Let’s start translating all the materials into even more languages!

* Let’s start revealing the new mathematics of the next topic for 2019 too! (That is, let’s get excited about both Exploding Dots and the next reveal!)

SAVE THE DATE: Oct 6

It looks like we might have some start funding to host another kick-off symposium for Global Math Week, like the successful one we had last October in at the Courant Institute in New York. This time, we’ll be out in the Bay Area (San Jose, California, and surrounds). Details need to be confirmed. Some top folk who work out there have this date on their books and are saving it for GMP. Might you be able to save the date too?

EXPLODING DOTS STORIES: THE BOOK

One of our ambassadors would like to collate stories of folk doing the mathematics of Exploding Dots from around the world. Details are just starting to come into focus now and I’ll write more about this in my next update – but feel free to start mulling. Have you any essays or articles that you have written that you would like the world to see? Is there something in the back of your mind you would like to write? This would be a math book – all the mathematics of Exploding Dots spelled out – with additional articles and essays and tidbits, collated as an edited volume.

CPN ARTICLE

Speaking of articles … Below is a very nice piece about Global Math Week just released by the Center for the Promotion of Science, Serbia.

I am still receiving requests from around the world to talk and give workshops on Exploding Dots. Folk are still signing up to www.explodingdots.org to play with scolab.com ‘s fabulous web app. Folk are still sending me emails and videos about new ways to do school algorithms that are beautifully explained with an Exploding Dots mindset. Folk are still exploring the mathematics of wild and crazy Exploding Dots machines. Those dots are still going mighty strong!

Here’s to a happy and healthy and uplifting and truly joyous 2018 for the world.

Cheers,

James – and the GMP team.

Some comments on fractions of integers less than and coprime to n

January 3, 2018 By Gary Ernest Davis

James Tanton (@jamestanton) asked the following question on Twitter (December 31, 2017):

“If all of the numbers 1, 2, …, n-1 are coprime to n (share only the factor 1 with n), then n must be prime. Is there an n with precisely half of the numbers 1,2,…,n-1 coprime to n? One with precisely a third of them coprime to n?”

There is a well-known name for the number of positive integers less than and coprime to n: this is Euler’s totient function, denoted $\phi(n)$ .

A pretty mindless computation indicates there’s not likely to be any positive integers k such that a fraction $1/k$ of the numbers $1,2,\ldots, n-1$ are coprime with $n$ .

The Mathematica code below was aborted at n = 1,038,898,229 without finding any such k:

n = 2;
While[IntegerQ[(n – 1)/EulerPhi[n]] == False, n++]
n

So why might this be so?

Euler’s product formula for the totient function is:

$\displaystyle\phi(n)=n\prod_{p|n, p \textrm{ prime}}(1-\frac{1}{p})$

so to say, for example, that

$\frac{\phi(n)}{n-1}=\frac{1}{3}$

is to say that

$\displaystyle3\prod_{p|n}(1-\frac{1}{p})=1-\frac{1}{n}$

While it’s commonly the case that

$\displaystyle3\prod_{p|n}(1-\frac{1}{p})>1-\frac{1}{n}$

it is not universally so. For example if $n$ is the product of the primes 2, 3, 71, 491, 1031, 1489, 1657, 1949, 2269, 2381, 3613, 4079, 5743, 5807, 6131, 6257, 6637, 6709, 7207, 7433 then

$\displaystyle3\prod_{p|n}(1-\frac{1}{p}) < 1-\frac{1}{n}$

So, at least from the perspective of Euler’s totient formula, the question even of whether there is an $n$ for which

$\frac{\phi(n)}{n-1}=\frac{1}{3}$

seems to be a little subtle.

When $n=p_1p_2\ldots p_k$ is a product of distinct primes $p_1,p_2,\ldots,p_k$ then

$\frac{\phi(n)}{n-1}=\frac{1}{3}$

is equivalent to

$3(p_1-1)(p_2-1)\ldots (p_k-1)= p_1p_2\ldots p_k - 1$

We can see how this isn’t possible for a product of 2 primes (i.e. $k=2$ ):

if $3(p_1-1)(p_2-1)= p_1p_2 - 1$ then

$2p_1p_2 -3(p_1+p_2) + 4 = 0$

We can write $p_2=p_1+d$ where $d\neq 0$ because $p_1\neq p_2$ .

Then,

$2 p_1^2 +(2d-6)p_1 +4-3d=0$

which means

$p_1 =(3 - d + \sqrt{1 + d^2})/2$

which is not possible since $1+d^2$ is not a square.

For a product of 3 distinct primes $p_1,p_2,p_3$ we can do something similar, writing $p_2=p_1+d_1, p_3=p_1+d_2$ and end up with a cubic polynomial in $p_1$ with coefficients involving $d_1, d_2$ . As we get a larger collection of primes we get polynomials, with integer coefficients, in $p_1$ of higher degree (for which the rational roots test doesn’t seem to help).

We can also see how $\frac{\phi(n)}{n-1}=\frac{1}{3}$ is not possible when $n = p^k$ is a prime power:

from $\frac{\phi(n)}{n-1}=\frac{1}{3}$ we get $2p^k-3p^{k-1}+1=0$ and the rational roots test tells us that the only integer solution is $p=1$ .

Maybe more is clear to a number theorist. At this point however, I am stumped.

Mathematical power to the people: Lessons from Global Math Week

November 6, 2017 By Gary Ernest Davis

Recently, Jim Tanton (@jamestanton) emailed the Global Math Project ambassadors:

“G’Day Dear Ambassadors and Ambassadors-to-be:
We’re still collating data from the grand week of GMW2017 and putting together a report for one and all to see. As soon as it is ready we’ll make sure one and all sees!

But just so you know, we are still receiving registrations each day (with an alleged student count of 2.8 million at present) and Scolab’s web app is receiving between 8,000 and 15,000 hits each day. I guess we have proved we have traction!
It has been pointed out to us by some key-people in US mathematics education that we seem to have done two important things:

1. We have proved that there is a critical mass of teachers who want open mathematics conversations about mathematics with their students. Even with solid curricula in hand, there is a demand for more.

2. Mathematics creation is often seen as only for those in a “specialized club” of sorts and that much of mathematics feels out of reach. GMP seems to have opened a door to show that everyone really is welcome, that mathematics is not an exclusive club”.

Seems to me there is something else going on here, too – something I find hard to pin down, yet keeps coming to mind through the examples of teacher and parent stories where they themselves tell how the scales dropped from their eyes, and how they were, for the first time ever, enlightened as to the simple nature of place value, and the previously mysterious, yet actually very simple, process of long division.

This has the flavor, to me of Piper Harron’s call of $\textrm{power}^{\textrm{people}}$ :

I believe the Global Math Week helped, and continues to help, teachers, parents and students, claim mathematical power for themselves: their minds are able to make sense of different number bases, of addition, subtraction, multiplication, division, long division, and algebra. Everyone involved seems to have experienced a freedom from reliance on mathematical experts, and authoritative (and often incomprehensible) textbooks. Why, this stuff is so simple, and such fun , you can figure it out yourself. And it makes sense!

I would dearly love to see Piper Harron, and like-minded mathematicians, link up with Jim Tanton and the Global Math Project crew to help continue this deep journey into providing all people, of all ages, with mathematical power, the way we saw happen in the week of October 10, 2017.

The dam has burst, the flood gates are open – a wave of joyous, comprehensible mathematics is sweeping the world.

Matching sequences of 0’s and 1’s and differences of Lucas numbers

November 6, 2017 By Gary Ernest Davis

Jim Tanton (@jamestanton) asks:

“A row of 0s & 1s repeats in blocks of 4, another below it repeats in blocks of 5. Count how many 0s line up over 20 terms. What notice?”

Curious question: what could we be looking for, or hoping to notice?

We could, of course, try all $2^4=16$ rows of 0’s and 1’s of length 4, together with all $2^5=32$ rows of 0’s and 1’s of length 5 – giving us $16\times 32 = 512$ possibilities – and check in each case the times the 0’s line up. And maybe we should do just that.

For now let’s just generate a random example and see what we might notice.

Here’s some Mathematica code to construct a random example:

A = Table[RandomInteger[{0, 1}], 4]
AA = Flatten[Table[A, 5]]
B = Table[RandomInteger[{0, 1}], 5]
BB = Flatten[Table[B, 4]]
Apositions = Flatten[Position[AA, 0]]
Bpositions = Flatten[Position[BB, 0]]
common=Intersection[Apositions, Bpositions];

Print[“There are “,Length[common], ” positions where the 0’s line up”]

and running this once gave the following:

{0, 0, 0, 1}

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

{1, 0, 0, 0, 0}

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

{1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 18, 19}

{2, 3, 4, 5, 7, 8, 9, 10, 12, 13, 14, 15, 17, 18, 19, 20}

There are 12 positions where the 0’s line up

Nothing pops out, at least not to me.

Doing this a few more times doesn’t indicate any pattern of the number of times 0’s line up.

So let’s do this a bunch of times, say 1,000,000 times.

What numbers of line ups do we get?

Here’s some Mathematica code to do that:

n = 1;
L = {};
While[n <= 1000000,
A = Table[RandomInteger[{0, 1}], 4];
AA = Flatten[Table[A, 5]];
B = Table[RandomInteger[{0, 1}], 5];
BB = Flatten[Table[B, 4]];
AAA = Flatten[Position[AA, 0]];
BBB = Flatten[Position[BB, 0]];
L = {L, Length[Intersection[AAA, BBB]]}; n++]
L = Union[Flatten[L]]

and here’s the result:

{0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 20}

The numbers that are missing from this list are 7, 11, 13, 14, 17, 18, 19

Curiously, this number sequence – 7, 11, 13, 14, 17, 18, 19 – occurs in the Online Encyclopedia of Integer Sequences as part of a larger sequence: namely the ordered sequence of nonnegative differences f-4g, where f and g are Lucas numbers.

Is the sequence 7, 11, 13, 14, 17, 18, 19 exactly the list of forbidden number of times the 0’s line up: we can check this by examining all possible sequences of 0’1 and 1’s of length 4 and 5.

Why is there a connection with Lucas numbers? Is this a coincidence, or is there a story here?

Patterns in the sesquinary representations of integers

November 4, 2017 By Gary Ernest Davis

We can represent all positive integers in a 2<- 3 exploding dots machine using the digits 0, 1, and 2.

We call such a representation the sesquinary representation (from “sesqui” = “one and a half”).

The integers between 15 and 23 have 5 digits in their sesquinary representation:

Reading the digits from the left we see:

The 1st digit (from the left) is always 2 – just 1 possible pattern.
The first two digits are always 2, 1- just 1 possible pattern.
The first three digits are either 2, 1, 0 or 2, 1, 2 – 2 possible patterns.
The first four digits are either 2, 1, 0, 1 or 2, 1, 2, 0 or 2, 1, 2, 2 – 3 possible patterns.

Jim Propp

Jim Propp examined (Endnote #7) the number of different patterns for the first 1, 2, 3, 4, 5, 6 ,…, 20 digits, for numbers large enough to have more than 20 digits.

What he found was a number sequence: 1, 1, 2, 3, 4, 6, 9, 14, 21, 31, 47, 70, 105, 158, 237, 355, 533, 799, 1199, 1798, … that the Online Encyclopedia of Integer Sequences indicated occurred in an apparently entirely different context, namely the $n^{th}$ term in this sequence is the least integer greater than, or equal to, (1+ sum of preceding terms)/2.

To proceed a little more systematically, we can compute those integers that require d digits:

and in each of those ranges we can examine the number of distinct patterns of the left-most digits.

What we see is that the pattern count for the first d digits of a sesquinary (d+1)-digit number is stable, but the pattern count for the whole d+1 digits is not:

What we compute, therefore, are the numbers P(d) of distinct patterns for the first d digits of an integer with d+1 sesquinary digits. That is what yields the sequence 1, 1, 2, 3, 4, 6, 9, 14, 21, 31, 47, 70, 105, 158, 237, 355, 533, 799, 1199, 1798, … which Jim Propp located, in a different context, in the Online Encyclopedia of Integer Sequences.

This sequence $a(n)$ can be calculated recursively as follows:

$a(1)=1$

$b(1)=1$

$a(n)=\textrm{Ceiling}((1 + b(n - 1))/2)$

$b(n)=b(n - 1) +a(n)$

This recursive definition of the sequence $a(n)$ allows for rapid calculation, unlike the very slow calculation that was required to produce the (apparently same) sequence 1, 1, 2, 3, 4, 6, 9, 14, 21, 31, 47, 70, 105, 158, 237, 355, 533, 799, 1199, 1798, … from the patterns of the first d digits of the representation of integers with d+1 sesquinary digits.

Glenn Whitney

Now, somewhat mysteriously, on the Online Encyclopedia of Integer Sequences page that describes the sequence $a(n)$ there is a remark by Glenn Whitney – founder of the Museum of Math – that these numbers – the $a(n)$ – are essentially the number of even integers with d+1 sesquinary digits.

Let’s see how these three equalities: $P(d+1) = a(n) =$ number of even integers with d+1 sesquinary digits – work in a few examples:

So it seems these 3 quantities are equal: the number of distinct patterns for the first d digits in integers with d+1 sesquinary digits, the recursively defined number a(d), and the number of even integers with d+1 sesquinary digits.

But why?

« Previous Page