2009 July « AdamJTP

Archive for July, 2009

Factorization of Beethoven numbers

July 24, 2009

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.

Ummm... where's the graph?

And that graph stretches a LONG way to the right.

Let’s look at that line on the left:

Up then down.

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.

No surprise

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.

Posted in Uncategorized | Leave a Comment »

Constructing Niven repunit – proofs

July 23, 2009

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

$R_{n}^{b}$

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

Algebraically they can be written as

$R_{n}^{b}=\sum_{i=0}^{n-1}b^i=\frac{b^n-1}{b-1}$

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:

$R_{n}^{b}\equiv0\pmod{n}$

A pretty obvious lemma

First we’re going to show if:

$a\equiv1\pmod{p}$

then:

$a^n\equiv1\pmod{p}$

Proof (although you probably don’t need it)

When

$n=0$

$a^0=1$

$a^0\equiv1\pmod{p}$

Using induction

Assume

$a^i\equiv1\pmod{p}$

$a^{i+1}=a^ia$

$\equiv1a\pmod{p}$

We know:

$a\equiv1\pmod{p}$

$1a\equiv1\pmod{p}$

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.

$R_n^b\equiv0\pmod{n}$

If n is chosen such that

$b-1\equiv0\pmod{n}$

Proof

Because:

$b-1\equiv0\pmod{n}$

We know:

$b\equiv1\pmod{n}$

One definition of a repunit is:

$R_n^b=\sum_{i=0}^{n-1}b^i$

So using

$b\equiv1\pmod{n}$

and the lemma we arrive at.

$R_n^b\equiv\sum_{i=0}^{n-1}b^i\equiv\sum_{i=0}^{n-1}1\equiv{n}\equiv{0}\pmod{n}$

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.

$R_n^b\equiv0\pmod{n}$

Choosing a value of p such that:

$R_n^b\equiv0\pmod{p}$

Then:

$R_{np}^b\equiv0\pmod{np}$

Proof

By definition of a repunit:

$R_{np}^b=\frac{b^{np}-1}{b-1}$

Multiplying top and bottom by

$b^n-1$

$=\frac{b^n-1}{b^n-1}\frac{b^{np}-1}{b-1}$

Rearranging

$=\frac{b^n-1}{b-1}\frac{b^{np}-1}{b^n-1}$

Moving the powers about

$=\frac{b^n-1}{b-1}\frac{{(b^n)}^p-1}{b^n-1}$

Note that by the definition of repunit:

$R_n^b=\frac{b^n-1}{b-1}$

and

$R_p^{b^n}=\frac{{(b^n)}^p-1}{b^n-1}$

$R_{np}^b=R_{n}^bR_{p}^{b^n}$

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

ie.

$R_n^b\equiv0\pmod{n}$

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:

$R_{p}^{b^n}\equiv0\pmod{p}$

then

$R_{np}^b\equiv0\pmod{np}$

We can use a similar proof to the first theorem:

We know:

$R_n^b=\frac{b^n-1}{b-1}$

and we chose p to be a factor of this so

$\frac{b^n-1}{b-1}\equiv0\pmod{p}$

So:

$b^n-1\equiv0\pmod{p}$

$b^n\equiv1\pmod{p}$

any by definition

$R_p^{b^n}=\sum_{i=0}^{p-1}(b^n)^i$

Remembering

$b^n\equiv1\pmod{p}$

$R_p^{b^n}\equiv\sum_{i=0}^{p-1}(b^n)^i\equiv\sum_{i=0}^{p-1}(1)^i\equiv{p}\equiv{0}\pmod{p}$

Which is what we wanted to prove.

So in a nutshell

$R_{np}^b\equiv0\pmod{np}$

Because

$R_{np}^b=R_{n}^bR_{p}^{b^n}$

$R_n^b\equiv0\pmod{n}$

and

$R_{p}^{b^n}\equiv0\pmod{p}$

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.

Posted in Uncategorized | Leave a Comment »

A fortunately timed trip

July 18, 2009

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:

$R_{n}^{(b)}=\sum_{i=0}^{n-1}b^i=\frac{b^n-1}{b-1}$

Where

$b$

is the number base and

$n$

is the number of digits.

And we want:

$R_{n}^{(b)}\pmod{n}\equiv0$

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

$n$

you get 0 remainder (so it exactly divides by

$n$

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

Niven Repunits

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:

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

$10^n\equiv1$

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

$n$

that satisfy

$10^n\equiv1$

then it’s just restating the problem.

Why?

$R_{n}^{(b)}=\frac{b^n-1}{b-1}$

Well if

$\frac{b^n-1}{b-1}\pmod{n}\equiv0$

Then

$a\frac{(b^n-1)}{b-1}\pmod{n}\equiv0$

Where

$a\in\mathbb{N}_0$

Let

$a=b-1$

Then

$b^n-1\pmod{n}\equiv0$

$b^n\pmod{n}\equiv1$

Neater (but still obvious)

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

$b^n\pmod{n}\equiv1$

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.

Posted in Uncategorized | Leave a Comment »

Twitter to the rescue

July 15, 2009

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.

Posted in Uncategorized | 7 Comments »

Revisiting Saturday’s problem

July 14, 2009

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

$R_n^{(b)}$

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

A repunit can be written as:

$R_{n}^{(b)}=\sum_{i=0}^{n-1}b^i=<br /> \frac{b^n-1}{b-1}” title=”R_{n}^{(b)}=\sum_{i=0}^{n-1}b^i=<br /> \frac{b^n-1}{b-1}” /></div> </p> <blockquote><p>Example:</p> <div style=$ $R_{3}^{(10)}$

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

$R_{3}^{(10)}=10^2+10^1+10^0=100+10+1=111$

$R_3^{(10)}=\frac{10^3-1}{10-1}=\frac{999}{9}=111$

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.

$\sum_{i=0}^{n-1}b^i$

Saturday number

So a number

$R_{n}^{(b)}$

is a Saturday number if satisfies this condition:

$R_{n}^{(b)}\pmod{n}\equiv0$

The first cases – 1st conjecture

Let:

$b-1=\prod{p_i^{\alpha_i}}$

When

$n=\prod{p_j^{\beta_j}}$

and

$\{p_j\}\subseteq\{p_i\}$

Then

$R_{n}^{(b)}\pmod{n}\equiv0$

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.

$10-1=9=3^2$

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

$R_3^{(10)},R_{3^2}^{(10)},R_{3^3}^{(10)},...R_{3^j}^{(10)}$

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

$13-1=12=2^23$

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

$R_2^{(13)},R_{3}^{(13)},R_{2^j3^k}^{(13)}$

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

$Q_n^{(b)}=\frac{R_n^{(b)}}{n}$

Where

$R_{n}^{(b)}\pmod{n}\equiv0$

ie.

$R_{n}^{(b)}$

is a Saturday number.

(by the definition of a Saturday number we know

$Q_n^{(b)}$

is an integer)

Factorising:

$Q_n^{(b)}=\prod{q_i^{\beta_i}}$

Then:

$R_{m}^{(b)}\pmod{m}\equiv0$

When:

$m=n\prod{q_j^{\gamma_j}}$

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

$Q_n^{(b)}$

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)

$R_3^{(10)}=111$

$Q_3^{(10)}=\frac{111}{3}=37$

Check in Wolfram|Alpha?

Therefore

$R_{3\times37}^{(10)}\pmod{3\times37}\equiv0$

That is

$R_{3\times37}^{(10)}$

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:

$R_9^{(10)}=111111111$

$Q_3^{(10)}=\frac{111111111}{9}=12345679=37\times333667$

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

$R_{9\times37}^{(10)}\pmod{9\times37}\equiv0$

Check in Wolfram|Alpha?

and

$R_{9\times333667}^{(10)}\pmod{9\times333667}\equiv0$

and

$R_{9\times37^i\times333667^j}^{(10)}\pmod{9\times37^i\times333667^j}\equiv0$

etc.

Example 3:

$R_{27}^{(10)}=111111111111111111111111111$

$Q_{27}^{(10)}=\frac{111111111111111111111111111}{27}$

$=4115226337448559670781893$

$=37\times757\times333667\times440334654777631$

So:

$R_{27\times37}^{(10)},R_{27\times757}^{(10)},R_{27\times333667}^{(10)},R_{27\times440334654777631}^{(10)},R_{27\times757\times333667}^{(10)}$

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:

$R_3^{(4)}=21$

$Q_3^{(4)}=\frac{21}{3}=7$

Giving us

$R_{3\times7}^{(4)},R_{3\times7^2}^{(4)}$

as new Saturday numbers.

Check 21 digit base 4 numbers in Wolfram|Alpha?

Check 147 digit base 4 numbers in Wolfram|Alpha?

Example 2

$R_9^{(4)}=87381$

$Q_9^{(4)}=\frac{87381}{9}=9709$

$9709=7\times19\times73$

So

$R_{9\times7}^{(4)},R_{9\times19}^{(4)},R_{9\times73}^{(4)},R_{9\times7\times73}^{(4)}$

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

$R_4^{(3)}=40$

$Q_4^{(3)}=\frac{40}{4}=10=2\times5$

Giving us

$R_{4\times5}^{(3)}=R_{20}^{(3)}$

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.

Posted in Uncategorized | Leave a Comment »

Reflection

July 13, 2009

Time to reflect on what I’ve learnt:

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.
The BigInteger class rocks for investigating this sort of stuff.
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.
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.
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.

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

Not the world's most interesting chart

Posted in Uncategorized | Leave a Comment »

Journey’s end

July 12, 2009

Okay – it’s been a fun weekend playing with numbers but I think it’s drawing to a close. I do have a real job to do, and I’m really just playing at this. This is documenting my hobby.

How Peter Rowlett had the patience to work through a throw away mathematical curiosity with a nong like me I don’t know – but it is a testament to how passionate he is about his subject.

Anyway Wikipedia (kindof) pointed this out:

…which is a pretty obvious way of thinking about repunits.

So if we’re dealing with a 3 digit repunit in base 10

So we get integer solutions when:

has integer solutions

My two conjectures

After looking at the numbers I had two conjectures:

1. That n must share at least one prime factor with x-1

..give me a chance I’m still thinking about this one…

2. That n must not share any prime factors with x

Let be a prime factor of and such that

Well if

and is divisible by then must also be divisible by (assuming n>1).

Now we’ve got.

But clearly

because

So that’s a contradiction and I can see now why this was the case.

Posted in Uncategorized | Leave a Comment »

..peter’s last comment..

July 12, 2009

Peter wrote the stuff below in the comment of the previous post.

Okay, I am cooking dinner but before I started I wrote the following. Meant to carefully check it for more silly errors after dinner but what the hey, here goes:

The follows shows that we can build numbers $n$ which satisfy the rule that a number consisting of $n$ digits, all 1, is divisible by $n$ with no remainder.

This means we can define any $n=g^m$ so that a number $a$ consisting of $n$ digits, all 1, is divisible by its digit sum if we choose a $g$ that satisfies $b \equiv 1 \pmod{g}$ .

This does not mean that any number for which this rule works is necessarily of the form $n=g^m$ .

Theorem

Working in base $b$ , let $s=g^p$ , $p$ a positive integer and g a positive integer satifying $b\equiv 1 \pmod{g}$ .

Define $n_i$ using:

$n_0 = 1$

$n_{k+1} = sn_k$

and $a_i$ using:

$a_0 = 1$

$a_{k+1} = Ma_k$

where $M = \sum_{p=0}^{s-1} b^{ps^k}$ .

Then,

$\frac{a_i}{n_i}\equiv 0 \pmod{n_i}$

Proof

Take the following results as proven:

1. If an integer $n$ is written in base $b$ , and $d$ is an integer with $b\equiv 1 \pmod{d}$ , then $n$ is divisible by $d$ if and only if the sum of its digits is divisible by $d$ . (Special case: $b=10$ and $d = 3$ or $d = 9$ ).

2. If $a \equiv 0 \pmod{c}$ and $b \equiv 0 \pmod{d}$ then $ab \equiv 0 \pmod{cd}$

Prove P(0):

$\frac{a_0}{n_0} = 1 \equiv 0 \pmod{n_0}$

Let

$n_0 = 1$

$a_0 = 1$

Then,

$\frac{a_0}{n_0} = \frac{1}{1} = 1 \equiv 0 \pmod{n_0}$

Assume P(k) is true:

$\frac{a_k}{n_k} = 1 \equiv 0 \pmod{n_k}$

Then prove P(k+1):

$\frac{a_{k+1}}{n_{k+1}} = 1 \equiv 0 \pmod{n_{k+1}}$

$\frac{a_{k+1}}{n_{k+1}} = \frac{Ma_k}{sn_k} = \frac{M}{s} \times \frac{a_k}{s_k}$

Since P(k) is true, we have

$\frac{a_k}{n_k} \equiv 0 \pmod{n_k}$

Then consider $\frac{M}{s}$ .

Remember $M = \sum_{p=0}^{s-1} b^{ps^k}$ is an $s$ digit number.

From result 1, if an integer $M$ is written in base $b$ , and $g$ is an integer with $b \equiv 1 \pmod{g}$ , then $M$ is divisible by $g$ if and only if the sum of its digits is divisible by $g$ .

Remember $s = g^p$ , so the number of digits of $M$ , $s$ , is divisible by $g$ . Therefore $M$ is divisible by $g$ . Let $M = g^q$ which $q$ some positive integer with $q>p$ .

(Since $M$ involves only positive terms to the power of $s$ and $s>1$ (since $p>0$ ), $M>s$ ).

So we can express

$\frac{M}{s} = \frac{g^q}{g^p}$

and since $q>p$ ,

$\frac{M}{s} = \frac{g^q}{g^p} \equiv 0 \pmod{g^p}$

Then, since $s=g^p$ ,

$\frac{M}{s} \equiv 0 \pmod{s}$

Now using result 2 we have

$\frac{a_k}{n_k} \equiv 0 \pmod{n_k}$

$\frac{M}{s} \equiv 0 \pmod{s}$

$\frac{a_{k+1}}{n_{k+1}} = \frac{Ma_k}{sn_k} = \frac{M}{s} \times \frac{a_k}{n_k} \equiv 0 \pmod{sn_k}$

and $sn_k = n_{k+1}$ so

$\frac{a_{k+1}}{n_{k+1}} \equiv 0 \pmod{sn_k}$

…and there’s more…

Okay, there are mistakes in the \latex here, such as $\frac{a_0}{n_0} = 1 \equiv 0 \pmod{n_0}$ should be $a_0 = 1 \equiv 0 \pmod{n_0}$ , (but I’m getting better) and in the maths, such as when I say if $M$ is divisible by $g$ then $M$ can be written as $M=g^q$ for some $q$ .

Anyway, in correcting it I think I have found a necessary and sufficient test for whether an n-digit number works (it hinges on proving another result). This is below with some examples. Once it is posted I will not doubt find a load of errors!

To test if an $n$ -digit number with all digits equal is divisible by the sum of its digits:

Working in base $b$ , let $g$ be a positive integer satisfying $b\equiv 1 \pmod{g}$ and define an n-digit number:

$A = lM$

for some $0 < l < 10$ with $M = \sum_{i=1}^{n} b^{i-1}$ .

Find $q$ such that $g^q < M < g^{q+1}$ (i.e., find the power of $q$ that gives the greatest number not greater than $M$ ). Then we can write $M$ as

$M = g^q + gt$

for t some positive integer.

Calculate

$g^q \equiv \alpha \pmod{n}$

$gt \equiv \beta \pmod{n}$

Then $A \equiv 0 \pmod{n}$ if and only if $\alpha + \beta \equiv 0 \pmod{n}$

That is, if both $\alpha=0$ and $\beta=0$ or $\alpha + \beta = n$ .

Note that if $M = g^q$ then $\alpha = \beta = 0$ and this is an earlier result we had. The cases that didn’t fit that pattern are those where $\alpha + \beta = n$ such as 202 (20) in base 3 or 111 in base 10.

Examples

1. In base 10, let $n=3$ so $M=111$ . Then $q=4$ and $t=10$ . $M$ written as $111 = 3^4 + 3 \times 10 = 81 + 30$ .

Calculate:

$81 \equiv 0 \pmod{3}$

$30 \equiv 0 \pmod{3}$

Since $\alpha$ and $\beta$ are both $0$ , $111$ is divisible by its digit sum.

2. In base 10, let $n=6$ so $M=111111$ . Then $q=10$ and $t=17354$ . $M$ written as $111111 = 3^{10} + 3 \times 17354$ .\\

Calculate:

$3^{10} \equiv 3 \pmod{6}$

$17354 \times 3 \equiv 0 \pmod{6}$

So $\alpha + \beta = 3 \neq 0$ so a $6$ digit number of this form is not divisible by its digit sum.

3. In base 10, let $n=12$ so $M=111111111111$ . Then $q=23$ and $t=5655977428$ .

Calculate:

$3^{23} \equiv 3 \pmod{12}$

$5655977428 \times 3 \equiv 0 \pmod{12}$

So $\alpha + \beta = 3 \neq 0$ so a $12$ digit number does not work.

4. In base 10, let $n=111$ (notice $111$ cannot be written as $3^p$ for any integer $p$ ) so $M=1…1$ has $111$ digits. Then $q=230$ and $t=18807848747093916309532620724520528630446052984091732544048431123431\linebreak707984366313069669581821075636677387820154$ .

Calculate:

$3^{230} \equiv 90 \pmod{12}$

$18807848747093916309532620724520528630446052984091732544048431\linebreak123431707984366313069669581821075636677387820154 \times 3 \equiv 21 \pmod{12}$

So $\alpha + \beta = 111 \equiv 0 \pmod{111}$ so a $111$ digit number is divisible by the sum of its digits (N.B. even though $\alpha$ and $\beta$ and not each equal to $0$ ).

5. In base 3, let $n=2$ so $M=11$ . (In base 10, $n=2$ , $M=4$ ). Then $q=2$ and $t=0$ so we write $11 = 2^2 + 2 \times 0 = 2^2$ .

Calculate:

$2^2 \equiv 0 \pmod{2}$

$0 \times 2 \equiv 0 \pmod{2}$

Since $\alpha$ and $\beta$ are both $0$ , a $2$ digit number of this form is divisible by its digit sum.

6. In base 3, let $n=101$ so $M=1111111111$ . (In base 10, $n=10$ , $M=29524$ ). Then $q=112$ (base 10: $14$ ) and $t=100000100$ (in base 10, $6570$ ) so we write $1111111111 = 2^{112} + 2 \times 100000100 = 2^2$ (in base 10, $29524 = 2^{14} + 2 \times 6570$ .

Calculate:

$2^{112} \equiv 4 \pmod{101}$
(In base 10: $2^{14} \equiv 4 \pmod{10}$ )

$2 \times 100000100 \equiv 0 \pmod{101}$
(In base 10: $2 \times 6570 \equiv 0 \pmod{10}$ )

Since $\alpha + \beta = 4 \neq 0$ , $1111111111$ is not divisible by its digit sum.

7. In base 3, let $n=202$ so $M=11111111111111111111$ . (In base 10, $n=20$ , $M=1743392200$ ). (N.B. $M$ cannot be expressed as $2^p$ for any integer $p$ ). Then $q=1010$ and $t=212100000212210220$ (in base 10, $q=30$ and $t=334825188$ ) so we write $11111111111111111111 = 2^{1010} + 2 \times 212100000212210220$ (in base 10 $1743392200 = 2^{30} + 2 \times 334825188$ ).

Calculate:

$2^{1010} \equiv 11 \pmod{202}$
(In base 10: $2^{30} \equiv 4 \pmod{20}$ )

$2 \times 212100000212210220 \equiv 121 \pmod{202}$
(In base 10: $2 \times 334825188 \equiv 16 \pmod{20}$ )

Since $\alpha + \beta = 11 + 121 = 202 \equiv 0 \pmod{202}$ , $11111111111111111111$ is divisible by its digit sum.

Let’s have a stab at a proof:

Working in base $b$ , let $g$ be a positive integer satifying $b\equiv 1 \pmod{g}$ and define an n-digit number:

$A = lM$

for some $0 < l < 10$ with $M = \sum_{i=1}^{n} b^{i-1}$ .

Then $A \equiv 0 \pmod{n}$ if and only if $M \equiv 0 \pmod{n}$ (since $\frac{A}{n} = \frac{lM}{n} = l \frac{M}{n}$ ).

Find $q$ such that $g^q < M < g^{q+1}$ (i.e., find the power of $q$ that gives the greatest number not greater than $M$ ). Then we can write $M$ as

$M = g^q + gt$

for t some positive integer.

Let

$g^q \equiv \alpha \pmod{n}$

$gt \equiv \beta \pmod{n}$

We use (without proving) the following result:

If and only if $a \equiv c \pmod{n}$ and $b \equiv d \pmod{n}$ then $a+b \equiv c+d \pmod{n}$

Then

$M \equiv 0 \pmod{n}$

if and only if

$\alpha + \beta \equiv 0 \pmod{n}$

Then $A \equiv 0 \pmod{n}$ if and only if $\alpha + \beta \equiv 0 \pmod{n}$

Not sure about cases where $g$ is not unique.

Posted in Uncategorized | 1 Comment »

…picking up supplies..

July 12, 2009

PeterRowlett thinks this could hinge on proving:

n is divisible by d (d satifies b ≡ 1 (mod d)) iff sum of its digits is divisible by d

Okay – let’s try this:

b ≡ 1 (mod d)

b-1 ≡ 0 (mod d)

Hang on I think I’ve got a lemma!

(gonna do some induction here)

Want to prove:

Start with:

is clearly divisible by

Now lets look at the case i

Okay take and add

Re-arrange

Take out the in the second bit

So

Now clearly (the second bit) is divisible by

so is divisible by b-1 iff is divisible by because we’ve shown the second bit is divisible by .

So I think we’ve proved by induction that

?

Okay – let’s put that on one side and get back to the original bit.

writing n in our number base

Let’s represent n in base b

Example (gotta do these ‘cos I’m not too sure if my notation shows what I want to express).

So if we’re looking at the number 1234 in base 10.

a(0)=4, a(1)=3, a(2)=2, a(3)=1

giving

Okay let’s rearrange

Now we can see that the second bit:

is clearly divisible by b-1 because all terms are divisible by (using the lemma).

so n is divisible by iff is.

Now:

iff

d=b-1 or d is a factor of b-1

..so I think it’s proven?

Posted in Uncategorized | 1 Comment »

Okay time for getting some stuff down.

July 12, 2009

Defining our n digit repunit.

1111…1111 etc – let’s say we have “n” 1’s in a row.

That is (in base 10)

So if we have the three digit repunit

1+10+100 = 111

or in base b

Or (making it look a bit more mathsy)

Now lets take off 1 from each number.

111=1+10+100 = 1+1+1 + (0+9+99)

Now, clearly n is divisible by n.

So for

to be divisible by n then

must also need to be divisible by n.

Note

when p=0

Now consider (in base 10)

9+99+999 = 9 + ((10*9)+9)+((100*9)+(10*9)+9)

= 3*9 + (10*9) + (10*9)+(100*9)

…TBC

Posted in Uncategorized | Leave a Comment »

	Bruce on Chaos for eight year olds
	Roxanne Honeymoons on Chaos for eight year olds
	Fay Cooper on Chaos for eight year olds
	adamjtp on 10 shallow thoughts about the …
	Mark Darling on 10 shallow thoughts about the …

Archive for July, 2009

Graphing the frequency

Conclusion

Definitions

A pretty obvious lemma

Proof (although you probably don’t need it)

Easy Niven repunits theorem

Theorem

Proof

Second set of Niven repunits

Theorem

Proof

Notes

Defining repunits

Enter the mathematicians (Peter and Paul)

My trip

What I hope I find

What I don’t hope to find

Why?

Neater (but still obvious)

Undue pessimism?

Firstly – a name

Proper maths

And this:

The problem

Following the examples?

Definitions

Repunit

Saturday number

The first cases – 1st conjecture

Example

Base 10

Base 13

The second cases – 2nd conjecture

Base 10

Base 4

Base 3

That’s your lot – 3rd conjecture

My two conjectures

1. That n must share at least one prime factor with x-1

2. That n must not share any prime factors with x

Theorem

Proof

…and there’s more…

Hang on I think I’ve got a lemma!

writing n in our number base

Note

Archives

Recent comments

Other stuff

devProcess

Other stuff