Sum of "freaky" squares

Computer Science Level 4

Riffing off of " Freaky Square Number! " by Mark Mottian :

Find the sum of all five-digit positive integers that

  1. are square numbers
  2. have all digits square
  3. and are NOT ordered numbers.

Clarifications:

  • An ordered number is one whose digits are in an increasing sequence. For example, 155 155 is an ordered number but 515 515 is not; 11235 11235 is an ordered number but 51321 51321 is not.
  • A square is one that can be obtained by multiplying a number by itself (in particular, 0 = 0 ⋅ 0 0=0\cdot 0 is a square).

This problem was inspired by " Freaky Square Number! " by Mark Mottian , which was inspired by Problem #3 of the 2014 South African Programming Olympiad.


The answer is 313293.

View wiki
Scott Kominers by Scott Kominers , 34, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

8 solutions

Mark Mottian
Aug 7, 2014

Here is a Python 3.4.1 solution. This code is identical to my "Freaky Square Number!" solution, however, I've modified it slightly to check if the number is NOT ordered. I've also made use of a "Sum" variable to return the desired result. 

import math

count = 0
Sum = 0

#Method to determine a square number
def isSquare(n):
    if math.sqrt(n) == int(n**(1/2)):
        return True
    else:
        return False

#This method determines if number is ordered
def ordered(n):
    if sorted(list(str(n))) == list(str(n)):
        return True
    else:
        return False

#Inspect all 5-digit numbers
for x in range (10000, 100000): 
    if isSquare(x):    #check if it is a square
       for a in str(x):   
            #each digit must be a square
            if isSquare(int(a)):
                #count = 5; if all digits are squares
                count += 1 

        if count == 5:
            #check if the number is NOT ordered
            if ordered(x)==False:   
               Sum += x    #update "Sum" variable

    count = 0   #reset count

print (Sum)

The program returns 313293 as the answer.

For a more palpable understanding, the answer 313293 was obtained by taking the sum of the following values:

10000, 10404, 14400, 19044, 40000, 40401, 44100, 44944, 90000

5 Helpful 0 Interesting 0 Brilliant 0 Confused
Bill Bell
Oct 28, 2014

I avoid checking whether a given five-digit number is a square by iterating from 100 to 316 and squaring these numbers. I convert the squares to strings for examination. In one stream of activity non-square digits are converted to the character 'x' for detection. In the other stream successive characters are compared as to their alphabetic order to form an array (aka a list in Python) or Booleans, then this array is checked to see whether it is all true which would indicate an ordered set of numbers. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
 
from string import maketrans

tab=maketrans('0123456789', '01xx4xxxx9' )

sum = 0
for n in range ( 100, 317 ) :
    N = n ** 2
    N_as_str = str ( N )
    if 'x' in N_as_str . translate ( tab ) :
        continue
    N_digits = list ( N_as_str )
    if all ( [ j >= i for i, j in zip ( N_digits [ :-1 ], N_digits [ 1: ] ) ] ) : 
        continue
    sum += N
print ( sum )

1 Helpful 0 Interesting 0 Brilliant 0 Confused
Sudip Maji
Aug 13, 2014

Faster than @Mark Mottian's solution.

Faster in the sense I used a tuple to avoid same (0-9) square checking in that 90000 iteration long loop and used a break statement if it fails in the mid-way. Though I didn't check it practically using timeit but pretty sure it's faster.

Another one that is space complexity: We should avoid using range() if not necessary, use xrange() instead. It doesn't create the list in the memory imediately, rather it returns an iterator. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
 
result = 0    
for num in xrange(100, 317):
    count = 0
    squared_num = num*num
    for digit in str(squared_num):   
        if digit in ('0', '1', '4', '9'):
            count += 1
        else:
            break
    if count == 5:
        if sorted(list(str(squared_num))) != list(str(squared_num)):
            result += squared_num
print result

Answer: 313293

1 Helpful 0 Interesting 0 Brilliant 0 Confused
David Holcer
Apr 4, 2015 
1
2
3
4
5
6
7
8
9
 
from math import *
summ=0
for i in range(10**4,10**5):
    nums=[]
    for j in str(i):
        nums.append(int(j))
    if sqrt(i).is_integer() and not all(nums[i] <= nums[i+1] for i in xrange(len(nums)-1)) and sqrt(int(str(i)[0])).is_integer()and sqrt(int(str(i)[1])).is_integer() and sqrt(int(str(i)[2])).is_integer() and sqrt(int(str(i)[3])).is_integer() and sqrt(int(str(i)[4])).is_integer():
        summ+=i
print summ

0 Helpful 0 Interesting 0 Brilliant 0 Confused

No need to sorte, a raltively proper way of doing it : 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
#include <iostream>
#include <cmath>
using namespace std;
bool isOrdered(int n)
{
    int const K = floor(log10(n))+1;
    int tab[K];
    int t = 1;
    int k = 0;
    for(int i = 1;i <= K; i++)
    {
        tab[K-i] = floor((n%(int)pow(10,i))/pow(10,i-1));
    }
    while(k < K){
        while(tab[k] <= tab[t] && t < K) t++;
        if(t != K) return (false);
        k++;
        t = k+1;
    }

    return (k == K);
}
int main()
{
    int sum = 0;
    int i,k;
    int d = 0;
    k = 1;
    for(i = 10000;i < 100000;i++){

        if(floor(sqrt(i)) - sqrt(i) == 0 && !isOrdered(i)) {
            d =  floor((i%(int)pow(10,5))/pow(10,4));
            while(floor(sqrt(d)) - sqrt(d) == 0 && k <= 5) {
                d = floor((i%(int)pow(10,k))/pow(10,k-1));
                k++;
            }
        }
        if(k == 6) sum += i;
        k = 1;
    }
    cout << sum << endl;
    return 0;
}

0 Helpful 0 Interesting 0 Brilliant 0 Confused
Drop TheProblem
Sep 15, 2014 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{int numero[10],sum=0;
for(int i=100;i<=316;i++)
        {
        int n=i*i;
        numero[0]=(n%100000-n%10000)/10000;
        numero[1]=(n%10000-n%1000)/1000;
        numero[2]=(n%1000-n%100)/100;
        numero[3]=(n%100-n%10)/10;
        numero[4]=n%10;
        if(numero[0]==1 || numero[0]==4 || numero[0]==9)
           if(numero[1]==0 || numero[1]==1 || numero[1]==4 || numero[1]==9)
              if(numero[2]==0 || numero[2]==1 || numero[2]==4 || numero[2]==9)
                 if(numero[3]==0 || numero[3]==1 || numero[3]==4 || numero[3]==9)
                    if(numero[4]==0 || numero[4]==1 || numero[4]==4 || numero[4]==9)
                       {if (numero[1]>=numero[0] && numero[2]>=numero[1] && numero[3]>=numero[2] && numero[4]>=numero[3]) {int x;}
                       else sum=sum+(numero[0]*10000+numero[1]*1000+numero[2]*100+numero[3]*10+numero[4]);
                       }
        }
        cout<<sum;
system("pause");
return 0;
}

sum=313293

0 Helpful 0 Interesting 0 Brilliant 0 Confused
Nj Rafi
Sep 14, 2014

Just modified the C code for the "Freaky Square Number!" :) 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
#include <stdio.h>
#include <math.h>
int main()
{
        float a,b,c,d,e;
        float num,sum=0;

                for(a=1;a<=9;a++)
                        if(a==4 || a==9 || a==1)
                        for(b=0;b<=9;b++)
                                if(b==0 || b==4 || b==9|| b==1)
                                for(c=0;c<=9;c++)
                                        if(c==0 || c==4 || c==9|| c==1)
                                        for(d=0;d<=9;d++)
                                                if(d==0 || d==4 || d==9|| d==1)
                                                for(e=0;e<=9;e++)
                                                        if(e==0 || e==4 || e==9|| e==1)
                                                        {
                                                                if(e>=d && d>=c && c>=b &&b>=a)
                                                                        continue;
                                                               num = a*10000+b*1000+c*100+d*10+e;
                                                               if(sqrt(num)== (int)sqrt(num) )
                                                                        sum += num;
                                                        }
        printf("%.0f", sum);
        return 0;
}

0 Helpful 0 Interesting 0 Brilliant 0 Confused
Kenny Lau
Sep 7, 2014

java code: 

public class brilliant201409071630{
    public static void main(String args[]){
        int count = 0;
        int[] list = new int[65536];
        for(int i=100;;i++){
            if(i*i>=100000) break;
            String s = i*i+"";
            char c;
            boolean b=false;
            for(int j=0;j<s.length();j++){
                if((c=s.charAt(j))!='0'&&c!='1'&&c!='4'&&c!='9') b=true;
            }
            if(b) continue;
            b=true;
            for(int j=0;j<s.length()-1;j++){
                if(s.charAt(j)>s.charAt(j+1)) b=false;
            }
            if(b) continue;
            list[count]=i*i;
            count++;
        }
        System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(list,count)));
        int sum = 0;
        for(int i=0;i<count;i++) sum += list[i];
        System.out.println(sum);
    }
}

output: 

[10000, 10404, 14400, 19044, 40000, 40401, 44100, 44944, 90000]
313293
Press any key to continue . . .
0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...