Trusted answers to developer questions
Trusted Answers to Developer Questions

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
RELATED COURSES

View all Courses

Keep Exploring