## Crafting grafting

Here’s a cool integer: 60,755,907. What’s cool about it? Take the square root. You’ll need more significant figures than usual; the calculator that came with my Android phone will do it:

$\displaystyle \sqrt{60755907} = 7794.6075590756973...$

Check out what’s to the right of the decimal point. Crazy, right? Here’s another similar number:

$\displaystyle \sqrt{63826090875} = 252638.2609087546739...$

Here the digits of the integer on the left appear in the real number on the right starting in the 100s place. Matt Parker calls these things “grafting numbers“. What’s going on with them? This isn’t just weird coincidence, is it?

It isn’t.

Consider good old $\phi = (1+\sqrt{5})/2$. It’s a solution of the equation $x^2=x+1$. So $\phi = 1.6180339...$ and $\phi^2 = 2.6180339...$. There a number and its square (or, looked at the other way, a number and its square root) have digits in common; an infinite number of them, in fact. There’s a hint here.

Now let’s look at solutions to $(j+x)^2 = 10x$. Suppose $0 < x < 1$. Now if $j$ is an integer, then $j+x$ in decimal form is just the concatenation of $j$ and $x$ and $10x$ is just the digits of $x$ shifted one to the left.

For instance, $j = 2$; then $(2+x)^2 = 10x$. One solution is $3-\sqrt{5} = 0.7639320...$, and $2.7639320...^2 = 7.639320...$. Or looked at another way, $\sqrt{7.639320...}=2.7639320...$.

This starts to look like the grafting numbers idea, but grafting numbers are integers. But hang on. Multiply both sides by, say, 100: $\sqrt{76393.20...} = 276.39320...$. Round the number on the left up and you find

$\displaystyle \sqrt{76394} = 276.394645...$

There you go, a grafting number. How about more? We’ll see…

## 2^n-gons

There’s nothing at all new about this, in fact it’s ancient, but maybe it’s new to you? So here goes.

Here’s a square inscribed in a unit circle:

Or to keep down the clutter, here’s just one quadrant of that:

One side of the square along with the radii at each endpoint forms a triangle. The length of one side of the square we’ll call $s_4$ and it is of course $\sqrt 2$. That means the perimeter of the square is $p_4 = 4\sqrt 2\approx 5.656854249$.

Now consider an inscribed octagon. Again, here’s just one quadrant.

One side of the square is labeled $s_8$; what’s its length? Well, drop a perpendicular from the vertex in the middle:

And now notice the right triangle with hypotenuse 1 and sides $x_8$ and $h_8$ is just half of a quadrant of an inscribed square, which means $h_8=s_4/2$. Then $x_8^2 = 1-h_8^2 = 1-s_4^2/4$. From that you can get $y_8=1-x_8$ and from that, $s_8^2=h_8^2+y_8^2$. The perimeter of the octagon is then $p_8 = 8s_8\approx 6.122934918$.

Well, that was so much fun, let’s do it again. Here’s a quadrant of a 16-gon:

The right triangle with hypotenuse 1 and sides $x_{16}$ and $h_{16}$ is just half of an eighth of an inscribed octagon, which means $h_{16}=s_8/2$. Then $x_{16}^2 = 1-h_{16}^2 = 1-s_8^2/4$, $y_{16}=1-x_{16}$, and $s_{16}^2=h_{16}^2+y_{16}^2$. The perimeter of the 16-gon is then $p_{16} = 16s_{16}\approx 6.242890305$.

You know the rest, right? From here you can do the 32-gon, 64-gon, 128-gon, and so on, getting $x_{2n}^2 = 1-h_{2n}^2 = 1-s_n^2/4$, $y_{2n}=1-x_{2n}$, $s_{2n}^2=h_{2n}^2+y_{2n}^2$, and perimeter $= p_{2n} = 2ns_{2n}$. For $n = 1024$, the perimeter is $p_{1024}\approx 6.283175451 = 2\times 3.1415877255$. As $n$ increases, the perimeter gets closer and closer to the circumference of the circle, so this gives a way to calculate $\pi$.

What about circumscribed polygons? If you look at the figures above, you can see the ratio of the size of a circumscribed square to an inscribed square is $1/x_8$. Likewise the ratio of the size of a circumscribed octagon to an inscribed octagon is $1/x_{16}$, and so on. So the perimeter of a circumscribed $n$-gon is $P_n = p_n/x_{2n}$. As $n$ increases, $P_n$ approaches $2\pi$ from above. And the average of $p_n$ and $P_n$ is a better approximation to $2\pi$ than either, though not by a lot.

 n h_n x_n y_n s_n p_n P_n average 4 1.41421356 5.65685425 8.00000000 6.82842712 8 0.70710678 0.70710678 0.29289322 0.76536686 6.12293492 6.62741700 6.37517596 16 0.38268343 0.92387953 0.07612047 0.39018064 6.24289030 6.36519576 6.30404303 32 0.19509032 0.98078528 0.01921472 0.19603428 6.27309698 6.30344981 6.28827340 64 0.09801714 0.99518473 0.00481527 0.09813535 6.28066231 6.28823677 6.28444954 128 0.04906767 0.99879546 0.00120454 0.04908246 6.28255450 6.28444726 6.28350088 256 0.02454123 0.99969882 0.00030118 0.02454308 6.28302760 6.28350074 6.28326417 512 0.01227154 0.99992470 0.00007530 0.01227177 6.28314588 6.28326416 6.28320502 1024 0.00613588 0.99998118 0.00001882 0.00613591 6.28317545 6.28320502 6.28319024

This is something like the way Archimedes calculated $\pi$ around 250 BC (I told you this was ancient), although he started with a hexagon rather than a square and only went up to a 96-gon. He didn’t have Google Sheets, though.

## Ancient ritual recovered, part 2

How does that method work? Say you have a number $x$ which can be written as $\sum_{i=0}^n 100^ix_i$, where the $x_i$ are positive integers less than 100, that is, they are pairs of digits in $x$. Start with $x_n$ and find the largest digit $a_n$ whose square is no greater than $x_n$, that is, $x_n=a_n^2+r_n$.

Now consider $100x_n+x_{n-1}$, that is, the number formed from the first two pairs of digits in $x$. Its square root is a little more than (or equal to) $10a_n+a_{n-1}$ where $a_{n-1}$ is the largest digit which, appended to $a_n$, gives you a number whose square is no greater than $100x_n+x_{n-1}$. That is, $100x_n+x_{n-1} = (10a_n+a_{n-1})^2+r_{n-1}$. But $(10a_n+a_{n-1})^2 = 100a_n^2+(20a_n+a_{n-1})a_{n-1}$ and so $100r_n+x_{n-1} = (20a_n+a_{n-1})a_{n-1}+r_{n-1}$. The number on the left is just the remainder from the previous step with the next pair of digits from $x$ appended, and the first term on the right is twice the result from the previous step with a new digit appended, multiplied by that new digit. Their difference gives our new remainder, $r_{n-1}$.

Iterate that process and you get each digit $a_n$ of the square root.

## Ancient ritual recovered

Back when I was a kid, probably in middle school I’m guessing, I was taught how to calculate square roots. And then I forgot. At some point I switched over to the algorithm where you enter the number into a calculator and press the square root button. Once in a while I’d recall I used to know how to do it on paper, but the method was gone.

Recently I saw a YouTube video explaining the method, so I got it back. And I’m writing it up here because I have an easier time keeping track of this blog than all the YouTube videos I’ve seen. In fact I’ve lost track of the video already.*

So let’s find the square root of 7252249.

This is going to look kind of like long division. Kind of. Start by putting the number under a square root sign, and separate it into pairs of digits, right to left. (If the number is not an integer, start from the decimal point.)

Now look at the leftmost pair of digits. (In this case the number of digits is odd, so the leftmost “pair” is just the 7.) Above it, write the largest single digit whose square is no greater than that pair. Here it’s 2, because 2² < 7 but 3² > 7. Write the square of that digit (4) under the pair, and subtract (3=7-4).

Next bring down the next pair, 25, to make the number 325. Take the result so far (2), multiply by 2 (4=2×2), and write that to the left, leaving room for another digit.

Now we want the largest single digit such that if we append it to the number we just wrote down on the left, and multiply the result by that digit, it’s no greater than the number on  the right. Here 7 is just barely too large, because 7×47 = 329 which is >325. But 6×46 = 276, which is <325, so put 6 on top and after the 4, put 276 under the 325, and subtract (49=325-276).

Lather, rinse, repeat. Bring down the next pair (22) and to the left write the result so far times 2, with room for another digit (52=2×26).

The largest digit that will work next is 9, because 9×529=4761 which is <4922. Write that down and subtract (161=4922-4761).

Again, bring down the next pair (49), double the result so far and write that on the left (538=2×269).

Looks like 3 should work for the next digit and in fact, 3×5383 = 16149 which is exactly what we have, so 7252249 is actually a perfect square, 2693².

If it were not a perfect square we could continue by bringing down pairs of zeros after the decimal point and carrying on as before to get as good an approximation as we need.

It’s not as easy as punching a calculator, but that’s not the point. Being able to do this on paper means you’re that much less dependent on machines. It’s amazing the feeling of power it gives you.

* I lied. It’s here: https://www.youtube.com/watch?v=nAZvUnWbS8c

## Stern scales

I mentioned in Three gaps, part 1 an article I have about xenharmonic musical scales, and in that article I mention a link between two-gap scales (MOS scales, as they’re somewhat reluctantly called there) and something called Stern’s diatomic series. As discussed previously, if you generate scales using a generator equal to $1200\log_2 (3/2)\approx 702$ cents, then you get two-gap scales with 2, 3, 5, 7, 12, 17… notes. Each of these numbers (starting with 5) is the sum of the immediately preceding number and one of the other preceding numbers:

5 = 3 + 2
7 = 5 + 2
12 = 7 + 5
17 = 12 + 5

and so on. Specifically each number is the sum of the immediately preceding one and one of the two numbers summed to make the immediately preceding one.

If you vary the generator by a small amount (and it’s still irrational) you get the same sequence to a point, and then it differs: for a musically significant example, a quarter comma tempered fifth, $1200\log_2 [(3/2)/(81/80)^{1/4}]\approx 697$ cents, the sequence is 2, 3, 5, 7, 12, 19… . Notice that the two numbers summed to make 12 are 7 and 5, and the two numbers summed to make 17 are 12, the immediately preceding one, and 5 which is one of the numbers in the sum for 12, while the two numbers summed to make 19 are 12 and 7, the other number in the sum for 12. Of course the sequence terminates if the generator is rational: for a generator of 700 cents, for example, it goes 2, 3, 5, 7; then the 8- through 11-note scales are all two-gap, and the 12-note scale is one-gap, i.e., an equal division of the octave. It stops there because further applications of the generator just give back notes you already have.

A generator for a 17-note equal division is $1200\times10/17 = 705\ 15/17$ cents and a generator for a 19-note equal division is $1200\times11/19 = 694\ 14/19$ cents. Generators between these two values (other than 700 cents) will give 2, 3, 5, 7, and 12 note two-gap scales, with ones below 700 going on to 19 and ones above 700 going on to 17. Generators a little outside that range will not give 12-note scales; they’ll go 2, 3, 5, 7, 9… if below the range or 2, 3, 5, 8, 13… if above. A diagram from which one can read off the 2-gap scales for generators from 685 to 720 cents is here, and for all generators from 600 to 1200 cents is here (the diagram for 0 to 600 cents is just a mirror image).

Stare at the first of those diagrams and you see 47 appears in two places. That is, the 47-note equal division can be generated by two different generators in that range: $1200\times27/47\approx 689$ cents and $1200\times28/47\approx 715$ cents.

In fact, looking at the whole range from 0 to 1200 cents, there must be 46 generators for a 47-note equal division: $1200\times n/47$ for $n = 1..46$. That’s because 47 is prime. For a 46-note equal division, though, $1200\times n/46$ will generate the scale only for odd $n$; even values will generate only a 23-note scale. And in general, the generators for an m-note equal division are $1200\times n/m$ for values of $n$ where $1\le n < m$ and n and m are relatively prime. The familiar 12-note equal division has only four generators: $1200\times 1/12$$1200\times 5/12$$1200\times 7/12$, and $1200\times 11/12$ cents.

Examine that diagram some more and you can see how it relates to a sequence of numbers developed as follows: Start with

5, 7

and interpolate the sum of the adjacent numbers

5, 12, 7

(in the diagram, 12 is linked to the horizontal lines associated with 5 and 7); and again

5, 17, 12, 19, 7

(17 is linked to 5 and 12, 19 to 12 and 7); and again

5, 22, 17, 29, 12, 31, 19, 26, 7

(22 is linked to 5 and 17, and so on); and again

5, 27, 22, 39, 17, 46, 29, 41, 12, 43, 31, 50, 19, 45, 26, 33, 7

ad infinitum. Those two values of 47 arise in later iterations of the this sequence from 27+5+5+5 and 33+7+7.

Likewise the big diagram and its mirror image relate to:

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

et cetera. We can concatenate the rows of this, dropping the 1s from one end, into a single sequence:

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

which we can define with the recurrence relation:

$b(1) = 1$
$b(2n) = b(n)$
$b(2n+1) = b(n) + b(n+1)$

This is known as Stern’s diatomic series, A002487 in OEIS.

From that definition it’s not at all obvious that, for instance, 47 will arise as a sum 46 times while 12 will arise as a sum only 4 times. It’s true though. In fact, consider the following sequence of rational numbers:

1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4/1…

That’s just each entry in Stern’s series divided by the subsequent entry. But there’s a theorem: The nth rational number, in reduced form, can be taken to be b(n)/b(n + 1), for n = 0, 1, 2 … That is, b(n) and b(n + 1) are relatively prime, and each positive reduced rational number occurs once and only once in the list b(0)/b(1), b(1)/b(2), … Or to put it another way, Stern’s series provides a way to enumerate the rational numbers.

The theorem’s proved in Calkin, N., & Wilf, H. (2000). Recounting the Rationals. The American Mathematical Monthly, 107(4), 360-363. doi:10.2307/2589182, if you want to look at it. Another fact about the series, also discussed there, is b(n) is the number of ways of writing the integer n as a sum of powers of 2, each power being used at most twice (i.e., once more than the legal limit for binary expansions).

Every positive integer appears in the list surrounded by two smaller numbers, which are relatively prime and sum to n, exactly once for each such possible distinct sum (counting m, n, n-m and n-m, n, m as distinct). So one finds 1, 12, 11; 5, 12, 7; 7, 12, 5; and 11, 12, 1; and no other instances of 12 adjacent to smaller numbers. On the other hand, one finds all 46 of 1, 47, 46; 2, 47, 45; 3, 47, 44; … 45, 47, 2; and 46, 47, 1.

Mind you, you have to look through a lot of numbers to find them. After all, 1 appears adjacent to $n$ and $n-1$ at position $2^{n-1}$ in the series: 1 followed by 2 and 1 is at position 2, 1 then 3 and 2 at position 4, 1 then 4 and 3 at position 8, and so on. 1 followed by 47 and 46 appears at position $2^{46} = 70,368,744,177,664$(!) So if you want to figure out how many numbers are smaller than and relatively prime to 47, examining Stern’s series may not be the best approach.

## Riddlers for 4 May 2018

Spoilers for last week’s fivethirtyeight.com Riddler Express and Classic:

# Express

From Charlie Drinnan, find the letters’ numbers:

If A, B, C, D and E are all unique digits, what values would work with the following equation?

ABC,CDE × 4 = EDC,CBA

No problem. $A$ must be even, and $4A < 10$, so $A=2$. Then $4AB < 100$ so $B < 5$, and $BA\mod 4 = 0$ so $B = 1$ and $E = 8$, or $B = 3$ and $E = 9$. But $4E \mod 10 = A = 2$ so $E = 8$.

Now $4D+3 \mod 10 = B = 1$ so $4D \mod 10 = 8$. $D\ne 2$ so $D = 7$.

Finally $4C+3 \mod 10 = C$ or $3C\mod 10 = 7$, so $C = 9$.

$219,978 \times 4= 879,912$.

# Classic

This is fairly mechanical although I tripped up several times on the way.

Let $n_i$ be the number of coconuts found by the $i$th pirate, and $n_8$ be the number of coconuts found in the morning. $n_8$ is divisible by 7 so write $n_8 = 7m_8$.

But $n_8$ is what was left when the seventh pirate discarded one coconut out of $n_7$ and hid one seventh of the rest, so $n_7 = (7/6)n_8+1 = (7/6)(7m_8)+1$. For that to be an integer $m_8$ must be a multiple of 6, so write $m_8 = 6m_7$. Then $n_7 = 7^2m_7+1$.

Now $n_6 = (7/6)n_7+1 = (7/6)(7^2m_7+1)+1$. For integer value, $7^2m_7\mod 6 = m_7\mod 6 = 5$, so write $m_7 = 6m_6+5$. Then $n_6 = (7/6)(7^2(6m_6+5)+1)+1 = 7^3m_6+288$.

You see how this goes.

$n_5 = (7/6)n_6+1 = (7/6)(7^3m_6+288)+1$. For integer value, $m_6\mod 6 = 0$, so write $m_6 = 6m_5$. Then $n_5 = (7/6)(7^3(6m_5)+288))+1 = 7^4m_5+337$.

$n_4 = (7/6)n_5+1 = (7/6)(7^4m_5+337)+1$. For integer value, $m_5\mod 6 = 5$, so write $m_5 = 6m_4+5$. Then $n_4 = (7/6)(7^4(6m_4+5)+337)+1 = 7^5m_4+14400$.

$n_3 = (7/6)n_4+1 = (7/6)(7^5m_4+14400)+1$. For integer value, $m_4\mod 6 = 0$, so write $m_4 = 6m_3$. Then $n_3 = (7/6)(7^5(6m_3)+14400)+1 = 7^6m_3+16801$.

$n_2 = (7/6)n_3+1 = (7/6)(7^6m_3+16801)+1$. For integer value, $m_6\mod 6 = 5$, so write $m_3 = 6m_2+5$. Then $n_2 = (7/6)(7^6(6m_2+5)+16801)+1 = 7^7m_2+705888$.

$n_1 = (7/6)n_2+1 = (7/6)(7^7m_2+705888)+1$. For integer value, $m_2\mod 6 = 0$, so write $m_2 = 6m_1$. Then $n_1 = (7/6)(7^7(6m_1)+705888)+1 = 7^8m_1+823537$. The smallest value corresponds to $m_1 = 0$ so $n_1^{min} = 823537$.

These pirates were either very sleepy, or incredibly quick at counting coconuts.

## Riddler Classic for 23 March 2018 (part 2)

We’ve seen a generalization of the problem to multiplicative factors other than 2 and bases other than 10. A third generalization would be to shift more than one digit.

Take a positive integer $j$ in base $b$ and move its last $m$ digits to the front. What is the smallest $j$ such that when you do this, the result $k$ is exactly $p$ times $j$ (where $p$ is in the range $[2,b-1 ]$)?

Let $j= b^m \times y+x$, where $b^{m-1}\le x< b^m$ . So the digits of $x$ are the final $m$ digits of $j$ and the initial $m$ digits of $k$, and the digits of $y$ are the remaining digits of both. Let $n$ be the number of digits in $y$. Then we require

$p(b^my+x)= b^nx+y$.

Solving, $(pb^m-1)y=(b^n-p)x$ or

$y= \frac{b^n -p}{pb^m-1}x .$

Now let $g=\gcd(pb^m-1,x)$ and let $w=x/g$, $v=(pb^m-1)/g$. Then

$y= \frac{b^n-p}{v}w$

and since $v$ and $w$ are relatively prime, we must have

$b^n=p\mod v$.

So we must calculate $pb^m-1$ and then, for each possible value of $x$, obtain $v$ and look for the least $n$ that satisfies the above relation. (The minimal value of $x$ is in fact not $b^{m-1}$ but $pb^{m-1}$, since there can be no carry to an additional digit when $j$ is multiplied by $p$.) Then we can compute $y$, and verify that it does indeed have $n$ digits. The smallest such $y$ and associated $x$ solve the problem.

If $(pb^m-1)$ is prime, then $v = (pb^m-1)$ for all possible $x$ and the smallest $k$ results when $x=pb^{m-1}$. But if $(pb^m-1)$ has a common factor with some $x$, then $v$ is some factor of $(pb^m-1)$. Generally $n$, the number of digits in $y$, is on the order of $v$, so when $(pb^m-1)$ is prime the solution tends to be many orders of magnitude larger than when it is not.

For instance, consider $p=3$ and $b=10$. For $m=2$, $(pb^m-1)=299=13\times 23$. In that case some values of $x$ have a common factor with $(pb^m-1)$. E.g., $x=46$ gives

$y= \frac{10^n-3}{13}w$

where

$10^n=3\mod 13$.

The solution is $n=4$, leading to

$j=153846$, $k=3j=461538$.

But for $m=1$, $(pb^m-1)=29$ is prime. The number of digits in $y$ then turns out to be 27, and

$j=1034482758620689655172413793$.

And for $m=3$, $(pb^m-1)=2999$ is prime too. We end up with the 1499 digit solution

$j = 100033344448149383127709236412137379126375458486162054018006\\ 0020006668889629876625541847282427475825275091697232410803601200\\ 4001333777925975325108369456485495165055018339446482160720240080\\ 0266755585195065021673891297099033011003667889296432144048016005\\ 3351117039013004334778259419806602200733577859286428809603201067\\ 0223407802600866955651883961320440146715571857285761920640213404\\ 4681560520173391130376792264088029343114371457152384128042680893\\ 6312104034678226075358452817605868622874291430476825608536178726\\ 2420806935645215071690563521173724574858286095365121707235745248\\ 4161387129043014338112704234744914971657219073024341447149049683\\ 2277425808602867622540846948982994331443814604868289429809936645\\ 5485161720573524508169389796598866288762920973657885961987329109\\ 7032344114704901633877959319773257752584194731577192397465821940\\ 6468822940980326775591863954651550516838946315438479493164388129\\ 3764588196065355118372790930310103367789263087695898632877625875\\ 2917639213071023674558186062020673557852617539179726575525175058\\ 3527842614204734911637212404134711570523507835945315105035011670\\ 5568522840946982327442480826942314104701567189063021007002334111\\ 3704568189396465488496165388462820940313437812604201400466822274\\ 0913637879293097699233077692564188062687562520840280093364454818\\ 2727575858619539846615538512837612537512504168056018672890963654\\ 5515171723907969323107702567522507502500833611203734578192730910\\ 3034344781593864621540513504501500500166722240746915638546182060\\ 6868956318772924308102700900300$.

If you’d asked me to guess, before I worked any of this out, the order of magnitude of the smallest positive integer which is exactly tripled when you move the last three digits to the front, I’m pretty sure I would have seriously underestimated it.