# When Matt Discovered “Grafting Numbers”

The square root of 8053139 has “8053139″ as its first decimal places. It is a so-called Grafting Number.

Mathematicians can be a bit derogatory towards other sciences which are less rigorous, comparing things like biology to stamp-collecting. Actually, every science more theoretical than biology calls it stamp-collecting. The gist of the insult being that all biologists do is document and label things with no underlying logic.

While this is not true of all biology, it’s also not true that maths is free of stamp-collecting aspects. I’m prepared to admit that I’m a bit of stamp-collector of the mathematical world. I love the fact that 3435 = 3^3 + 4^4 + 3^3 + 5^5 and it’s the only such number. Sure it’s only true for Base 10 numbers and it offers no real insight into other numbers, but it’s still fun.

In a similar vein, I noticed something about the number 98 a few months ago, in relation to its square-root.

√98 = 9.899494937…

The first two digits of the square root are “98”. I started wondering if there were any other numbers where the leading digits of the square-root are the same as the digits of the number. It turns out there is a whole family of similar numbers, with a bit of a nice pattern:

√98 = 9.899494937…
√99 = 9.949874371…
√9998 = 99.9899995…
√9999 = 99.99499987…
√999998 = 999.998…
√999999 = 999.9995…

These are all numbers where their root grows out from the number itself, so I took to calling them “Grafting Numbers”. And those are the only numbers where the number appears as the lead digits. But then I noticed something similar about 77 and its own little family of numbers:

√77 = 8.774964387…
√9797 = 98.97979592…
√997997 = 998.997997…
√99979997 = 9998.99979997…

These are all number where the number appears in the square-root starting from the decimal point, which I also declared to be Grafting Numbers.

Now I was curious to see if there were other numbers that appeared somewhere near the start of their own square-root. I decided that “somewhere near the start” was anywhere up to and including the decimal point[1]. However, these would be harder to find than just square-rooting two digit numbers on a calculator.

Which, frankly, is a good thing.

At university I learned some programming, and I’ve since worked teaching programming to school kids; but it’s been a while since I was fluent in a programming language and I never learned anything useful for mathematics (it was always robotics focused). So one of my resolutions for 2011 was to start learning to programming language “Python”.

Python is a lovely, fun little language and it comes already preinstalled on Macs, ready to run from the Terminal prompt. So away I went, setting myself mathematical challenges and then writing little programmes to solve them. This was a perfect such challenge: I wrote some code to find all the Grafting Numbers less than 10,000,000 (ignoring perfect squares). I’ve put the code below[2] if you’re interested, but here are the results:

√764 = 27.64054992…
√765 = 27.65863337…
√5711 = 75.57115852…
√5736 = 75.73638492…
√76394 = 276.3946454…
√2798254 = 1672.798254…
√7639321 = 2763.932163…
√8053139 = 2837.8053139…

Now, while this was all good fun, and I was learning some new programming skills, you will notice that all I’m doing is numerical stamp-collecting. I’m hunting down new numbers and giving them labels. Are far as I can find online – and I’m very keen to be corrected if anyone knows better – this type of number has not be named before, but that doesn’t make it interesting in a bigger mathematical context.

What the mathematician in me really wanted now, was some kind of underlying pattern to investigate. Which was why I took a closer look at these Grafting Numbers:

√764 = 27.64054992…
√76394 = 276.3946454…
√7639321 = 2763.932163…

They looked like a new family of numbers where each one appeared in its square-root, proceeded by a “2”. A quick new bit of code found that there are plenty more in the same family:

764
76394
7639321
763932023
76393202251
7639320225003
763932022500210
76393202250020992
7639320225002102784

A little bit of algebraic messing-around[3] revealed that these numbers are following the decimal places of the irrational number: 3-√5 = 0.763932022500…

Strictly speaking, each of these numbers is a value of ⌈(3-√5)10^(2n+1)⌉

So I decided to call 3-√5 a “grafting constant”. People have pointed out to me that because of the √5 this can be linked to the Golden Ratio: 3-√5 = 2(2-ϕ)

I don’t know if there are other such constants, and I’ve not really had a look at other roots or number bases. An obvious next step might be to look at cube roots in base 10. Feel free to adapt my python code below or write something better!

Programming is such great fun (combined with the greatest levels of frustration) and is such a unique way of using logic. Everyone should learn to program at least once in their lives. There are countless Python resources online, and if you’re looking for some programming challenges to get you started, I recommend Project Euler.

The vast majority of mathematics started because someone noticed something interesting, gave it a name and started playing around to see how it worked. So maybe we should be a bit nicer to biologists after all. A bit.

Matt Parker first talked about Grafting Numbers at the Maths Jam annual weekend, 13 November 2011. He talks about both Grafting Numbers and Maths Jam in this Numberphile video:

[1] If you let go of the decimal point, it’s a long way down. If you have a never-ending sequence of random digits, then you would expect to find any string of digits sooner or later, making all such roots Grafting Numbers. However, this also requires that the number is a Normal Number, meaning that all possible combinations of digits are equally likely. So far, mathematicians haven’t managed to prove that any number is a Normal Number. So I’m not going near it.

[2] Sorry, this code has lost all its formatting. You’ll need to put some indents/tabs in to get it to run as python code. Like this.

``` # Just looking for ones right at the beginning and alerting to ones that are right at the beginning or lead off form the decimal point. # Set "mag" to what magnitude number you want to check up to. mag = 7 will give up to 10 million.```

``` r = 2 n = 0 mag = 7 end = 10 ** mag flags = 10 ** (mag-2) interest = 0 run1 = 1 ```

```while run1 == 1: run2 = 1 n = n+1 if n % flags == 0: print 'Checked {0}'.format(n) root = n ** (1./r) #the r'th root if n == (int(root)) ** r: #this bit moves it along if n is a perfect square, cube etc n = n + 1 root = n ** (1./r) length = len(str(n)) #length of number being tested lead = len(str(int(root))) #number of leading digits test = root * (10 ** (length -lead)) pos = -lead while run2 == 1: t = int(test) if n == t: print 'Found {0} at position {1}'.format(n, pos) run2 = 0 test = 10*test-(10 ** length)*int(test*(1./(10 ** (length-1)))) pos = pos+1 if pos > interest: run2 = 0 if n >= end: print "finished" run1 = 0 ```

[3] I had a look at the examples so far and to get the grafting constant “g” solved g.10^(2n+1)=[(2+g).10^n]^2

James Grime noticed that 180°(3-√5) is the Golden Angle and did some more involved working out on twitter.

I do mathematics and stand-up. Sometimes simultaneously.
This entry was posted in Uncategorized. Bookmark the permalink.

### 8 Responses to When Matt Discovered “Grafting Numbers”

1. normally_distributed says:

Very nice.

Regarding the biologists insult, on one hand:
http://xkcd.com/435/

But on the other:
http://xkcd.com/520/

2. Blake Gravenor says:

I’d argue that it is physicists who are to blame for the “stamp collecting” biologists slur! Certainly Maths is full of classification problems (e.g. Finite Simple Groups) and most mathematicians I’ve known are interested in quirky number properties even if there isn’t necessarily a deep and meaningful result behind them.

Anyway, regarding Grafting Constants here’s a few observations I’ve made. If you look at them in the limit (i.e. with no truncation/rounding) you are effectively solving the quadratic below for g to be a Grafting Constant (in base b):

(m+g)^2 = (b^n)g for n, m integers (1) (The Grafting Equation perhaps?)

I won’t spell out the general solution but it can be shown that for b=10 and n = 1 there are only two valid solutions:
m=1, g=4-√15
m=2, g=3-√5 (as observed in your article)

There are infinitely many solutions with n>1 as the condition on allowable values of m becomes more relaxed. Each Grafting Constant can be used to generate a sequence (or family) of numbers in the same way as for g=3-√5, however not all these number are necessarily Grafting Numbers, e.g.

b=10, n=1, m=1, g=4-√15=0.12701665379…
√127 = 11.2694…
√12702 = 112.70314…
√1270167 = 1127.016858…
√127016654 = 11270.1665471…

I’ve only used Excel so I start getting rounding errors at this point but my guess is that eventually the sequence produces only valid Grafting Numbers. This leaves three interesting questions for somebody else to solve (in base 10):

1) Do all Grafting Constants eventually produce an infinite sequence of Grafting Numbers (after N terms)? I’m guessing the answer is yes
2) Are there any Grafting Constants (other than 3-√5) that produce a pure sequence of Grafting Numbers? This could be a good one to test the programming skills
3) Are there any exotic Grafting Numbers that don’t correspond to a term in one of these Grafting Constant sequences? WARNING: I think this one could be pretty hard!

3. Alex Brown says:

What I find curious about the “stamp-collecting” slur is the assumption that there’s anything wrong with stamp collecting.

4. Tyle Stelzig says:

I watched your ‘numberphile’ video about grafting numbers a week or so ago, and it inspired me to learn how to program (at least a little bit). So I downloaded python 2.7, and after reading through a bit of the documentation I wrote my own ‘graft finder’! Here’s my code, not necessarily an improvement but short and straightforward:

for a in range(1,1000000):
for b in range(0, int(ceil(log(sqrt(a),10)))+1):
if floor((sqrt(a)%pow(10,b))*pow(10,ceil(log(a,10))-b))==a:
print a, sqrt(a), ‘FOUND ONE! b==’, b

I wrote this before I knew you could convert things to different types, so ceil(log(sqrt…))) is just a way to find the length of sqrt(a) using maths instead of type conversion. Haven’t tested which is faster.

I’ve also been lucky enough to discover Project Euler, and would like to repeat your endorsement. In my spare time over the last week or so I’ve been doing some of those problems, and I’ve been having a really good time with it. I’m still very much a novice at Python, but I’m tremendously excited about the progress I’ve made. Project Euler keeps it fun and interesting with little challenges, and gives me a sense of accomplishment as I progress. I’ve done the first 50 so far… they’re starting to get a bit trickier, and it looks like I might have to really start learning how to write efficient algorithms!

So anyway, thanks for giving me that spark to get started with the programming. It truly is like skydiving – everyone should give it a shot, because it’s pretty cool that we can! But if anything, the barriers to learning a programming language are even lower, and it’s even more rewarding!

5. Blake Gravenor says:

Thought I’d just share this to get it off my chest even though this thread looks pretty dead! I stumpled onto this problem again after watching the original Numberphile video on YouTube and got to thinking about Grafting Numbers again. Suffice to say that I think everything I said a year ago (see comment above) is wrong! Sorry for filling up the server but get ready for a bit of a read.

Originally I stated (correctly) that there are an infinite number of solutions to the Grafting Equation (let’s call them Perfect Grafting Numbers). They are the fixed points of the Grafting Process if we were allowed to use infinite decimal expansions rather than finite numbers. I went on to say (point 1) that rounding all these Perfect Grafting Numbers could generate infinitely many finite Grafting Numbers. However I hadn’t studied the rounding process in enough detail. After some tinkering with Taylor series for the square root function I made the following discovery:

As you take ever more accurate approximatations of a Perfect Grafting Number, the difference caused by the grafting process scales linearly with the truncation error.

Let me explain in plain English for anyone who’s not a mathematician. Remember that the aim of the Grafting Process is to get back the same number we put in, and I’ve already got all these Perfect Grafting Numbers that do just that. So ideally I want to take finite approximations to these numbers and hope they work just as well. However the Grafting Process has a sting in the tail, just as you get close to the Perfect Grafting Numbers, running the process can move you away again if the parameters aren’t quite right.

In particular the scaling parameter (lets call it r for repulsiveness) mentioned in bold above must be less than 1. To see why, imagine I’ve approximated my Perfect Grafting Number g to N decimal places (where N is really big). Now my approximation error is at most 1/(10^N) but applying the scaling factor tells me the Grafting Process error is r/(10^N). If r is greater than 1 then this is enough to change one of the important decimal places and the approximation doesn’t work. Now the formula for r (when N is big) is as follows:

r = (m/g – 1)/2

Where m is the extra number you add onto the front during the Grafting Process. In my equation g is always less than 1 so m can be at most 3 if we want r<1. What's worse is that g and m are related by the Grafting Equation and generally if m is low then g is a lot less than 1 so even taking m = 2 or 3 is not usually good enough. In fact for base 10 there is only one Perfect Grafting Number that fits the bill: our old friend 3-√5.

So after all that I've got back to where Matt started! However I can add a couple of interesting facts:

1) There is only one other base with a Perfect Grafting Number with r<1, i.e. which can generate an infinite sequence of Grafting Numbers: in base 5 you can use (3-√5)/2. And that's it! (Unless you count 0.999999… or the equivalent in other bases, e.g. 0.7777777… in base 8).

2) Most Grafting Numbers are serendipitous accidents, they all correspond to a Perfect Grafting Number I think (there are an infinite number after all!) but the fact that the approximation error perfectly matches the Grafting Process error is just a happy coincidence.

Wow, I feel liberated!

6. Blake Gravenor says:

Due to popular(ish) demand, here’s the working behind the previous post.

Assume we’re given a “pure grafting number” g that satisfies the “grafting equation”:

(m + g)^2 = g*(b^n), in base b for some integers n and m (1)

Now round g to K decimal places and check if this is a (standard) grafting number, as defined by Matt in his post. Denote the rounded number [g] and the rounding error as e = [g] – g. Note that |e| <= 1/2*b^-K by definition. For [g] to be a grafting number we require:

√([g]*b^n) = m + [g] + d, where |d| <= 1/2*order([g]) = 1/2*b^-K (2)

Substitute in [g] = g + e to get: √((g + e)*b^n) = m + g + e + d
Rearrange to express d as: d = √(g*b^n)√(1 + e/g) – (m + g) – e
Use fact g satisfies equation (1): d = (m + g)(√(1 + e/g) – 1) – e (3)

Now use the Taylor series expansion of √(1 + x) around x=0:

√(1 + x) = 1 + x/2 – x^2/8 + x^3/16 – … (4)

Use (4) with x = e/g to rearrange equation (3):

d = -e + (m + g)*((e/g)/2 – (e/g)^2/8 + (e/g)^3/16 – …)

But if we chose the rounding point K to be large enough*, e is a lot less than g and powers of e/g can be ignored. Therefore for large K we get:

d = -e + (m + g)*(e/g)/2
d = e * (m/g – 1)/2 (5)

At this point, remember that e is a rounding error and therefore e*b^K is likely to be uniformly distributed on the interval (-1/2,1/2) for various values of K. Therefore to guarantee that d*b^K is also in this interval (as required by equation (2)) we need:

(m/g – 1)/2 <= 1, i.e.
m <= 3g (6)

I’ll just pause to point out that this condition is only required if we want all values of K (past a certain point, see *) to produce a valid grafting number. There may still be a (possibly infinite) number of cases where [g] is so close to g that although d is greater than e it is still < 1/2*b^K. However I think equation (6) must be true for pure grafting numbers that generate an infinite sequence of grafting numbers such as 3-√5.

Finally, getting back to equation (6), it is possible to combine it with the grafting equation itself (1) to get various relationships that must hold between b, n, m and g. After some fiddly case analysis I came up with the results detailed in the last post, that there are only tow valid values of g. However please feel free to check, the important point is that equations (1) and (6) are all you need.

7. Robert Tanniru says:

Awesome explanation, Blake!

I have been addicted to this problem on and off (mostly on) for the past month or so since I first watched Matt’s video about grafting numbers on Numberphile. I actually sent an email to Matt where I independently derived almost exactly the formula as you did in your first message on 1/24/12 (I used different variable names).

I originally focused on just the irrational numbers like 3-√5 and 4-√15 and all the others and I was always curious why the rounding always worked for 3-√5 but not consistently for all of the others. Using your r value, I delved back into the grafting integers (GIs), as I like to refer to them to differentiate them from the pure irrational grafting numbers (GNs). What I found was that, as you mention, the root error, d, that occurs when rounding up the GN needs to be less than 1 to make the result a GI. If e is the amount of initial rounding that occurs, d can be estimated as e*r as shown in your equation (5) where r = (m/g – 1)/2.

So if d needs to be < 1, then simply calculating e*r for a specific candidate GI will give a good indication of that candidate actually will be a GI. Now, as you show in your rearrangement of equation 3, (m/g – 1)/2 is always going to be an overestimate of the actual r value, so d*r is always going to be an overestimate of the e value. So there will be some candidates who have d*r slightly greater than 1 but are actually GIs so they will be false negatives. If you use the second term as well as the first term, then you will get a slight underestimate and will have a few false positives.

I actually came across this in excel and had no idea about the taylor series expansion or any of the derivation above. For 3-sqrt(5), the error seemed to be overestimated by (written using your variables):
[d^2*(5+sqrt(5))] / [8*b^K]

For 4-sqrt(15), it was the same, but with the term being 5+sqrt(15) instead and it was divided by 12 instead of 8. I even found that this new correction would cause the underestimation to be bound by a different term that related to d^3 but I never found what the number was though I could now using the taylor series!

Anyway, the point is that a candidate GI that has a d*r value of less than 1 is guaranteed to be a true GI. I wrote a program in Excel to find these GIs for various values of, as you call them, m, and n (I only use b=10 and p=2 for now). It first computes g using the quadratic equation for a specific m and n. Then it progressively tries multiplying g by 10^(n + 2k) for k = 0 to however many digits I want to search and looks for d values that are < 1/r.

Some examples are:
17,424,305,044,160 = [(4+0.17424305044160)*10^6]^2
658,350,974,743,100,200,166 = [(25+0.658350974743100200166) * 10^9]^2

I have calculated the smallest GIs for each n value from 1 to 100. The one for n=38 is 550 digits long!

If you're wondering how I have gotten so many digits of precision in Excel, I purchased an addin called xlPrecision (http://precisioncalc.com/xlprecision.html). I get 1500 digits of precision now. If you want to get it as well, let them know I referred you and I can get a rebate!

8. Robert Tanniru says:

I confused the d and e value a few times in my post above. d should be the resultant error of the square root and e should be the initial error of the rounding.

d ~= e*r

So each of the calculations in my Excel program look for e values that are less than 1/r since when that is the case, e*r will be less than 1.

Another thing, is that that assumes that r > 0. The only time that r is less than 0 is if m/g < 1. Since m is an integer and g is always between o and 1, this is only the case when m = 0. If m = 0, then, using the equation g*b^n = (g+m)^2 you get that g = 0 or 1. For g = 1, you can look at 100 and see that since r = -0.5, g-1 and g-2 should also be grafting integers and it turns out they are! That's where the the 99, 98, 9999, 9998, etc grafting integers come from!

The next step is generalizing this r value to different roots (cube, fourth, …, p-th).