Project Euler Problem 917 – Number Splitting

We define an S-number to be a natural number, \(n\), that is a perfect square and its square root can be obtained by splitting the decimal representation of n into 2 or more numbers then adding the numbers.

For example, 81 is an S-number because \(\sqrt{81} = 8 + 1\).
6724 is an S-number: \(\sqrt{6724} = 6 + 72 + 4\).
8281 is an S-number: \(\sqrt{8281} =8 + 2 + 81 = 82 + 8 + 1\).
9801 is an S-number: \(\sqrt{9801} = 98 + 0 + 1\).

Further we define \(T(N)\) to be the sum of all S numbers \(n ≤ N\). You are given \(T(10^4) = 41333\).

Find \(T(10^{12})\).

One Comment Leave one →

Anonymous permalink

Every so often the Project Euler team slip in a relatively easy problem to encourage us lesser mortals to have a go at solving it. This one was one of these and is relatively easy to solve in Python. It is quite slow but gets the result in a few minutes.


# check if the integer in <value> can be split
# into parts that sum to <total>
def check(total, value):
  if value <= total:
    return value == total
  else:
    t = 10
    while t < value:
      left, right = divmod(value, t)
      if left <= total:
        if check(total - left, right):
          return True
      t *= 10
  return False

tot = 0
for n in range(4, 1000001):
  s = n * n
  if (n - s) % 9 == 0:
    if check(n, n * n):
      tot += n * n
      print(n, tot)

print(tot)

# check if the integer in <value> can be split

# into parts that sum to <total>

def check(total, value):

if value <= total:

return value == total

else:

t = 10

while t < value:

left, right = divmod(value, t)

if left <= total:

if check(total - left, right):

return True

t *= 10

return False

tot = 0

for n in range(4, 1000001):

s = n * n

if (n - s) % 9 == 0:

if check(n, n * n):

tot += n * n

print(n, tot)

print(tot)

A great feature of Python is the ease with which a solution method can be coded and tested but the result is always going to lag what can be achieved by compiled code. Nevertheless, once a Python program has been developed and tested, it s often easy to translate it into C or C++ to gain a big speed increase.


#include <stdio.h>
#include <stdint.h>

uint64_t check(uint64_t total, uint64_t value)
{
    if(value <= total)
        return value == total;
    else
    {
        uint64_t t = 1;
        while((t *= 10) < value)
        {
            uint64_t left = value / t, right = value % t;
            if(left <= total && check(total - left, right))
                return 1;
        }
    }
    return 0;
}

int main()
{
    uint64_t tot = 0;
    for(uint64_t n = 4; n <= 1000000; ++n)
    {
        uint64_t s = n * n;
        if((s - n) % 9 == 0)
            if (check(n, n * n))
            {
                tot += n * n;
                printf("%I64u  %I64u\n", n, tot);
            }
    }
    printf("%I64u", tot);
}

#include <stdio.h>

#include <stdint.h>

uint64_t check(uint64_t total, uint64_t value)

{

if(value <= total)

return value == total;

else

{

uint64_t t = 1;

while((t *= 10) < value)

{

uint64_t left = value / t, right = value % t;

if(left <= total && check(total - left, right))

return 1;

}

return 0;

}

int main()

{

uint64_t tot = 0;

for(uint64_t n = 4; n <= 1000000; ++n)

{

uint64_t s = n * n;

if((s - n) % 9 == 0)

if (check(n, n * n))

{

tot += n * n;

printf("%I64u %I64u\n", n, tot);

}

printf("%I64u", tot);

}

Project Euler Problem 917 – Number Splitting

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta