How to find the sum of digits in 2^n. Where n=0,1,2,3,.....1024
Ex:
2^8 = 256=2+5+6=13.
2^12= 4096=4+0+9+6=19.
How to find the sum of digits in 2^n. Where n=0,1,2,3,.....1024
Ex:
2^8 = 256=2+5+6=13.
2^12= 4096=4+0+9+6=19.
Use repeated modulus and division (by 10) to extract off the digits one-by-one. Put this in a loop.
"Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
-Christopher Hitchens
Don't think C has native data types that can store a 1024-bit integer and do modulus and division.Originally Posted by hk_mp5kpdw
@veera:
Start by reading this: Power of two - Wikipedia, the free encyclopedia. There may be some information you can glean in the "First 96 powers of two" section, were it talks about the last digit or two being periodic. Also, there may be some tricks with logarithms you can use. Those are just ideas, I haven't thought about it enough to have a solution myself. No doubt, however, the purpose of this problem is for you to discover the "trick" to solving this problem yourself. Post up any ideas and information you may have, and we can help you sort it out
Last edited by anduril462; 07-25-2013 at 12:18 PM.
Can you get access to a bignum library: e.g.,
gmp The GNU MP Bignum Library for Linux
C# express for Windows Download | Microsoft Visual Studio 2012
cygwin + gmp + gcc for windows Cygwin for windows
Is this one of the Project Euler or hackathon or whatever classroom-like problems? A priori: There is probably some bit of information (a theorem) in number theory about sequences that provides a shortcut. I do not know it.
Omg, I totally think hk_mp5 did it right!
Literally, this was a question on a job interview I had once. Or rather, it was a screening test.
Basically, divide the number by 10 repeatedly until you only get one left. So for 17, you do 17/10 = 1, just by using ints.
To get the 7, you have to do 17-10 = 7 and then you have the digits 1 and 7.
So for 256, you divide by 10 and get 25. Divide by 10, get 2. Then you do 25-2*10 = 5. Then you do 256 - 200 - 50 = 6 and there you have it, 2, 5 and 6 stored up. I still have the working algorithm on my computer if need be.
Except for the fact that his idea only works on numbers fit in a native C data type (i.e. numbers for which the / and % operators work), which typically limits you to 2^32 or 2^64. The OP needs 2^1024, much, much bigger than any native C data type. That is the simple, intuitive way, just not appropriate for the OP's specific version of this problem.
That works, but it's the long way. You're throwing away digits each time, until you get to the most significant one. Then you have to "recreate" them and work back to the original number. Just strip the least significant digit, add it to digit_sum, and then divide the number by 10. Using your 256 as an example:
Just code that up into a loop and you're good to go, no complicated "reassembly" or multiplying and subtracting.Code:int num = 256; int digit_sum = 0; digit_sum += num % 10; // 256 mod 10 is 6, add that to digit sum num /= 10; // divide by 10, "removing" the 6 and leaving 25 digit_sum += num % 10; // 25 mod 10 is 5, add that to digit_sum num /= 10; // divide by 10, "removing" the 5 and leaving 2 ... // stop when num is 0
As posted by anduril462:
Unless there is some clever algorithm for this (like some type of pattern), it seems that an extended precision divide is needed.
Last edited by rcgldr; 07-25-2013 at 01:55 PM.
Ha! So that's why I didn't get the job :P
Does my physics BS show? Lolololol.
And can't a long double store 2^1024? Oh, it can't. Dang, that's a huge number then. That's like 1<<1023, isn't it? That's over 1000 bits!
Do computers handle those kinds of calculations by solving it in blocks? Like, couldn't you solve a 64 bit operation over a 32 bit processor just by having it run two cycles? You'd evaluate one half with one cycle and then carry over the appropriate stuff and solve over the second half. Wouldn't that basically be how you solve a 1024 bit operation like this?
yes, it can, but it stores it as an approximation, not the actual value. on x86 systems, a long double is 80 or 128 bits long, and therefore can't possibly store the real value of 21024.
edit: actually, it will store it internally as a perfectly precise 21024. when it is translated to decimal format, you lose much of that precision.
Last edited by Elkvis; 07-25-2013 at 02:21 PM.
What can this strange device be?
When I touch it, it gives forth a sound
It's got wires that vibrate and give music
What can this thing be that I found?
> That's like 1<<1023, isn't it? That's over 1000 bits!
Yep, 2^1024 is over 1000 bits. Actually, it's 1024 bits exactly!
> Do computers handle those kinds of calculations by solving it in blocks? Like, couldn't you solve a 64 bit operation over a 32 bit processor just by having it run two cycles? You'd evaluate one half with one cycle and then carry over the appropriate stuff and solve over the second half. Wouldn't that basically be how you solve a 1024 bit operation like this?
For general operations, yes. In fact, I'm pretty sure that's how many (all?) 8 and 16 bit processors did their 32-bit operations. The problem here is, base 2 and base 10 aren't very compatible (the way base 2, 8 and 16 are) since no power of 2 is also a power of 10. The 32 and 64 bit boundaries don't line up well with base 10 numbers, making the modulus stuff tricky.
Mind = blown.
And it all makes sense now. That's tricky, yo.
actually, to represent 21024 precisely, you need 1025 bits, because the most significant bit of a 1024-bit word would be 21023
What can this strange device be?
When I touch it, it gives forth a sound
It's got wires that vibrate and give music
What can this thing be that I found?
Write a function that constructs the positive integer 2N as a string. For N <= 1024, just start with a string "000001" (with sufficient number of leading zeroes to hold the final number), then double it N times.
Because 223 < 107, you know that any N-bit unsigned integer can be represented using 7⌈N/23⌉ digits. (That's math notation. In C, you can just round down and add 1, i.e. N-bit unsigned integer uses at most ((N/23)+1)*7 decimal digits.)
(Or, you can just note that log(21025)/log(10) = 1025 log(2)/log(10) < 1026 log(2)/log(10) < 309, so if you use a 310-char buffer (including the '\0' at end) for 309 digits, you can represent all N = 0..1026.)
Doubling is trivial, especially if you remember long multiplication by hand. I use this pseudocode logic:
If CARRY and TEMP are chars, then the C compiler can optimize the modulo-10 and divide-by-10 expressions extremely well, usually better than the equivalent if-then-else clause.Code:Set CARRY = 0 For each digit D from right to left: TEMP = 2 * D + CARRY Replace digit with TEMP % 10 Set CARRY = TEMP / 10
After you have doubled "1" N times, you have the decimal digits for 2N, and it's trivial to calculate the sum of the decimal digits. (Hint: Since the leading zeroes do not affect the sum, you don't need to avoid them.)
As a comparison, I wrote a 80-line program (not counting empty and comment lines), of which about half were needed to apply the above logic. If computed the sum of decimal digits in 21024 (1375) in about 2 milliseconds.
The algorithm can easily do larger numbers, but it scales roughly O(N2), so it took almost five seconds to sum the decimal digits in 265536 (88261). (230000 took almost exactly a second, and the sum of its decimal digits is 41194).
I do know a few ways to enhance the program for larger N. For example, using multiplications instead of doubling can modify the algorithm to O(N log N), and using decimal digit groups (say, nine digits per 31/32-bit integer) uses less than third the amount of memory. But, since N=1024 takes just two milliseconds on my machine, it's only worthwhile for larger N (which you're not interested in).
None of this requires architecture-dependent code, or any libraries; it's all just plain C.
(The sequence of (sum of decimal digits of 2N, N = 0, 1, 2, 3, ..) is A001370, if you want to check the results from your program.)
Last edited by Nominal Animal; 07-25-2013 at 04:10 PM.
I think there might be a better way based on the following fact (letting s mean the digit sum function) :
E.g, (letting a number stand for two raised to that power) :Code:s(x * y) = s(s(x) * s(y))
Wouldn't that give it a speedy dynamic-programming solution?Code:s(1024) = s(512 * 512) = s(s(512) * s(512)) = s(s(256 * 256) * s(256 * 256)) ...
An alternative is a binary based extended precision divide. Since the divisor is 10, which is less than 16, up to 28 bits per 32 bit integer could be used (need to leave space for the remainder from each divide which is appended to the upper bits of the next integer). The issue here is that it's a double loop, and for the case 2^1024, the outer loop runs 309 times to produce 309 digits, and the inner loop 37 times (ceil(1024./28.)), unless the algorithm is improved to drop leading zeroes in the dividend as it loops.
The decimal string multiply might be a faster method.
