[unreality]

"We should just make base-10 computers," Bob commented to his friend Randy. "Rather than old base-2, which they only made because they used on/off vacuum tubes. We have the technology today to build faster computers... think of a base-10 computer! It would be five times faster than a base-2 computer - think about it. What could take up a bazillion digits in base 2 - or should I say bits, of 0 or 1, would take up much less in base-10. Five times less digits, five times more efficient!"

"That's not necessarily true," mused Randy, scratching his chin. "We're defining Base Efficiency as this, where x is the number to be compared, y is the larger base and z is the smaller base: "

B_ef(x) in y|z = [digits of x in base z] / [digits of x in base y]

For example, 5 in base 10 takes up 1 digit ("5") whereas, in base 2, it takes up three digits ("101"). Thus:

B_ef(5) in 10|2 = 3/1 = 3

"That's not 5x the storage efficiency," Randy added. "That's only three. Look at 10, that's 4/2, or 2. One is only 1/1! No, I think the average overall efficiency of base 10 compared to base 2 is...."

What does Randy say next? Why? Also, what's the largest efficiency you can get in 10|2, and what number(s) give you that efficiency?

Use spoilers and show your work

[unreality]

Thanks for doing that!!!

It's got to converge to 3.219... (log base 2 of 10). What else would it be doing? At 80 million iterations it's pretty much there. It must have gone over somehow? But the log's convergence so far doesn't jump over and below, over and below, etc, logarithms don't do that and all of our tests seem to follow the pattern of approaching slowly from below... yet it's gone over? Is the limit possibly infinity, just very slowly? I'm so confused now But 3.22 is so close that it's tantalizing, even if it's over ;D

the question is, why? I'm trying to think of a way to turn that equation in post 5 into some sort of recursive pattern using the properties of logarithms, but no luck so far

Edited October 16, 2008 by unreality

[Guest]

I think it oscillates. At 9,999,999 its at 3.24033. Which actually makes sense. It goes through streaks of a single ratio, only changing at powers of 2 and 10. These periods also get longer the farther you go, influencing the average more. Mathematically it makes sense that it would converge to log base 2 of 10. So I think it will converge there, just very slowly.

[Guest]

Awesome! Thanks for writing that program, I never got around to it. <_< And it does make sense that it would oscillate, but ultimately converge to log base 2 of 10. However, (and I may be mistaken here), isn't the log base 2 of 10 3.321928095?

[unreality]

Yes, that's correct.... which is why it's strange that it's going over. Maybe that's not the convergent? Maybe it doesn't converge at all? It might "make sense" but I'm not sure if the overall formula would be that simple... hmmm...

[Guest]

You could be right, it might not converge at all. Or it might oscillate between a small range of values...hmmmmmmmmm

[unreality]

This is bugging me, though the original equation [post 5] is hard to work with because of the ceiling function. To look at it, I think we need to look at it as digits divided by digits (the very basic definition), and see if that leads to an overall pattern... hmmm... if the efficiency is represented as:

B_ef(x) = a/b = c

When a power of y is hit by x (y>z remember, and y & z are the two bases), b goes up by 1. When a power of z is hit by x, a goes up by 1.

But the overall effect on c isn't obvious yet. I'm in a hurry so I can't think straight, when I have more time I'll think it over

[Guest]

Well, what we're trying to figure out is on average, how many times a increases before b increases by 1, right?

[unreality]

is there a definition of a "least common power" rather than "least common multiple"? Is such a thing even possible, other than x⁰ = 1 = y⁰, which must be excluded

Is there any power of 2 that equals a power of 3? (other than 1 of course)

[Guest]

is there a definition of a "least common power" rather than "least common multiple"? Is such a thing even possible, other than x⁰ = 1 = y⁰, which must be excluded

Is there any power of 2 that equals a power of 3? (other than 1 of course)

Alright, no one has been on this in about 3 months, but I was just thinking about it the other day and thought I would check on it.

In response to your question, unreality, there is no power of 2 that equals a power of 3 other than one.

I think we agree that it seems like it should oscillate slightly around log base 2 of 10, which equals 3.32193. But it would be nice to check this, does anyone know how to check it up to, say, a billion, without sacrificing accuracy? Honestly I do not- I might attempt to write it in excel or C++ (although I just reinstalled my OS so I have neither excel or a compiler currently on my computer).

Any thoughts? Anyone else still reading this?

[Guest]

Alright, no one has been on this in about 3 months, but I was just thinking about it the other day and thought I would check on it.

In response to your question, unreality, there is no power of 2 that equals a power of 3 other than one.

I think we agree that it seems like it should oscillate slightly around log base 2 of 10, which equals 3.32193. But it would be nice to check this, does anyone know how to check it up to, say, a billion, without sacrificing accuracy? Honestly I do not- I might attempt to write it in excel or C++ (although I just reinstalled my OS so I have neither excel or a compiler currently on my computer).

Any thoughts? Anyone else still reading this?

Here are samples at the lower and upper bounds of a 1000-digit base 2 number per OpenOffice Calc.

2^999 = 5.36E+300 ; log10(5.36E+300) = 300.73 ; 1000 / 300.73 = 3.32525334823560

2^1000-1 = 1.07E+301 ; log10(1.07E+301) = 301.03 ; 1000 / 301.03 = 3.32192809488736

The scientific notation made it easy to see the simple ratio of binary digits to decimal digits.

[Guest]

Here are samples at the lower and upper bounds of a 1000-digit base 2 number per OpenOffice Calc.

2^999 = 5.36E+300 ; log10(5.36E+300) = 300.73 ; 1000 / 300.73 = 3.32525334823560

2^1000-1 = 1.07E+301 ; log10(1.07E+301) = 301.03 ; 1000 / 301.03 = 3.32192809488736

The scientific notation made it easy to see the simple ratio of binary digits to decimal digits.

Wow! That's awesome! Thanks for doing that.

So we can safely say that it converges somewhere between 3.3219 and 3.3253. And as the log base 2 of 10 is 3.3219 that sounds good!

[unreality]

I was actually going to post recently... and there ARE other numbers that share powers, although admittedly they are powers of each other

2^4 = 4^2

works with -2 and -4 as well. In fact many of the lower powers of 2 are very linked with their counterparts... 2^3 = 3^2 - 1, etc. Anyway this is deviating so much from the actual problem I'll stop lol. On topic now:

~~~

if we ignore the brackets around the original equation:

B_ef(x) in y|z = [log_zx] / [log_yx]

and think of a graph of the function

f(x) = log₂x / log₁₀x

you could rewrite it entirely in log base 10 form (just "log" without a subscript) as:

(log(x)/log(2))/log(x)

ie,

log₂x / log₁₀x

=

1 / log₁₀2

regardless of x

this is 3.321928095

which is also equal to log₂(10) because that can be written in log base ten as log(10)/log(2) ... but log(10) = 1, so it simplifies to 1 / log(2)

ie,

log₂(10) = 1 / log₁₀(2) = 3.321928095

so if we ignore the brackets, the equation in post #5 will ALWAYS be that exact number. The brackets just add on a bit of decimal (the range of addition is from 0 to 1, so as the numbers get very big, their logarithms get big, and big enough for the ceiling function to become inconsequential on the overall effect)

So... the limit of the equation approaches 1/log(2) or log base 2 of 10... so does that mean the average of values up to that point approaches the same limit? Your computer programs have been calculating the AVERAGE (ie, sum of all values up to a result dividing by the total number of values summed) rather than the equation for a single result, right?

I'm not that well versed in calculus yet, but it seems to me we could use an integral of some sort to solve this. Or maybe there's a simple formula with the manipulation of limits that can solve it. Is it strange, or commonplace, for the limit of an equation as x approaches infinity to be the same as the average of all the values of x as x goes to infinity?

[Guest]

I was actually going to post recently... and there ARE other numbers that share powers, although admittedly they are powers of each other

2^4 = 4^2

works with -2 and -4 as well. In fact many of the lower powers of 2 are very linked with their counterparts... 2^3 = 3^2 - 1, etc. Anyway this is deviating so much from the actual problem I'll stop lol. On topic now:

~~~

if we ignore the brackets around the original equation:

B_ef(x) in y|z = [log_zx] / [log_yx]

and think of a graph of the function

f(x) = log₂x / log₁₀x

you could rewrite it entirely in log base 10 form (just "log" without a subscript) as:

(log(x)/log(2))/log(x)

ie,

log₂x / log₁₀x

=

1 / log₁₀2

regardless of x

this is 3.321928095

which is also equal to log₂(10) because that can be written in log base ten as log(10)/log(2) ... but log(10) = 1, so it simplifies to 1 / log(2)

ie,

log₂(10) = 1 / log₁₀(2) = 3.321928095

so if we ignore the brackets, the equation in post #5 will ALWAYS be that exact number. The brackets just add on a bit of decimal (the range of addition is from 0 to 1, so as the numbers get very big, their logarithms get big, and big enough for the ceiling function to become inconsequential on the overall effect)

So... the limit of the equation approaches 1/log(2) or log base 2 of 10... so does that mean the average of values up to that point approaches the same limit? Your computer programs have been calculating the AVERAGE (ie, sum of all values up to a result dividing by the total number of values summed) rather than the equation for a single result, right?

I'm not that well versed in calculus yet, but it seems to me we could use an integral of some sort to solve this. Or maybe there's a simple formula with the manipulation of limits that can solve it. Is it strange, or commonplace, for the limit of an equation as x approaches infinity to be the same as the average of all the values of x as x goes to infinity?

Ah, excuse me with my mistake about numbers sharing certain powers. For some reason I was thinking prime numbers, maybe just because you listed 2 and 3 as examples.

I've only taken 2 years of calc so far, which isn't much I know, and an integral would probably be useful in this situation. Or probably the average value theorem or whatever it's called. The one that's (f(b)-f(a))/(b-a)

I'll get to work on that and post if I come up with anything.

As a side note, if we agree that the limit as F(x) approaches infinity is 3.3219..... then the ultimate average of the function should definitely turn out to be that. Because, say you pick the number 10 million and the value of the function is very close to 3.32. Now considering ALL the numbers from 10 million to 100 trillion, all their values are going to be right around 3.32 as well (with some minor oscillations obviously) but the point is that the infinite number of values will indeed cause the average of the function to balance out to 3.32.

I'll still work on that integral though.

[Guest]

Ok so I just wrote in the function on my TI-83 plus and this is what it looks like:

Y= (iPart(log(X)/log(2) + 1)) / (iPart(log(X) + 1))

Not very complicated actually. For anyone unfamiliar with the functions on the TI-83 I can explain.

iPart means integer part. So if you have the 2.345, this would be 2. This means that for the first half of the function, it takes the integer part of the log base 2 of the number, and adds 1 to it. This is equivalent to the number of digits in that number in base 2. Suppose X=10. Log base 2 of 10 is 3.32, so the function takes the integer (3) and adds 1 to it, which equals 4. And indeed, 10 in base 2 is 1010, which has 4 digits.

Suppose X=16. Log base 2 of 16 is 4, so the function takes the integer (4) and adds 1 to is, equaling 5. And 16 in base 2 is 10000, which has 5 digits.

And the second part of the function (after the division sign) counts the number of digits in base 10. If X=99, the log is 1.99, the integer part is 1, and adding 1 to that totals 2, which is of course the number of digits in 99 in base 10.

So as you can see this function develops the ratio of digits in a number- in base 2 versus base 10.

The problem? TI-83's are immensely slow and inaccurate for functions like this. I just tried to take the integral from 1 to 500 and it could not manage it in a solid minute (perhaps if I had given it more time it could have) but regardless it can not handle the integral from 1 to 50 million or 50 trillion or whatever we need.

And also, this function can obviously not be integrated by hand.

So.........anyone know a way to translate that function into a function on excel? I never use excel but I hear it does some wonderful things. Or maybe this function could be plugged into OpenOffice Calc?

[unreality]

Yeah I was thinking that, as it stretches out to infinity the convergence rates flattens out until itself is 3.32, the average is 3.32, the average of the average, etc. It just takes longer for each successive average because an infininte infinity more is needed to overcome the more outlying values in the beginning

Anyway, I think I sufficiently explained why the value itself approaches log base 2 of 10, and I think we can think informally how the average must approach that same value, but it'd put the final gift wrapping on if we can do it formally with limits or integrals or whatever

[Guest]

Agreed! It's fantastic that we have confirmed an answer, but I would like to prove it with an integral.

So, do you know how to make an integral in OpenOffice Calc? Because I wrote the function in it:

=(INT(LOG(A2;2))+1)/(INT(LOG10(A2))+1)

But now I need to take the integral of it and I'm not sure if OpenOffice can do that.

[unreality]

I'm not familiar with OpenOfficeCalc, but why not try Mathematica?

Online Integrator

this is how to type it in. For the base efficiency of b10 over b2 for a single value of x, it would be

Ceiling[Log[2,x]]/Ceiling[Log[10,x]]

not sure how exactly you would use integrals (as I said I dont know much calc yet) to find the average for all values of x

I'm sure as x -> ∞ in that, the ceilings eventually dont matter so it becomes log₂x / log₁₀x = 1 / log₁₀2 or log₂10, both of which equal 3.321928095

but we're more interested in the average of all values of x... hmmm...

edit: did a google search, found this, will read it and get back to you

Edited January 17, 2009 by unreality

[unreality]

edit2: after reading it, it looks like it's for the defininte integral of a set range of values... we don't have a set range, we want overall average. Although we could figure it out for continually expanding set ranges, turn that into a function, and take the limit.

But if we wanted to take the average from, say, 0 to 1 million, we would multiply one millionth by an integral from 0 to million of our equation( Ceiling[Log[2,x]]/Ceiling[Log[10,x]] ) ... but if you think about it, the definite integral sums up the area underenath, and multiplying by the millionth reduces it to the average value from a million values... so this is just a fancy way of saying "take the average of all values from 0 to 1 million"

BUT, even though I have no calc training yet, you would just do this then:

take the integral from 0 to infinity (I've seen pictures of that, I know it's possible) of our function. Then I don't know if we multiply by 1/inf, ie, infintesimal, or what

[unreality]

Actually, now that I think about it, instead of the ceiling function, we need to use the floor function and then add 1. The only numbers this makes a difference for are perfect powers of 2 or perfect powers of 10. Ie, in base 2, the number 8 (1000) is 4 digits, not 3. For all other numbers there is no difference

Again, I don't expect this to have much impact as x->∞, and the limit should still drop off any ceiling/floor oddities leaving the reduction to log base 2 of 10. So we can say with certainty that the base efficiency for a number approaches 3.322 as x approaches infinity, and then that would be true of the average as well

ie,

for x=10,000

log₂10,000 ~= 13.288

log₁₀10,000 = 4

13.288/4 = 3.322 or so

So yeah I think this riddle is solved

but let me just state it formally from the beginning...

* the number of digits of number x in base y is logarithm-base-y of x, floored for the integer part, then added with 1

* to compare the number of digits required in base y and in base z to represent the number x, we just find the digits for each and then divide. To find the efficiency of base 10 over base 2, we do the number of digits it takes in base 2 and divide by the number of digits in base 10 [it's flipped cuz base 2 requires more digits than base 10]

* as we get larger, the floor+1 part of the function becomes more and more inconsequential as it's just adding/subtracting tiny parts of a number, between 0 and 1, to both the numerator and denomenator, thus in the end we can drop it out of our final calculations

* thus the overall, limit, and average, etc, of the function for the efficiency of base y over base z can be represented by this simple equation: (where z is going to be our smaller base, y the larger one)

log_zx / log_yx

recall the change of base formula, where 'b' is ANY base:

log_ac = log_bc / log_ba

so we have this:

log_zx / log_yx

= ( log_xx / log_xz ) / ( log_xx / log_xy )

(a/b) / (c/d) = (a/b)*(d/c) = ad/bc

so

= (log_xx * log_xy) / (log_xz * log_xx)

the log_xx 's cancel out, leaving:

log_xy / log_xz

remember the change of base formula again:

log_bc / log_ba = log_ac

where b is ANY base

thus

log_xy / log_xz = log_zy

that's right That's our final result:

log_zy

So the efficiency of base 10 over base 2 is log base 2 of 10 or 3.322

Problem solved, gentlemen

^i've always wanted to say that ;D

[unreality]

it may be notable that the efficiency of hexadecimal over binary is exactly 4

~~~

anyway, I thought of how it was interesting that at first we were thinking it took a while to converge... anyway, so I made a function g(x) to graph the deviation from the average value (3.321928095)

[x] = floor function, ie, take the integer part


		   [log[sub]z[/sub]x]+1

g(x) = ----------------------------   -   log[sub]z[/sub]y

		   [log[sub]y[/sub]x]+1

on my calculator for z=2 and y=10, where log(x) is in base 10, it was:

(iPart(log(x)/log(2))+1)/(iPart(log(x))+1)-1/log(2)

the resulting graph was pretty interesting looking, though not revealing for the smaller numbers. But the calculator has a table feature where you can see the result for large numbers if you want, and it oscillated in a few places, but I went into extremely high numbers and it got smaller and smaller. The deviation gets close to 0, and is within one for almost all numbers. Because the deviation jumps higher at each power of 10 and then gets a little lower and jumps back up, a bit after 10,000 it will always be no more than .5 less than the constant.

Anyway just thought that was interesting. I think we've solved this problem in its entirety, but it was a good one while it lasted

[Guest]

but let me just state it formally from the beginning...

* the number of digits of number x in base y is logarithm-base-y of x, floored for the integer part, then added with 1

* to compare the number of digits required in base y and in base z to represent the number x, we just find the digits for each and then divide. To find the efficiency of base 10 over base 2, we do the number of digits it takes in base 2 and divide by the number of digits in base 10 [it's flipped cuz base 2 requires more digits than base 10]

* as we get larger, the floor+1 part of the function becomes more and more inconsequential as it's just adding/subtracting tiny parts of a number, between 0 and 1, to both the numerator and denomenator, thus in the end we can drop it out of our final calculations

* thus the overall, limit, and average, etc, of the function for the efficiency of base y over base z can be represented by this simple equation: (where z is going to be our smaller base, y the larger one)

log_zx / log_yx

recall the change of base formula, where 'b' is ANY base:

log_ac = log_bc / log_ba

so we have this:

log_zx / log_yx

= ( log_xx / log_xz ) / ( log_xx / log_xy )

(a/b) / (c/d) = (a/b)*(d/c) = ad/bc

so

= (log_xx * log_xy) / (log_xz * log_xx)

the log_xx 's cancel out, leaving:

log_xy / log_xz

remember the change of base formula again:

log_bc / log_ba = log_ac

where b is ANY base

thus

log_xy / log_xz = log_zy

that's right That's our final result:

log_zy

So the efficiency of base 10 over base 2 is log base 2 of 10 or 3.322

Problem solved, gentlemen

^i've always wanted to say that ;D

A most excellent summary. That was a very awesome problem.

[unreality]

I'm revitalizing this topic because of something interesting I just found.

The number we've been talking about, log-base-2 of 10... log₂(10) or 1/log₁₀(2), etc (it equals 3.321928095) is veeeery close to equaling this:

2^(√3)

that, is, 2 to the power of the square root of 3

I've been messing with it but no obvious reasons why it should be so other than coincidence of the closeness of the numbers (the equalization is not exact, there is a small difference in the realm of 10^-6 or so between them)

[Guest]

I'm revitalizing this topic because of something interesting I just found.

The number we've been talking about, log-base-2 of 10... log₂(10) or 1/log₁₀(2), etc (it equals 3.321928095) is veeeery close to equaling this:

2^(√3)

that, is, 2 to the power of the square root of 3

I've been messing with it but no obvious reasons why it should be so other than coincidence of the closeness of the numbers (the equalization is not exact, there is a small difference in the realm of 10^-6 or so between them)

Um.... no idea about why that would be. :shrug:

But of course that brings up the possibility that perhaps the efficiency averaged out to 2^(√3) :whistling:

I doubt it though. Probably just a coincidence...who knows though?

And where are all the smilies? :verymad: Haha

[unreality]

Yeah, I'm sure it's just a coincidence Still cool though. And we pretty much proved that it eventually averaged out to log₂10 but you never know... ;D

Edited June 8, 2009 by unreality