Wikipedia:Reference desk/Archives/Mathematics/2017 June 25

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 25

Calculating Graham's number

Hello everyone. As we all know, to calculate Graham's number, we need to start from 3↑↑↑↑3 whose sum is G1 and then continue to calculate 64 layers all the way to G64 which is the final result of Graham's number. What I wanted to know is that is it possible to calculate from beginning to the final result using a standard calculator or any other viable method? It is also mentioned that "Graham's number is so large that the observable universe is far too small to contain an ordinary digital representation of Graham's number, assuming that each digit occupies one Planck volume, possibly the smallest measurable space". So, is it possible to know the actual number of total digits in the final result (G64) of the Graham's number or it can only be guessed? TheGeneralUser (talk) 00:38, 25 June 2017 (UTC)

The total number of digits (i.e. its logarithm) in Graham's number is itself too big to fit in the observable universe. This implicitly means we cannot calculate it using any method, we would literally run out of room before we even get close.--Jasper Deng (talk) 07:11, 25 June 2017 (UTC)

How many logs of logs of logs of logs ..... of Graham's number would we need to take to get to some reasonably representable number? -- Jack of Oz ^{[pleasantries]} 22:10, 25 June 2017 (UTC)

Even the number of times you need to take the logarithm to get a writeable number is too large to write out. This really makes Graham's number huge. Georgia guy (talk) 22:30, 25 June 2017 (UTC)

Optimal algorithm for lights out puzzle?

I would like to solve the following: https://artofproblemsolving.com/community/q1h564755p3301930 . How can I solve the problem via Gaussian elimination? — Preceding unsigned comment added by 37.219.20.248 (talk) 12:53, 25 June 2017 (UTC)

The problem is not always solvable. If n is a multiple of 2m+1 then usually there is no solution. Exclusive or the n/(2m+1) stretches with each other to give a 2m+1 stretch of 1s and 0s. If the result is not all 1s or 0s there is no solution as all 0s is what would result from a solution and all 1s is what one would get from a switch of a 2m+1 stretch - and it would switch back to all 0s. Dmcq (talk) 11:38, 26 June 2017 (UTC)

In fact you get a similar result if there is a number greater than 1 that divides both n and 2m+1. A stretch of 1 is always all 0 or 1 :) Dmcq (talk) 11:42, 26 June 2017 (UTC)

On the business about Gaussian elimination, try working modulo 2. Then multiplying by 1 is equivalent to selecting a vector and adding is equivalent to exclusive orr'ing values. When the matrix has been reduced to upper triangular form you can remove one bit at a time and know the switches required to do that. When n and 2m+1 have a common factor you can still get a solution if one exists this way. Dmcq (talk) 14:45, 26 June 2017 (UTC)

Does Gaussian elimination returns always the optimal solution? --37.219.20.248 (talk) 14:47, 26 June 2017 (UTC)

Just to be clear, although it's not explicitly stated in the problem, the indices on the lights are supposed to be modulo n, so the operation for i=1 switches light 1 through m+1 and n-m through n-1. (I'm going to go with that since it says the light are in a circle.)

In general you'd use Gaussian elimination for something like this, but I think in this case the special form of the basis allows for a faster approach. Instead of looking at the patterns of lights as a vector space over GF(2), think of it as the ring R=GF(2)[x]/(xⁿ+1). You're trying to an element of R as some multiple of f=(x^k+1)/(x+1), where k=2m+1. In other words you're trying to find x/f for a given x assuming it exists. If k and n are relatively prime then you can use the Euclidean algorithm to find p and q so p(xⁿ+1)+qf=1, and this makes q=f^-1 in R. So x/f is then xq. This should give you O(n log n) time as opposed to O(n³) for Gaussian elimination. Sorry about jumping into ring theory for a problem in linear algebra, but it seemed like the easiest way explain the idea, since trying to talk about it in terms of vectors looked like a lot of reinventing the wheel. --RDBury (talk) 16:27, 26 June 2017 (UTC)

There is just the one solution for every input pattern in terms of which ranges to switch or not. That is assuming you don't go switching the same range more than once which is a bit pointless. Yo can see this as there is the same number of ranges and switches and one can do every pattern. Dmcq (talk) 10:31, 27 June 2017 (UTC)

Maybe I'm confused about the problem, but there are 2ⁿ different patterns of lights and 2ⁿ possible ways to work the switches. You were saying above that some patterns don't have solutions, which would imply that some patterns have multiple solutions. --RDBury (talk) 21:37, 27 June 2017 (UTC)

Sorry I forgot to put in the bit about n and 2m+1 being coprime. Yes most of the cases where they aren't coprime don't have solutions but when they are coprime there is a single solution for every pattern. Dmcq (talk) 21:57, 27 June 2017 (UTC)

Just trying to understand the problem. I think you have n lights in a circle and a group of m lights you toggle. Then to change a single light, you must flip it an odd number of times and all the others even. Example ~ n=5 m=3 lights=abcde. Then flip abc = ABCde, bcd = AbcDe, dea = abcdE has managed to flip a single light with 3 swaps. Therefore in this case any pattern can be brought to 00000 with an upper bound of 3*5 flips. Often far fewer. -- SGBailey (talk) 06:44, 29 June 2017 (UTC)

The upper bound is n as there is no point doing the same flip twice, so here it is 5 not 243. IT has to be at least n because there are 2^n patterns and 2^n combination of flipping or not flipping the different groups. Again assuming the numbers are coprime. Dmcq (talk) 13:07, 29 June 2017 (UTC)

? Sorry - didn't understand that reply. Have I got the question correct (forget any answers for now). -- SGBailey (talk) 16:13, 29 June 2017 (UTC)

Your description of the problem sounded fine to me. I was just saying the actual maximum number of swaps needed for any pattern would be 5 in your example. After getting a pattern one at a time the way you said you can remove a lot of flips that are done twice.. Dmcq (talk) 21:56, 29 June 2017 (UTC)

Understood. -- SGBailey (talk) 06:51, 3 July 2017 (UTC)

What is the base X where the biggest % of the division of the digits possible at this base works?

What is the base X where the biggest % of the division of the digits possible at this base works?

As some example at base 3:
0 in base 3 is not divisible by 0 in base 3
1 in base 3 is not divisible by 0 in base 3
2 in base 3 is not divisible by 0 in base 3
0 in base 3 is divisible by 1 in base 3, the result is 0
1 in base 3 is divisible by 1 in base 3, the result is 1
2 in base 3 is divisible by 1 in base 3, the result is 2
0 in base 3 is divisible by 2 in base 3, the result is 0
1 in base 3 is NOT divisible by 2 in base 3, the result is 0.11111111111111111
2 in base 3 is divisible by 2 in base 3, the result is 1

That means 5 out of 9 divisions are possible, so 55.5555...%

Is there any base that would have a % bigger than 55.55555....% — Preceding unsigned comment added by 179.197.131.18 (talk) 13:49, 25 June 2017 (UTC)

First, there is no such thing as numbers being divisible in a particular base. Here are the first 10 rows and columns of a table of what numbers are divisible by each other:

       0 1 2 3 4 5 6 7 8 9  ...

    0  N Y Y Y Y Y Y Y Y Y  ...
    1  N Y N N N N N N N N  ...
    2  N Y Y N N N N N N N  ...
    3  N Y N Y N N N N N N  ...
    4  N Y Y N Y N N N N N  ...
    5  N Y N N N Y N N N N  ...
    6  N Y Y Y N N Y N N N  ...
    7  N Y N N N N N Y N N  ...
    8  N Y Y N Y N N N Y N  ...
    9  N Y N Y N N N N N Y  ...

    ...  ...  ...  ...  ...

The 5 Y's and 4 N's in the top left 3 rows and columns represent the 5/9 of 179.197's example. Each time we go to a higher base, we add one more row and column at the right, so we take a larger and large square from this infinite table. But notice how all each time we add a column it consists mostly of N's with just two Y's. Even if the rows added at the bottom were all Y's, in the limit the table would approach half Y's and half N's. So if there is any solution better than 5/9 it has to be for a small base. It clearly doesn't occur up to base 10, as you see from the table, so I don't think there is better solution, but I'm not going to try to prove it. — Preceding unsigned comment added by 76.71.5.114 (talk) 00:26, 26 June 2017 (UTC)

Laws about numbers

Some Wikipedia articles taught me that in the real world, numbers that start with 1, 2, or 3 occur the most. Why is this law so natural?? (The first article of this kind I found by looking in the see also section of Significant figures. Georgia guy (talk) 13:55, 25 June 2017 (UTC)

According to the Benford's law article, this is because many natural processes are described by power laws, and a lot of data tends to be distributed approximately uniformly across multiple orders of magnitude. Double sharp (talk) 14:53, 25 June 2017 (UTC)

I would also expect there to be an effect that, if a given quantity only ranges from 1-19, (or 1-199, 1-1999, etc.) then more than half of those numbers start with 1, whereas if it ranges from 1-99 (or 1-999, 1-9999, etc.) the number distributions would be about equal. So, when you average in different ranges, you would tend to get more of the lower numbers at the start. StuRat (talk) 06:03, 26 June 2017 (UTC)

In order for this not to be the case, we would need many quantities to only have the high range, like 80-99 (or 800-999, 8000-9999, etc.), to balance it out. There aren't many quantities I can think of that are like that, although percentage school grades are certainly biased towards the high end. StuRat (talk) 14:13, 26 June 2017 (UTC)