Big Number Problems
Kimota94 mentioned that the last math problem I posted was easy. He got it right, so I guess for him it was easy as everyone knows an easy question is one that you know the answer to.
Here are two 'easy' ones (Easy in that it only requires public school level arithmetic to solve).
1) What is the sum of all the digits used in writing out all the numbers from 1 to 1,000,000,000?
2) What is the product of 666...666 * 333...333 (where each number has 666 digits, the first being all sixes, the second being all threes).
12 comments:
I think the first one is solved the Gaussian way by calculating the sum of the arithmetic series:
1/2*(1,000,000,000)*(1,000,000,000+1) =
(500,000,000)*(1,000,000,001) =
500,000,000,500,000,000 =
5*10^17 + 5*10^8
If the answer was a trick, then it could also be 9/2*(10) = 9*5 = 45
2) No clue.
1. I might be 100% wrong.. but heres a shot anyways.
Say X= number of digits in numbers from 1 .. 1000000000.
(ok this cant be too hard to calculate, using combination permutations)
total sum = X * (1+2+3+4+5+6+7+8+9+0)/10
(this is based on that there are the equal numbers of 1,2,3,4,etc in all the digits)
2. 22..2221777...778
with 2 and 7 repeated 665 times.
I'm not even going to tackle # 2, but # 1 seems like it should be deducible. Here's my crack at it (having not read cjg's or Vish's).
If you'd asked the same question, but from 1 to 9, the answer would be 45 (the sum of the first 9 positive integers).
If you'd asked about 1 to 99, then the answer would be 900. Each of the 2 digits ranges from 1 to 9 (really, 0 to 9, but 0 doesn't change the total so I'm discounting it) 10 times, holding each value once for each possible value of the OTHER digit. So the sum of the digits would be 450 + 450, or 900. Extending the range to be 1 to 100 would simply change the answer to 901.
Similarly, if the question asked about 1 to 999, the answer would be 4500 + 4500 + 4500, or 13,500.
Again, extending the range to include 100 would add 1 to the total. So, as a formula:
total = n(45*10**n-1) + 1 where the ending value of the range = 10**n
In this case, n = 9, so the total would be 9(45*10**8) + 1, or
9(4,500,000,000) + 1, or
40,500,000,001
That looks like way too strange an answer to be right, but it made sense to me as I was going through it.
Simplifying the problem, I will count from 0-999,999 since the sum of digits of 1MM is 1. I will just add 1 after my calculations.
Using induction and breaking down this problem as the sum of digits with each magnitude of numbers. Digit one shall refer to the most significant digit.
One Digit 0-9:
n(n+1)/2 = 45; //n=9
Two Digits 0-99:
Digit one:
n(n+1)/2 = 45
Digit two: From 10-99 each SECOND digit occurs 9 times and using this fact
(1*9) + (2*9) + ... + (9*9)
= n(n+1)/2 * 9
= 45 * 9 = 405
Adding single digit count yields 405+45 = 450
Hence, this formula should calculate sum
for(i=0->n)
{
SUM += 45 * 9^i;
}
SUM++;
Im too lazy to actually do the calculation, but is this right? Are you going to post the answer?
Well... It seems only appropriate that I put a numeric answer and apparently its 1B not 1M... So as N=8 the answer is 2179240246
Is this right?
Alright, I decided to take a crack at # 2 after all.
6*3 = 18
66*33 = (180+18) + (1800+180), or
1800 + 2*180 + 18
666*333 = (1800+180+18) + (18000+1800+180) + (180000+18000+1800), or
180000 + 2*18000 + 3*1800 + 2*180 + 18
Extrapolating from the pattern seen in the first 3 examples, the answer would be:
18*10**1330 +
2*(18*10**1329) +
3*(18*10**1328) +
... +
665*(18*10**666) +
666*(18*10**665) +
665*(18*10**664) +
664*(18*10**663) +
... +
2(18*10) +
18
Or something like that...
Ohh. I missed part 2. SO MUCH FUN!! Refactoring would yield 2*(333...333)^2. Computing from base case yields the following pattern
2...207...78 and the answer would be 2..207..70 where 2 and 7 occurs 665 times.
Opps type on last comment. Answer: 2..207..78 where 2 and 7 occurs 665 times.
Clearly I missed the boat on # 2 as both Vish and Ron saw a way to calculate the answer directly, albeit with a wicked number of repeating digits! Way to go, guys!
Congrats to Vish who got #2 right and to Kimota who got #1.
Way to go guys...and congrats to anyone who attempted it.
math geeks across the world: unite!
Sounds like somebody's just a wee bit jealous, doesn't it?
Post a Comment