Related Tags

project euler
communitycreator

# How to Solve Project Euler 80

Armaan Nougai

### Problem statement

For the first 100 natural numbers, find the digital sums’ total of the first 100 decimal digits of all irrational roots.

### Question analysis

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.

### The solution approach

A simple brute force solution will do a decent job here.

1. We will run the for loop for n between 1-100.
2. For each non-perfect-square 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.

### 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:

1. if a>=b:

• a = a - b
• b = b + 10
2. 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.

Root of 2
 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)



### Code explanation

• 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

project euler
communitycreator

CONTRIBUTOR

Armaan Nougai
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time 