Republic of Mathematics blog

The digits of 1/2 (base 2.5)

Posted by: Gary Ernest Davis on: April 27, 2010

In: Uncategorized
1 Comment

The unusual title for this post comes from a tweet from my Twitter colleague Peter Flom.

Peter tweeted that he was thinking about writing numbers in base 2.5

I recalled that some years ago when I was teaching a graduate mathematics education class at Rutgers, we looked at an algorithm for generating the expansion of a number in a given whole number base, and one of the students asked what would happen if we chose a fractional base – like $2\frac{1}{2}$ .

We implemented the algorithm in Excel, so we just changed the base from a whole number – 2 – to a fractional number – $2\frac{1}{2}$ – and bingo! the digits of the expansion appeared.

Writing numbers in different whole number bases

How do we go about writing a number such as $\frac{1}{3}$ as a sequence of digits base 2?

First we have to agree on what the digits base 2 are. The usual convention is that they are the digits 0 and 1.

So we are looking for a representation of $\frac{1}{3}$ in the form $\frac{1}{3}=0.b_1b_2 b_3\ldots$ Â (base 2) where the $b_n$ are digits 0 or 1.

By this we mean that $\frac{1}{3}=\frac{b_1}{2}+\frac{b_2}{2^2}+\frac{b_3}{2^3}+\ldots$ .

How can we find the sequence of digits $b_n$ ?

The key is to begin by multiplyingÂ $\frac{1}{3}$ by the base 2. Â This gives us the representation $\frac{2}{3}=b_1+0.b_2b_3b_4\ldots$ .

The digit $b_1$ is then the integer part – or floor – of $\frac{2}{3}$ , so $b_1=0$ and $\frac {2}{3}=0.b_2b_3b_4\ldots$

Now we multiply by 2 again to get the repesentation $\frac {4}{3}=b_2+0.b_3b_4b_4\ldots$ .

This means that $b_2$ is the floor of $\frac{4}{3}$ , namely 1, and $\frac{1}{3}=\frac{4}{3}-1=0.b_3b_4b_5$ .

Now we are in luck, because we have a representation for $\frac{1}{3}$ again, so we can take $0=b_1=b_3=b_5\ldots$ and $1=b_2=b_4=b_6\ldots$ .

So the base 2 representation for $\frac{1}{3}$ is $0.01010101\ldots$

Recall this means that $\frac{1}{3}=\frac{1}{2^2}+\frac{1}{2^4}+\frac{1}{2^6}+\ldots$

Writing the algorithm in Excel

The recursive algorithm for finding the digits in the base 2 expansion of a number is so simple that we can code it in Excel (of course feel free to use Python or R).

Here’s how the Excel spreadsheet looks:

base =	2	n	b(n)	a(n)
number =	1/3	1	0	1/3
		2	1	2/3
		3	0	1/3
		4	1	2/3
		5	0	1/3
		6	1	2/3
		7	0	1/3
		8	1	2/3
		9	0	1/3
		10	1	2/3
		11	0	1/3
		12	1	2/3
		13	0	1/3
		14	1	2/3
		15	0	1/3
		16	1	2/3
		17	0	1/3
		18	1	2/3
		19	0	1/3
		20	1	2/3

with the entries in the a(n) column set to be fractions (rather than decimal expansions).

The simple Excel code to generate this table is as follows:

base =	2	n	b(n)	a(n)
number =	=1/3	1	=INT(E2*$B$1)	=B2
		=C2+1	=INT(E3*$B$1)	=E2*B$1-D2
		=C3+1	=INT(E4*$B$1)	=E3*B$1-D3
		=C4+1	=INT(E5*$B$1)	=E4*B$1-D4
		=C5+1	=INT(E6*$B$1)	=E5*B$1-D5
		=C6+1	=INT(E7*$B$1)	=E6*B$1-D6
		=C7+1	=INT(E8*$B$1)	=E7*B$1-D7
		=C8+1	=INT(E9*$B$1)	=E8*B$1-D8
		=C9+1	=INT(E10*$B$1)	=E9*B$1-D9
		=C10+1	=INT(E11*$B$1)	=E10*B$1-D10
		=C11+1	=INT(E12*$B$1)	=E11*B$1-D11
		=C12+1	=INT(E13*$B$1)	=E12*B$1-D12
		=C13+1	=INT(E14*$B$1)	=E13*B$1-D13
		=C14+1	=INT(E15*$B$1)	=E14*B$1-D14
		=C15+1	=INT(E16*$B$1)	=E15*B$1-D15
		=C16+1	=INT(E17*$B$1)	=E16*B$1-D16
		=C17+1	=INT(E18*$B$1)	=E17*B$1-D17
		=C18+1	=INT(E19*$B$1)	=E18*B$1-D18
		=C19+1	=INT(E20*$B$1)	=E19*B$1-D19
		=C20+1	=INT(E21*$B$1)	=E20*B$1-D20

The key is to start with $a(1)$ as the number whose base 2 representation we want to find. Then $b(n)=$ integer part (=floor) of $a(n-1)*base$ Â (in this case the base is 2), and $a(n)=a(n-1)*base-b(n-1)$ .

Having set up the Excel code this way we can change the number whose representation we want to find from $\frac{1}{3}$ to $\frac{1}{4},\frac{1}{5}$ or even $\pi$ .

Changing to another whole number base

We can also change the base. If we change the base to 3, so using the digits $0, 1, 2$ in our representations, we get, for example, $\frac{1}{4}=0.02020202\ldots$ (base 3).

Changing to a Â fractional base

But nothing stops us from choosing a fractional base, such as $2\frac{1}{2}$ .

In this case the digits will be 0, 1 or 2 Â – the non-negative integers less than $2\frac{1}{2}$ .

Then, we get, for example,Â $\frac{1}{2}=0.10111000011012100011111210001002000100120100111110\ldots$ (base 2.5).

Changing to arbitrary real number bases

We can even choose transcendental bases such as $\pi$ and to within the numerical accuracy of Excel, we get $\frac{1}{2}=0.11211202102012230001010010211022022021112301100001\ldots$ (base $\pi$ ).

Changing to complex integer bases

We can even calculate the base b expansion of a number where b is a complex integer – that is a complex number of the form $m+ni$ where m and n are integers. Â This is because there is a nice floor function for complex integers, which is $\textrm{Floor}(m+ni)=\textrm{Floor}(m)+\textrm{Floor}(n)i$ .

We can use the built-in complex arithmetic of Excel to carry out the calculations as before (but you might want to use Mathematica, MATLAB, R or Python instead).

Two examples are:

$\frac{1}{2} = 0.00i$ (base 1+i ) and $\frac{1}{3 }= 0.00-1(-1+i)0i -1i$ repeated (base 1+i).

Postscript

Because of the problem of non-uniqueness of representation in weird bases, one needs to think a little about what are appropriate digits for a base b representation, where b is something other than a positive integer, as pointed out in the comment by John Lame, below.

A lovely account of representation in weird bases appears in James Tanton’s Exploding Dots.

How long does it take to count to one trillion?

Posted by: Gary Ernest Davis on: February 16, 2010

In: Uncategorized
3 Comments

MyFox Houston quotes University of Houston professor Jim Granato as saying that it would take someone more than 31,000 years to count to one trillion.

Where does this estimate come from?

Recall that a trillion is a thousand billion, and a billion is a thousand million.

There are Â 31,536,000 seconds in a 365 day year, and one trillion divided by 31,536,000 is approximately 31,710.

So it looks like that’s where the estimate of over 31,000 years to count to one trillion came from: it’s based on an assumption that a person is counting one number each second.

But let’s think about this a little.

Can we easily count to 10 in 10 seconds? Sure: just say each number name, taking at most one second each time: “one”, “two”, …, “ten”. I had no trouble doing this.

How about counting to 100? Could we do that in 100 seconds by saying each number name in 1 second or less?

Now, it’s not quite so clear. The problem is the longer number names as we get into the teens and then the twenties, thirties, forties, and so on. Names like “thirteen, fourteen, fifteen, …” take longer to say than the number names from 1 through 10. And when we get to 20 we have “twenty one, twenty two, twenty three” and so on.

So unless we speed up how fast we say each number name, it’s looking like it will take longer than 100 seconds to count to 100. How much longer?

Counting time assumptions

Let’s try to model how long it will take to count to 100 and then to 1,000, by making some simplifying, but moderately realistic, assumptions.

Let’s assume that we can say each single word in a name in 1 second.

This is not exactly correct, because it takes longer to say “nineteen” than it does to say “ten”. But what we are assuming is that it will take twice as long to say “twenty one”, and three times as long to say “one hundred one”.

Note, by the way, that the answer depends on where one lives. First of all, even in English, people in the UK and in Commonwealth countries do not count like people in the United States, and people in Vietnam and Germany count differently again, and from each other. I am assuming US English counting.

Counting to 100

The numbers 1 through 20 all Â take 1 second to say, as do the 7 numbers 30, 40, 50 ,60, 70, 80, and 90, while the remaining 73 numbersÂ up to 100 all take 2 seconds to say.

These are approximations, but they serve us better than assuming all numbers take the same time to say.

So our estimated time to count to 100 is now $20+ 7 + 2\times 73 =173$ seconds.

Of course we can do if faster if we speed it up, but there’s a long way to go to one trillion so let’s keep an even pace. At the end we can think about what would happen if we could say more number words each second.

Notice that 173 seconds is close to the time it would take – 180 seconds – to count 90% of the numbers 1 through 1,00 at 2 seconds each.

Counting to 1,000

With our stated assumptions on how long it takes to say number names, how long will it take us to count to 1,000?

Many of the numbers from 101 through 1,000 will take 4 seconds to say: numbers like 131 (“one hundred thirty one“) and 273 (“two hundred seventy three“).

But there are exceptions.

I tried to take into account all exceptions in counting to 1,00 and, below, in counting to 10,000. To the best of my knowledge I did not omit any exceptions.

Some numbers from 101 through 1,000 will take 2 seconds to say. These are the 9 numbers 200 (“two hundred“), 300, 400, 500, 600, 700, 800 , 900 and 1,000 (“one thousand“).

Some numbers from 101 through 1,000 will take 3 seconds to say. There are a lot more of these.

Between 101 and 199 these are the 27 numbers 101 (“one hundred one“) through 120 (“one hundred twenty“) and 130, 140, 150, 160, 170, 180 ,190.

Similarly between 210 and 299 there are 27 numbers that take 3 seconds to say.

The same goes for 310 to 399, 410 to 499, 510 to 599, 610 to 699, 710 to 799, 8210 to 899 and 910 to 999.

So there are $9\times 27 = 243$ numbers that will take 3 seconds to say.

This leaves 648 numbers between 101 and 1,000 that will take 4 seconds to say.

So the total time to say all the numbers up to 1,000 we estimate as $173+2\times 9+ 3\times 243+4\times 648 =3512$ seconds, which is just under 1 hour.

Notice that this is not far off the number we would get if just assumed we counted 90% of theÂ numbers up to 1,000 at 4 seconds each.

Counting to 10,000

How long will it take us to count to 10,000?

Most numbers will take 6 seconds to say: numbers like 1274 (“one thousand two hundred seventy four“), but again there are exceptions.

Let’s count these exceptions to see how far off would be an estimate of $0.9\times 10,000 \times 6 = 5,400$ seconds.

We already know the exceptions up to 1,000, so let’s look at them from 1,001 on.

There are 9 numbers from 1,001 through 10,000 that require only 2 seconds to say. These are: Â 2,000, 3,000; 4,000; 5,000; 6,000; 7,000; 8,000; 9,000 and 10,000.

There are 252 numbers between 1,001 and 10,000 that require 3 seconds to say. These are 1,001 through 1,020; 1,030; 1,040; 1,050 1,060; 1,070; 1,080; 1,090 and the corresponding numbers in the n,000 range where n=2, 3, …, 9.

There are 648 numbers in the range 1,001 through 10,000 that require 4 seconds to say. These are 1,021 through 1,029; 1,031 through 1,039; … , 1,091 through 1,099 and the corresponding numbers in the $n\times 1,000$ range where $n=2, 3, \ldots, 9$ .

There are $9\times 243=2187$ numbersÂ in the range 1,001 through 10,000 that require 5 seconds to say. These are the numbers $n\times 1,000+m$ where $n=1,2,\ldots 9$ and $1\leq m\leq 999$ is a number that takes 3 seconds to say. Â For each choice of $n=1,2,\ldots 9$ there are 243 of the latter, as we saw in counting up to 1,000.

The remaining 5,913 numbers in the range 1,001 through 10,000 take 6 seconds to say.

So the total time to count to 10,000 is $3512+2\times 9+3\times 252+4\times 648+5\times 2187+ 6\times 5,913 = 53,291$ seconds.

Again, this is close to the time we would take – 54,000 -Â if we counted 90% of the numbers up to 10,000 at 6 seconds each.

An estimate of the time to count to one trillion

Counting all exceptions as we say larger numbers becomes more difficult.

However by now we can see a glimmer of a general pattern: there are many more numbers from 100 billion to one trillion Â than there are from one to 100 billion. In fact there are 9 times as many. So by looking only at numbers from 100 billion to one trillion we are covering 90% of all the numbers from one through one trillion.

Most numbers up to one trillion take 19 seconds to say: numbers like 832, 521,432,987 (“eight hundred thirty two billion, five hundred twenty one million, four hundred thirty two thousand, nine hundred eighty seven“).

Our general observation is that to count up to $10^n$ takes about as long as it would to count 90% of the numbers up to $10^n$ at the typical rate.

If this continues to hold good up to one trillion then we estimate to count to one trillion would take about $0.9\times 19=17.1$ times as long as if we were to count one number per second.

That is, we estimate it would take approximately 542,241 years to count to one trillion.

Dali

What if we could count faster?

Let’s imagine we can say 3 number words each second (as in: “one one thousand”). Still it would take us something like 180,747 years to count to one trillion.

How far could we expect to count in a lifetime?

If we counted from age 5 through 85, 80 years in total , saying one number word each second, with 8 hours a day off Â for sleeping, eating and bathroom breaks, how far could we count in those 4,608,000 seconds? Less than one million?