Wikipedia:Reference desk/Archives/Mathematics/2011 December 29

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

December 29

15 Coin game

What is the name of the game that uses 15 coins in 5 horizontal rows with 1 coin in the top row incrementing by one in each row to 5 coins in the bottom row. Each of two players take turns and in turn is allowed to remove as many coins as desired from any single (horizontal) row. The player forced to remove the last coin loses. Thanks, hydnjo (talk) 05:17, 29 December 2011 (UTC)

It's a Nim variation. PrimeHunter (talk) 05:30, 29 December 2011 (UTC)

Arghh, of course. Thanks PH. hydnjo (talk) 05:59, 29 December 2011 (UTC)

Order statistics

Is there a nice "physical" interpretation for order statistics of fractional order? For example, I keep encountering beta distributions involving parameters with close to half integer and integer +- 1/3. --HappyCamper 07:24, 29 December 2011 (UTC)

Sum of digits of 2^1000

I'm trying to solve this problem which is to sum the digits in 2^1000. The obvious thing seems to be to just brute force it by working out 2^1000 (using big ints) and then suming the digits. However, I feel that that would be missing the point and think there may be a more clever way of doing it; perhaps based on the digits behaving in a predictable way every time they are multiplied by 2. I'd rather not get the full answer but if you could tell me whether I'm right or give me a hint otherwise. I can see for example that every digit is doubled and then if it is greater than 10 you keep the least significant digit and add the most significant to the next one after it is doubled but then with everything you need to keep track of I feel it looks a lot similar to what would be done simply by using big ints --178.208.197.58 (talk) 15:46, 29 December 2011 (UTC)

This was first posted to Wikipedia:Reference desk/Computing#Sum of digits of 2^1000. PrimeHunter (talk) 15:49, 29 December 2011 (UTC)

Note that $2=10^{0.301}$, so $2^{1000}=(10^{0.301})^{1000}=10^{0.301*1000}=10^{301}$, so $2^{1000}$ must have 302 digits. 84.228.166.2 (talk) 17:38, 29 December 2011 (UTC)

...if written in decimal, of course. CiaPan (talk) 17:51, 29 December 2011 (UTC)

And more precisely: $\log 2\approx 0.30103,$ so $2^{1000}\approx \left(10^{0.30103}\right)^{1000}=10^{0.30103\times 1000}=10^{301.03}\approx 1.07\times 10^{301}$, so $2^{1000}$ has 1 + 301 = 302 digits in decimal notation. --CiaPan (talk) 17:58, 29 December 2011 (UTC)

The mean value of a random digit is (0+1+2+3+4+5+6+7+8+9)/10=4.5. The mean value of the sum of 302 random digits is 302×4.5=1359. The mean value of the square of a random digit is (0+1+4+9+16+25+36+49+64+81)/10=28.5. The variance is 28.5−4.5²=28.5−20.25=8.25. The variance of the sum of 302 random digits is 302×8.25=2491.5. The standard deviation is the square root of the variance. So the sum of the digits of 2¹⁰⁰⁰ is 1359±50. Bo Jacoby (talk) 20:00, 29 December 2011 (UTC).

That's quite close to the actual answer which is 1366... but what I think the OP's more interested in is an algorithm, or some mathematical property between binary to decimal conversion that doesn't require big integers. Shadowjams (talk) 22:17, 29 December 2011 (UTC)

Actually, the math part of this question is whether there's some known properties of the sequence of decimal digit sum of numbers 2ⁿ, or in other words, whether the digit sum of doubled numbers follows a set pattern, or is it irrational (on a graph it looks irrational). The first few numbers are 1 2 4 8 7 5 10 11 13 8 7 14 19 20 22 26 25 14 19 29 31 26 25 41 37 29 40 35 43 41 37 47 58 62 61 59 64 56 67 71 61 50 46 56 58 62 70 68... I searched the OEIS for that string and nothing came up, which suggests to me it's not a common conversion. That said, I'm always amazed at the Math desk so maybe someone knows something about it.

Unless there's some programmer's trick (still waiting for that programmer that knows it to answer), all the straightforward methods seem to either directly rely on big int, or somehow duplicate its logic. If you could calculate 2ⁿ incrementally in decimal digits, then you could do this without ever outright using a bigint... That might work... maybe someone can expand on that idea.

I also got the whole implementation down to 50 characters in perl (commit to the code: a10dcea4a0e707a77bd9b7cf80b47ed4). Golf anyone? Shadowjams (talk) 23:04, 29 December 2011 (UTC)

Here is is in 27 characters in mathematica: +##&@@IntegerDigits[2^1000]. Sławomir Biały (talk) 00:18, 31 December 2011 (UTC)

I thought we shouldn't do homework so I didn't post the relevant OEIS link earlier but the answer has now been posted so here it is: OEIS:A001370. It links a table going to 10000. Perhaps you didn't put your sequence in quotes and overlooked the right result among other hits. There is no easy algorithm with manual computation. It would be a big work with any algorithm. PrimeHunter (talk) 01:27, 30 December 2011 (UTC)

I didn't realize OEIS was so picky about quotes. I don't think this is a homework question (particularly given the time of year) and even if it is, 1366 isn't the answer, the program to find it is. I'm pretty confident the OP knows how to solve the problem (although I didn't post my perl code for the same reason... just in case). I find the underlying question interesting though, and I'm curious if anyone has any insight on that part. (I'm not the OP btw) Shadowjams (talk) 06:13, 30 December 2011 (UTC)

I wonder if the original poster got the question wrong and was being asked for the sum if you kept on adding the digits together till you just got one digit, i.e. the digital root rather than the digital sum. Dmcq (talk) 09:45, 30 December 2011 (UTC)

Elementary calculation modulo 9: 2¹⁰⁰⁰ = 2^6×166+4 = (2⁶)¹⁶⁶×2⁴ = 64¹⁶⁶×16 == 1¹⁶⁶×7 = 7 (mod 9). So the sum of the digits in 2¹⁰⁰⁰ is of the form 7+9n where the integer n ≈ (1359±50−7)/9 = 150.22±5.55 ≈ 150±5. Actually n=151 because 7+9×151=1366. Bo Jacoby (talk) 11:43, 30 December 2011 (UTC).

Excuse my ignorance.... I'm with you up to 64¹⁶⁶×16, but I don't understand the next operation that goes to 1¹⁶⁶×7. Shadowjams (talk) 23:15, 30 December 2011 (UTC)

See modular arithmetic. 64=9×7+1 and 16=9×1+7. This means that 64 is congruent with 1 (modulo 9), and 16 is congruent with 7 modulo 9. And so 64¹⁶⁶×16 is congruent with 1¹⁶⁶×7 (modulo 9). Bo Jacoby (talk) 23:37, 30 December 2011 (UTC).

I'm not the OP, but the question is Euler problem 16 so I think the actual sum of the digits is desired, not the digital root. 67.122.210.96 (talk) 09:08, 5 January 2012 (UTC)