- All Contests
- ProjectEuler+
- Project Euler #171: Finding numbers for which the sum of the squares of the digits is a square
- Discussions

# Project Euler #171: Finding numbers for which the sum of the squares of the digits is a square

# Project Euler #171: Finding numbers for which the sum of the squares of the digits is a square

+ 1 comment Well, the example is crazy completely different from what he wants. It leads you to think that se answer is f(100) = 1^2 + 0^2 + 0^2 based on the question input. I believe itÂ´s an easy level but the explanation is hard.

+ 0 comments actual question says perfect square moduli(10^9+7)

+ 0 comments This is much harder than the original question. I can solve the original question in 3 seconds (Python 3), but the following changes make it much much harder:

- n could be 10^100 instead of 10^20 (at 10^20 I'm at 3s, the sum is about 10^40, at 10^30 I'm at 50s and I didn't bother testing more).
- n could be other than 10^N (e.g. n = 12563) makes me use a second algorithm

The extra "module 10^9 + 1" is just a diversion. In the range of n <= 10^100 they are just perfect squares (the next one is 14122 = 31623^2 module 10^9 + 1 but it has at least 175 digits).

+ 1 comment Let me try to explain the problem and reach out to 826 from 100

Givem k=100 , 0<=n<=100 Iterate n, for n = 0 to 100 if(f(n) is a perfect square) add to the result

(Please sum to get 826) 0 1 2 3 4 5 6 7 8 9 10 20 30 34 40 43 50 60 68 70 80 86 90 100

Naive solution: static void Main(string[] args) { long k = 100; long output = Project_Euler_171(k); }

`private static long Project_Euler_171(long k) { long sum = 0; for(int i = 0; i <= k; i++) { sum += IsPowerSquare(f(i)) ? i : 0; } return sum; } private static bool IsPowerSquare(long n) { double number = (double)n; return ((double)(Math.Sqrt(number) - (long)Math.Sqrt(number))) == 0.0; } private static long f(long n) { if (n == 0) return 0; return f(n / 10) + (n % 10) * (n % 10); }`

+ 0 comments I have passed 5 test cases can anyone please help how to optimise code for larger input

# Enter your code here. Read input from STDIN. Print output to STDOUT

if

**name**=="**main**": n=int(input()) def squares(value): return sum(int(c)**2 for c in str(value)) a=0 for i in range(1,n+1): if (squares(i)**0.5)==int(squares(i)**0.5): a+=i else: pass print(a)

Sort 70 Discussions, By:

Please Login in order to post a comment