AdamJTP

 

I don’t think I drink a lot (although alcoholics probably say that too), but I do drink regularly.

I’m taking a challenge to not drink alcohol until Christmas. That doesn’t sound too hard. Does it?

Unfortunately, Twitter is my “pub”. Many evenings I sit back with some wine and chat to people on Twitter.  It’s a sort of social drinking.

Books have the opposite effect.  If I’m reading a good book then my glass of wine will go untouched. I completely lose track of time.

So, until Christmas I’m going to stop tweeting and read more.

It seems like a logical strategy.

This isn’t some sort of major lifestyle change. It’s not like I’m going to start exercising or anything radical like that.

I’m just going to stop drinking. How hard could it be?

The purpose of this post is to give an example of using the ensembl genome database to investigate the genomes by playing spot the difference between species.

Disclaimer

“I don’t know what the hell I’m talking about!” ~ Me, August 2009

I’m not a biologist. Qualification wise I stopped at O level biology (and I don’t think my biology teacher had a good grasp of the subject either).

I’m primarily a software developer and recreational mathematician.  So my job is exploring data, constructing models and testing stuff.

Anti-disclaimer

So what if I’m not a biologist? I’m also not a great fan of accepting opinion on the basis of authority. I read books, magazines and journals. I’m not completely stupid. I do accept expert opinion, but I also like to see data.

This means you shouldn’t take any of my opinions on board, which is just as well because I’m not offering any (did I mention that I don’t know what the hell I’m talking about?).

Objectives

• I just want to look at some data and use it to influence my opinion. This has got to be better than either “Dawkins” told me or “God” told me.
• I want people to tell me how to improve my understanding of the Ensembl database (although given the small number of people that look at this blog, that’s probably a tall order!).

(my) methodology

I find this fun but I am a geek and your mileage may vary

Go to http://www.ensembl.org/

In the dropdown where it says “All genomes” (which is clearly not ALL genomes, but whatever!) I’ll pick “Human” because I’m human and I guess there’s quite a lot of data in there.

Okay. Now I get this:

There are some sample entry points (whatever THAT means). Yeah, like I’ll pick those! The purpose of this is to explore, not follow a map.

Now the search box is pretty cool. You seem to be able to put all sorts of biology stuff in there and get results back.

Pick a "biologyish” word. Haemoglobin, cardio, limbic, … . Choose whatever you want. Some words don’t get many results (lung seemed to be a dead-end, whereas pulmonary wasn’t – the moral of the story might be to use big words).

I’ll choose marrow because it was the first word that popped into my head.

If you ONLY choose marrow too then I’ve failed. The purpose of this is to explore not follow my map (especially as I don’t really know where I’m going).

If your want, choose marrow now, but try other things later.

You’ll get something like this back.

 

You see the little entries at the top? They tend to be dead ends (but I don’t know this to be true).

But the big one at the bottom looks like the database has some info.

Click on that and get a frightening screen.

Okay – I want to play spot the difference. See that “Genomic alignments (38)” link? Click on that.

Ah – now we’re getting somewhere.

There’re a bunch of letters. I know DNA uses the letters ACG and T. This looks like data.

(bear with me – nearly there)

Now let’s play spot the difference – against the Chimpanzee.

Some clever software lines them up against each other (sometimes there are blanks that the software shuffles in for you).

See that gene compared with the Chimp and Human? Their DNA is not identical.

Pretty close though. With humans and chimps it’s a bit like playing “Where’s Wally?”

Humans and dogs next.

Some bits are not even close:

Some bits are frighteningly close:

Next steps

You could ask the system to show you on a graph how close the different species are in terms of shared genome.

But isn’t it so much more fun to look at the streams of letters representing molecules making up the definition of a human and a chimp?

So now, try different genes (I picked genes involved with marrow at random).

Try other stuff too (we’ve only looked at a few of the features of this fantastic site). Explore the site. Have some fun.

Conclusion

Don’t talk saft! I don’t have a conclusion.

Get your own conclusions – that’s the point.

 

Today, @ViolaMaths introduced me to Beethoven numbers.

They’re not mathematically interesting like other special numbers. They’re just pandigital numbers (without any zeros) in base 10.

Now, it can be seen that the digits sum to a 45, which is divisible by 9.  This means all Beethoven numbers are divisible by 9.

This means that if we to factorize Beethoven numbers we’d see a lot of 3s.

Anyway here are factorizations of the first few Beethoven numbers:

123456789=3 3 3607 3803
123456798=2 3 3 3 3 769 991
123456879=3 3 3 3 3 3 7 13 1861

@ViolaMaths’s Beethoven number factorized is:

396457812=2 2 3 3 37 297641

The largest prime we’d see is 109739359 in:

987654231= 3 x 3 x 109739359

Graphing the frequency

So here’s the frequency of the prime factors for the first few primes:

2	323145
3	909442
5	54148
7	60320
11	34885
13	30083
17	22678
19	20216

 

Looking at all the data and unsurprisingly lower primes are more frequent.

And that graph stretches a LONG way to the right.

Let’s look at that line on the left:

We can see from the mini-table above that there’s a spike at 3 (as expected). I’d guessed that we’d see a number of 2s a bit lower than 9! (362880), the actual number was 323145.

There’s a bit of dip in the 5s, but as we’ve taken out the numbers ending in zero (Beethoven didn’t write a zeroth symphony).

If Beethoven had only written 7 symphonies then we wouldn’t get any 3s.

You’d expect to see effects like that when the numbers have a relationship to the number base.

 

Conclusion

None really. It allowed me to make some guesses about the frequency before running the test app, and the graph looked pretty much as I expected it to.

A fun exercise – nothing more interesting than that.

 

Revisiting the Saturday problem.

Given a number made only out of 1s, when is it exactly divisible by the number of 1s. How do we construct Niven Repunits?

This isn’t a tough problem, but my maths is rusty and I struggled to find a proof. I also wanted a proof that anyone with high school maths could follow.

In previous posts I put down some conjectures – it’s time to show some proofs. I’ve tried to make these as simple as possible.

Definitions

is a repunit (made of repeated 1s with n digits in number base b).

Algebraically they can be written as

A Niven repunit is divisible by the sum of its digits.  As all the digits are “1” this is equivalent to saying it’s divisible by the number of digits.

ie. A Niven repunit satisfies:

 

 

A pretty obvious lemma

First we’re going to show if:

then:

Proof (although you probably don’t need it)

When

 

 

Using induction

Assume

 

 

We know:

So

 

Easy Niven repunits theorem

This first theorem lets us find our first Niven repunits really easily by just ensuring the number of digits is a factor of one less than the number base.

Theorem

Given a repunit with n digits in base b.

When n is a factor of b-1

The repunit will be exactly divisible by n

IE.

If n is chosen such that

Proof

Because:

We know:

One definition of a repunit is:

So using

and the lemma we arrive at.

 

Second set of Niven repunits

This second theorem allows us to create huge Niven repunits based on the first and second type of repunit. e.g. Why repunits with 2,997 are Niven.

Theorem

Given a Niven repunit, a new Niven repunit can created with a number of digits that is obtained by multiplying the number of a digits in the first repunit by any factor of the first repunit.

Choosing a value of p such that:

Then:

Proof

By definition of a repunit:

Multiplying top and bottom by

 

Rearranging

Moving the powers about

 

Note that by the definition of repunit:

and

So

We know our original repunit was divisible by n (because it was a Niven repunit).

ie.

If we can just prove that the other repunit is divisible by p we’ll be done.

It’s not enough to say the first repunit is divisible by p because p and n could be the same number – so just because the 111 is divisible 3 it doesn’t make 111 divisible by 9 – we need to prove the second p digit repunit in base b^n is also divisible by 3 (in that example).

i.e. if:

then

We can use a similar proof to the first theorem:

We know:

and we chose p to be a factor of this so

So:

So

any by definition

Remembering

 

Which is what we wanted to prove.

So in a nutshell

Because

 

and

 

Notes

Given these two theorems we can construct huge Niven repunits in any number base. It does seem a bit odd that if we start with a three digit repunit in base 10 we could end up multiplying it by a 37 digit repunit in base 1000!

But if you think about how base 1000 would be represent in decimal and how long multiplication works you’d see that it was:

111×1001001001001…1001

 

If you did the long multiplication you can see why you’d get another repunit and why it would be Niven.

 

So where are we?

I’m looking at repeated sets of 1s that are divisible by the number of 1’s.

So:

111 is divisible by 3

111,111,111 is divisible by 9

Whereas

11 isn’t divisible by 2

1,111,111 isn’t divisible by 7

..and generalized to different number bases.

e.g. 1,111 in base 3 = 27+9+3+1 = 40 which is divisible by 4.

I called these Saturday numbers. The proper name is a Niven Repunit. Niven because it’s divisible by the sum of its digits and repunit because it’s a repeated unit – repeated 1s.

Defining repunits

Okay – in any number base a repunit is:

Where 

is the number base and 

is the number of digits.

And we want:

Which is a fancy way of saying if you divide it by 

you get 0 remainder (so it exactly divides by

). Which is exactly what we’re after.

Enter the mathematicians (Peter and Paul)

@PeterRowlett and @paulhertz swim in a sea of mathematics (whereas I swim in a sea of software development), they know how to do this stuff – and importantly where to look things up.

Paul did a search and found this:

Which looks promising.

Niven Repunits.  That’s exactly what I’m looking for!

Peter did a search and found that Fibonacci Quarterly is at the British Library:

My trip

As it happens, I’m in London on business next week.  I can quite easily make a detour to the British Library to look this up.

But it is helpful to define success/fail criteria before doing things, so these are my criteria for success/failure next week (wrt library trip – success for the business trip will be defined by the quality of the business requirements!).

 

What I hope I find

I hope to get a better understand of numbers, and why (whether?) my original conjectures are true.

What I don’t hope to find

The title of the article is Niven Repunits and

Now if all the article tells me is that Niven Repunits are values of 

that satisfy

then it’s just restating the problem.

 

Why?

 

 

Well if

Then

Where

Let

Then

or

 

Neater (but still obvious)

So saying a repunit is a Niven number (in base b) when:

is really just restating the original problem.

I hope I don’t find this – because even I can already see that!

 

Undue pessimism?

I’m fairly sure that getting something published in any maths journal takes more than a fairly obvious restatement of the problem.

I’m probably reading too much into the title. I don’t expect they publish the question and the conclusion on the same line!

I’ll post an update next week.

I asked my followers on twitter to help me in my search to understand what I’d called Saturday numbers better (I now have a proper name for them. More on that later).

@paulhertz replied an gave me some helpful links.

Firstly – a name

What I’ve been calling a Saturday number in base b is a b-Niven repunit.

How cool does that sound?

I didn’t spend the weekend messing about with some problem I heard on a podcast. I was investigating b-Niven repunits. I now what that means, but it still sounds awfully impressive.

A Niven number is one that is divisible by the sum of it’s digits (so 18 is divisible by 1+9 so is a Niven number, 19 isn’t divisible by 1+9 so it isn’t one).(Read more on Wikipedia).

A repunit has repeated digits. (Read more on Wikipedia).

That’s why my Saturday numbers are called b-Niven repunits (for base b).

Proper maths

Because @paulhertz also sent me some references and I’ve been following them up:

..which appears to be a bit of a dead end. I might have been able to track it down back when I was at University. But you might be surprised to know that I don’t have a 1989 copy of Fibonacci Quarterly on my shelves.

And this:

http://www.maths.tcd.ie/pub/ims/bull59/R5901.pdf

That’s more like it!

I’m going to look forward to reading this one.

The problem

We’re looking at numbers all made of “1”s that have a special property.

They are made of repeated 1s (repunit) and are exactly divisible by the number of 1s.

111 (3 1s) is divisible by 3

111,111,111 (9 1s) is divisible by 9

111,111,111,111,111,111,111,111,111 (27 1s) is divisible by 27

..but not all repunits have this property.

11 (2 1s) isn’t divisible by 2

1111 (4 1s) isn’t divisible by 4

I need a name for this special property. I’m going to call numbers with this property Saturday numbers (because Peter’s podcast was on a Saturday).  We’ll define it more formally later.  If anybody knows a proper name for these then let me know. Let me know if Saturday number means some else too.

Note, whether something is a Saturday number depends on the number base you’re writing it in.  We’ll consider this too below.

Following the examples?

You’ll probably want to use Wolfram|Alpha.

Open it up now.

I’ll wait.

So here’s a sample Wolfram|Alpha query:

(b^n -1)/(n*(b-1)) ,b=10,n=9

Change b and n to see if you get a whole number (a Saturday number).

If you’re really cruel try:

(b^n -1)/(n*(b-1)) ,b=10,n=27*757

to test a 20,439 digit long Saturday number.

Check in Wolfram|Alpha?

Heh – image that:

“Think of a 20,439 digit number where all the digits are the same but not zero. Divide it by the sum of the digits. The answer is:”

…and on and on for a whole load more digits. Check out out the scroll thumb on the right of that screenshot – ouch!

…maybe not such a good puzzle to pose your friends… 

 

Definitions

Repunit

I mean an “n” digit repunit in base b.

A repunit can be written as:

means a number with three 1s in base ten (the number at the bottom is the number of digits the number in brackets at the top is the number base).

or

 

If you don’t like to think of this as number bases then pretend I’m taking about the expression below instead. I’ll be doing all my working out in base 10 anyway, so trying to think in crazy number bases would just confuse the situation.

Saturday number

So a number

is a Saturday number if satisfies this condition:

The first cases – 1st conjecture

Let:

When

and

Then

 

What I’m trying to say is:

When n is a product of powers from the set of prime factors of b-1 it will be a Saturday number.

 

Example

Base 10

Firstly we find the prime factors of one less than our number base.

So 3 is our prime factor. When n is a power of 3

Will all be Saturday numbers.

That is to say in base 10: 3,9,27,81,243 etc digit numbers will be Saturday numbers (divisible by the number of digits in the number).

Base 13

So when n is a product of powers of 2 and/or 3 it will give us a Saturday number

That is to say in base 13: 2,3,4,8,9 etc digit numbers will be Saturday numbers.

 

The second cases – 2nd conjecture

These second cases mean that if we have a Saturday number (and the first case gives us some trivial cases to work from) we can find a bunch more more surprising Saturday numbers.

Let

Where

ie.

    is a Saturday number.

(by the definition of a Saturday number we know

    is an integer)

Factorising:

Then:

When:

That is if you multiply n by any combination of powers of prime factors of

then you will get another Saturday number.

 

Base 10

 

Example 1:

The first Saturday number n=3 (prime factors of 10-1=3 x 3)

Check in Wolfram|Alpha?

Therefore

That is

Is also a Saturday number.

Check in Wolfram|Alpha?

So an 111 digit number will be a new Saturday number (note unlike the first case it isn’t a simple power of 3), as will 3×37x37 digit numbers etc.

This makes Peter’s original podcast puzzle even more interesting. 37 isn’t just the result of the curiosity, it’s the source of a new one.

 

Example 2:

So the 9 digit base 10 Saturday number generated some new Saturday numbers for us:

Check in Wolfram|Alpha?

and

and

etc.

 

Example 3:

So:

are all Saturday numbers.

So if you have a number with 20,439 (27×757) digits (all 1) then it will be divisible by 20,439.

These numbers become unimaginably large quite quickly – although some are testable. I have run up to 100,000 digit numbers and found this to be true. Let’s look at some other number bases.

Base 4

In base 4, our 1st cases will also be powers of 3.

All numbers will be represented in base 10 for simplicity.

Example 1:

Giving us

as new Saturday numbers.

Check 21 digit base 4 numbers in Wolfram|Alpha?

Check 147 digit base 4 numbers in Wolfram|Alpha?

 

Example 2

So

etc are all Saturday numbers.

Base 3

Over the last week we’ve been looking at the “funny case” of 20 digit repunits in base 3 and scratching our heads.

Now we can see why it happens.

Start with the trivial cases n=4

Giving us

as another Saturday number.

Check in Wolfram|Alpha?

Note that you can also construct new Saturday numbers from 2nd case Saturday numbers.

That’s your lot – 3rd conjecture

All Saturday numbers are either 1st or 2nd case Saturday numbers.

Time to reflect on what I’ve learnt:

1. I’m becoming quite comfortable with LaTeX – It’s always been a struggle in the past, but I think I’m getting the hang of it and I’m starting to appreciate what an elegant language it is.
2. The BigInteger class rocks for investigating this sort of stuff.
3. I remembered how hard it is to express your ideas in maths notation. With whiteboards at work, we tend to scribble, draw lines and talk.  This doesn’t work remotely.  Also, at work we rarely have to really formally prove.
4. WolframAlpha isn’t as pointless as I first thought.  I tended to write code for real investigation but it was useful to test the output from the code.
5. Collaborating using twitter and blogs is HARD!  I think this would have helped:
• A shared workspace – like a blog (with LiveWriter support and supported LaTeX)  – but not a blog.  A shared, rich editing space.
• The ability to add notes and comments to lines in the blogs (e.g. Peter is a much better mathematician than I am. I would have liked to add notes questioning where he was going (or if he could give a specific example)).
• You’d probably need read, read/comment & read/write on a per problem basis. I don’t want to give anyone full access to my blog and they probably would feel the same. Besides – I’m not sure a blog is the right metaphor.
• Twitter helped for quick observations and conjectures (like n will never share a prime factor with x), but these tweets can get lost and confused other followers.
6. Nobody else joined in.  It would be nice if they had, but it probably isn’t everyone’s cup of tea.  In saying that, if mathematicians could see other maths problems that were being discussed they might join in (although I suspect for serious stuff they’d be careful about losing control).
7. This shit is addictive.  I used to lose weeks on these sorts of things when I was younger, I could easily see myself going the same way over this weekend.
8. Peter Rowlett is a very nice chap.  His job is to promote mathematics, but teaching us one person at a time probably doesn’t scale well!

To finish with – here’s a picture I generated whilst looking at the problem.