For the first 100 natural numbers, find the digital sums
’ total of the first 100 decimal digits of all irrational roots.
A number’s digital sum
is the sum of its digits.
The main task in the question is calculating irrational roots fast with a 100 digit precision.
A simple brute force solution will do a decent job here.
for
loop for n
between 1-100.n
, we will add the digital sum of its root (with a 100 decimal precision).We have to implement our own function for root calculation.
Dr. Frazer Jarvis explains a faster and precise way of calculating roots in the following document.
According to the document, the root of n
can be calculated faster by subtraction.
Let:
n
: The number whose root we want.
a
= 5*n
.
b
= 5.
Now, repeat the following steps:
if a
>=b
:
a
= a
- b
b
= b
+ 10
if a
<b
:
Add two 0’s at the end of a
:
a
= a
x100
Add one 0 in b
just before the last digit:
b
= ( b
- b
%10 )x10 + b
%10
While repeating the steps above, b
's value will be the root of n
's digits. As we repeat the steps above, the precision will increase. Hence, we will stop when we get a 100-decimal-precision.
a | b | |
1st time | 10 | 5 |
2nd time | 5 | 15 |
3rd time | 500 | 105 |
4th time | 395 | 115 |
5th time | 280 | 125 |
6th time | 155 | 135 |
# dSum calculates digital sum of n def dSum(n): sum = 0 while n!=0: sum+=n%10 n//=10 return sum # fastRoot will calculate root of n with 100 decimal digit precision. def fastRoot(n): a=5*n b=5 limit = 10**(101) while b<limit: if a>=b: a-=b b+=10 else: a*=100 b= (b-b%10)*10 + b%10 root = int(str(b)[:100]) return root result=0 for n in range(1,101): if n not in [1,4,9,16,25,36,49,64,81,100]: rootN = fastRoot(n) result += dSum(rootN) print(result)
Lines 2-7: We define a function, dSum
, which takes a number n
as input. It returns the digital sum of n
.
Lines 10-23: We define a function, fastRoot
, which takes n
as input. It computes the root of n
with a 100 digit precision by the method discussed above and returns this root.
Line 27: We initialize our
result
with 0.
Lines 28-31: We start a for-loop
for n
from 1 to 100. For every non-perfect-square n
, we increment our result
with the digital sum of n
's 100-digit-precision root.
RELATED TAGS
CONTRIBUTOR
View all Courses