题目80：计算无理平方根小数部分的各位和
Square root digital expansionIt is well known that if the square root of a natural number is not an integer, then it is irrational. The decimal expansion of such square roots is infinite without any repeating pattern at all.
The square root of two is 1.41421356237309504880..., and the digital sum of the first one hundred decimal digits is 475.
For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.
题目：
众所周知，如果一个自然数的平方根不是整数，那么就是无理数。这样的平方根的小数部分是无限并且没有任何重复模式的。
2 的平方根是 1.41421356237309504880..., 小数部分的前一百位和是 475。
对于前一百个自然数，找出其中无理平方根的小数部分前一百位的总和。 本帖最后由 jerryxjr1220 于 2016-10-16 20:40 编辑
要是不知道高精度求解算术平方根的方法，这题算起来会很麻烦，因为计算机rounding很容易出错。
Square roots by subtraction
Frazer Jarvis
When I was at school, my mathematics teacher showed me the following
very strange method to work out square roots, using only subtraction,
which is apparently an old Japanese method. I’ll start by writing down the
algorithm in a fairly formal way, which may, for example, make it easier to
implement on a computer.
Although this method converges much more slowly than Newton’s method
for finding square roots, for example, this method also has its advantages.
Perhaps the main advantage from the computational point of view is that,
when finding square roots of integers, no infinite decimals are involved at any
step, which can cause loss of precision due to rounding errors.
Algorithm to compute the square root of an integer n
Initial step
Let a = 5n (this multiplication by 5 is the only time when an operation other
than addition and subtraction is involved!), and put b = 5.
Repeated steps
(R1) If a ≥ b, replace a with a − b, and add 10 to b.
(R2) If a < b, add two zeroes to the end of a, and add a zero to b just before
the final digit (which will always be ‘5’).
Conclusion
Then the digits of b approach more and more closely the digits of the square
root of n.
1
An example
To illustrate the method, let’s begin to work out the value of the square root
of 2. The initial step sets a = 5 × 2 = 10 and b = 5. So we start with the
pair (a, b) = (10, 5).
Now we perform the repeated steps. As 10 > 5, we must apply R1. We
therefore replace a with a − b, so that now a = 10 − 5 = 5, and add 10 to b,
so that b becomes 15. The new pair is therefore (5, 15).
We apply the rule again. This time, however, a = 5 < 15 = b, and so we
use R2. This rule says: Add two zeroes to the end of a, to make a = 500,
and put a zero before the final digit of b, so that now b = 105. The pair
becomes (500, 105).
Now 500 > 105, so we apply R1, and we replace a by a−b = 500−105 =
395, and add 10 to b, so that b becomes 115. Our pair is then (395, 115).
Repeatedly applying the rules in turn gives:
(10, 5) R1 −→ (5, 15) R2 −→ (500, 105) R1 −→ (395, 115) R1 −→ (280, 125)
R1 −→ (155, 135) R1 −→ (20, 145) R2 −→ (2000, 1405) R1 −→ (595, 1415)
R2 −→ (59500, 14105) R1 −→ (45395, 14115) R1 −→ (31280, 14125)
R1 −→ (17155, 14135) R1 −→ (3020, 14145) R2 −→ (302000, 141405)
R1 −→ (160595, 141415) R1 −→ (19180, 141425) R2 −→ (1918000, 1414205) −→ · · ·
and you can see that the digits of b are settling down to start with 14142 . . ..
Moreover,
√
2 = 1.41421356 . . . .
In fact, the method does not only work for positive integers. The method
works for all positive numbers, even decimals such as 2.71, and even π. In
these cases, rather than add two zeroes at the end, we have to multiply by
100 (which comes to the same thing for integers), i.e., to shift the decimal
point two places to the right. Here’s another example, where we work out
the square root of 2.345. Initially, a = 5 × 2.345 = 11.725, and b = 5. Now
apply the steps as before to get:
(11.725, 5) R1 −→ (6.725, 15) R2 −→ (672.5, 105) R1 −→ (567.5, 115)
R1 −→ (452.5, 125) R1 −→ (327.5, 135) R1 −→ (192.5, 145)
R1 −→ (47.5, 155) R2 −→ (4750, 1505) R1 −→ (3245, 1515)
R1 −→ (1730, 1525) R1 −→ (205, 1535) R2 −→ (20500, 15305)
R1 −→ (5195, 15315) R2 −→ (519500, 153105) −→ · · ·
and the correct value for √
2.345 is 1.53133928 . . ..
2
Although the method works perfectly well for any positive number, it is
usually easiest to begin by multiplying or dividing the given number by 100
as often as is necessary until it lies between 1 and 100. For example, given
the number 23450, we would begin by dividing by 100 twice to get 2.345,
and then continuing as above. Since we have divided by 100 twice, we must
multiply by 10 twice to get the correct square root: thus, the square root of
23450 is 153.133928. . . .
Finally, let’s see how the algorithm copes with a perfect square. Let’s
work out the square root of 16. First, multiply by 5, and set a = 80. As
usual, b = 5. Then, applying our rules gives;
(80, 5) R1 −→ (75, 15) R1 −→ (60, 25) R1 −→ (35, 35)
R1 −→ (0, 45) R2 −→ (0, 405) R2 −→ (0, 4005) R2 −→ (0, 40005)
since multiplying 0 by 100 leaves it unchanged. In practice, one can stop
as soon as a = 0, and identify the square root by removing the final digit
from b.
It is an amusing exercise to program a computer to do this algorithm, at
least if n is an integer, and because only integer additions and subtractions
are used, there are no errors due to floating-point arithmetic. On the other
hand, it is necessary to use more complicated storage techniques (strings or
arrays) to store the values of a and b as they get larger and larger, and the
algorithm will get slower and slower at producing successive digits.
Explanation of the algorithm
It’s a bit tricky to explain that the algorithm does indeed produce the correct
answer. Before we embark on the demonstration, let’s make a couple of
observations.
Note that the number of times rule R1 is applied in between the applications
of rule R2 ought to give the sequence of digits in b. We can check that
all these digits lie between 0 and 9. Indeed, let’s choose a point at which R2
is applied. So we begin with a < b, we change a to 100a, and then subtract
successively 10b − 45 (this is what you get by putting 0 before the final 5 of
b), 10b −35, 10b −25 and so on. We can do no more than 9 of these subtractions;
to subtract 10 times would take away 10 numbers averaging exactly
10b from 100a – i.e., to subtract 100b from 100a, but since a < b, the first
number of the pair would become negative, which is not allowed. It follows
that we can apply rule R1 at most 9 times between any two applications of
rule R2, and so the digits appearing in b really are exactly the number of
times R1 is applied in between applications of R2.
3
As remarked above, we’ll assume that our initial number lies between 1
and 100, so that its square root lies between 1 and 10. Thus we suppose that
b is equal to b0.b1b2b3 . . . , where all of the bi
lie between 0 and 9. Let’s show
that n = b
2
. We shall consider a modified version of the algorithm which
incorporates the decimal point:
Let a = n/2, and put b = 0.5.
Repeated steps
(R10
) If a ≥ b, replace a with a − b, and increase the next-to-last decimal
digit of b by 1;
(R20
) If a < b, add two zeroes to the end of a, divide b by 10, and add a
zero to b just before the final decimal digit (which will always be ‘5’).
Let’s see how this works in the example before, where n = 2. We begin
by setting a = n/2 = 1, and b = 0.5. Next, we run through the steps:
(1, 0.5) R10
−→ (0.5, 1.5) R20
−→ (0.5, 0.105) R10
−→ (0.395, 0.115) R10
−→ (0.280, 0.125)
R10
−→ (0.155, 0.135) R10
−→ (0.020, 0.145) R20
−→ (0.02000, 0.01405)
R10
−→ (0.00595, 0.01415) R20
−→ (0.0059500, 0.0014105)
R10
−→ (0.0045395, 0.0014115) R10
−→ (0.0031280, 0.0014125)
R10
−→ (0.0017155, 0.0014135) R10
−→ (0.0003020, 0.0014145)
R20
−→ (0.000302000, 0.000141405) R10
−→ (0.000160595, 0.000141415)
R10
−→ (0.000019180, 0.000141425) R20
−→ (0.00001918000, 0.00001414205) −→ · · ·
(Note that the numbers which appear are exactly the same as in the earlier
example; we have merely multiplied all of them by a power of 10.)
We begin with a = n/2, and, using rule R10
, we have to subtract various
numbers (which we occasionally make smaller with rule R20
), we eventually
get that the first number in the pair approaches 0. It follows that a is the
sum of all the numbers which we take away from it, to get 0.
Before the first application of R20
, we make b0 applications of rule R10
,
subtracting b0/2 on average each time. The total amount subtracted in these
steps is therefore b
2
0
/2.
Between the first and second applications of R20
, we make b1 applications
of rule R10
, subtracting b0/10 + b1/200 on average each time. The total
amount subtracted in these steps is therefore b0b1.10−1 + b
2
1
.10−2/2.
Between the second and third applications of R20
, we make b2 applications
of rule R10
, subtracting b0/100 + b1/1000 + b2/20000 on average each time.
4
The total amount subtracted in these steps is therefore b0b2.10−2+b1b2.10−3+
b
2
2
.10−4/2.
In general, between the kth and k + 1st applications of R20
, we make bk
applications of rule R10
, subtracting b0.10−k +b1.10−k−1 +· · ·+bk−1.101−2k +
bk.10−2k/2 on average each time. The total amount subtracted in these steps
is therefore b0bk.10−k + b1bk.10−k−1 + · · · + bk−1bk.101−2k + b
2
k
.10−2k/2
But remember that n/2 must be the sum of all the terms we are subtracting.
Thus
n/2 = b
2
0/2
+ b0b1.10−1 + b
2
1
.10−2
/2
+ b0b2.10−2 + b1b2.10−3 + b
2
2
.10−4
/2
+ · · ·
+ b0bk.10−k + b1bk.10−k−1 + · · · + bk−1bk.101−2k + b
2
k
.10−2k
/2
+ · · ·
the total subtracted before the first R20
, between the first and second, between
the second and third, and so on. Note that the coefficient of bibj
is
10−i−j
if i and j are different, and is 10−i−j/2 if i = j. However, if we expand
(b0 + b1.10−1 + b2.10−2 + b3.10−3 + · · ·)
2
,
then the coefficient of bibj
is 2.10−i−j
if i and j are different, and is 10−i−j
if
i = j. It follows that the sum making n/2 above is exactly
(b0 + b1.10−1 + b2.10−2 + b3.10−3 + · · ·)
2
/2,
and so
n = (b0 + b1.10−1 + b2.10−2 + b3.10−3 + · · ·)
2
,
so that
√
n = b0 + b1.10−1 + b2.10−2 + b3.10−3 + · · · ,
and the digits bi coming out of the algorithm are therefore exactly the digits
in the decimal expansion of √
n, as required.
Frazer Jarvis is a member of the Department of Pure Mathematics
at the University of Sheffield, and his research interests are
centred on algebraic number theory. Outside mathematics, he is
a keen pianist and sings with the Sheffield Philharmonic Chorus. 答案：40886
import math
def count(n):
limit=math.pow(10,102)
a=n*5
b=5
while b<limit:
if a>=b:
a=a-b
b=b+10
else:
a=a*100
if b!= 5:
b=(b-5)*10+5
b_str=str(b)
return b_str[:-3]
def digitalcount(s):
ans=0
c=0
for i in range(0,len(s)):
tmp=int(s)-int('0')
ans=ans+tmp
c=c+1
return ans
ans = 0
j=1
for i in range(1,101):
if j*j==i:
j=j+1
continue
a=digitalcount(count(i))
ans=ans+a
print('ans = ',ans) 另外还有个python库，计算高精度小数应该很好用
“decimal”
from decimal import *
getcontext().prec = 102
summ = 0
for i in range(1,100):
r = Decimal(i).sqrt()
if i not in :
d = str(r)+str(r)
t = 0
for j in d:
t += int(j)
summ += t
print(summ) # encoding:utf-8
# 计算高精度平方根
from time import time
limit = 10e101
def squre(n):
a, b = 5 * n, 5
while b < limit:
if a >= b:
a -= b
b += 10
else:
a *= 100
b = b // 10 * 100 + b % 10
return sum(int(i) for i in str(b)[:-3])
def euler080(N=100):
sum = 0
for n in ]:
sum += squre(n)
print(sum)
if __name__ == '__main__':
start = time()
euler080()
print('cost %.6f sec' % (time() - start))
40886
cost 0.028003 sec
学习三楼，感谢老大~~ 用的matlab
小数部分前100位和为
s =
40727
时间已过 2.370446 秒。
>> 用了一下楼上的方法，在matlab里就是灾难，收敛太慢了
40886
时间已过 152.175905 秒。
>> 应用大数库mpir（或gmp），非常容易得到：
/*
答案：40886
*/
#include <iostream>
#include <algorithm>
#include <mpir.h>
#include <cstring>
using namespace std;
int sq = { 1,4,9,16,25,36,49,64,81,100 };
int main(void)
{
mpf_t f;
mpf_init2(f, 1024);
char str;
int nS = 0;
long int k = 0;
for (int i = 1; i <= 100; ++i)
{
if (binary_search(sq, sq + 10, i))
continue;
memset(str, 0, sizeof(str));
mpf_sqrt_ui(f, i);
mpf_get_str(str, &k, 10, 126, f);
for (int i = 0; i < 100; ++i)
nS += int(str - '0');
}
mpf_clear(f);
cout << nS << endl;
return 0;
}
页:
[1]