Wanna square up?!

A simple memoization solution does the trick handily. We note that there will be a state (current sum, numbers remaining), and that since the maximum number is $81 * 16 = 1296$ , and we can have at most 16 numbers, there are about 20,000 states, easily doable. Sample C++ code below, noting the use of a for loop over all starting digits to avoid numbers with leading zeros

 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

#include <iostream>
#include <bitset>
#include <map>

using namespace std;

bitset<1300> square;
map< pair<int, int>, long long> memo;

long long num_squares(int current_sum, int numbers_remaining) {
    if (numbers_remaining == 0) {
        return square[current_sum];
    }
    if (memo.find(make_pair(current_sum, numbers_remaining)) != memo.end())
        return memo[make_pair(current_sum, numbers_remaining)];

    long long ans = 0;
    for (int i = 0; i < 10; i++) {
        ans += num_squares(current_sum + i*i, numbers_remaining - 1);
    }
    return memo[make_pair(current_sum, numbers_remaining)] = ans;
}

int main() {
    int i = 1;
    while (i*i < 1300) {
        square[i*i] = true;
        i++;
    }
    long long ans1 = 0;
    for (int i = 1; i < 10; i++) {
        ans1 += num_squares(i*i, 3);
    }
    cout << ans1 << endl;
}

Dynamic programming solution:

 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

#include <cmath>
#include <cstdio>
using namespace std;

long long memo[17][1297];

void init() {
    for(int i = 0; i < 17; i++) {
        for(int j = 0; j < 1297; j++) {
            memo[i][j] = 0;
        }
    }
    for(int i = 0; i <= 9; i++)  {
        memo[1][i*i] = 1;
    }
    for(int i = 2; i < 17; i++) {
        for(int j = 0; j <= 81*i; j++) {
            long long sum = 0;
            for(int k = 0; k <= 9; k++) {
                if(j - k*k >= 0) { sum += memo[i-1][j-k*k]; }
            }
            memo[i][j] = sum;
        }
    }
}

int main() {
    init();
    long long tot = 0;
    for(int i = 0; i <= 36; i++) {
        tot += (memo[16][i*i]-memo[15][i*i]);
    }
    printf("%lld\n", tot);
    return 0;
}

A bit of dynamic programming is convenient here. I keep track of a table $t[d, k] = \text{how many numbers with}\ d\ \text{digits have digit-square-sum of}\ k,$ and generate the table by increasing $d$ : $t[d+1,k] = \sum_{a = 0}^9 t[d,k - a^2].$ (For the first digit we start at $a = 1$ instead: a number does not start with zero.)

 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

final int nDig = 16, maxDig = 9;
long[][] t = new long[nDig+1][];        // t[d,k] = number of d-digit numbers with value k
t[0] = new long[1];                     // there is one zero-digit number with value 0
t[0][0] = 1;

for (int d = 1; d <= nDig; d++) {       // generate each row from the previous one
    t[d] = new long[maxDig*maxDig*d+1];
    for (int i = 0; i < t[d].length; i++)   // start with all zeroes
        t[d][i] = 0;

    int minDig = (d == 1 ? 1 : 0);          // first digit may not be zero
    for (int a = minDig; a <= maxDig; a++) {    // cycle through all digits
        int a2 = a*a;
        for (int k = 0; k < t[d-1].length; k++)
            t[d][k+a2] += t[d-1][k];            // the key step!
    }
}

long total = 0;
int n = 0, n2 = 0;                      // add t[d,n2] for last row and n2 a square
while (n2 < t[nDig].length) {
    total += t[nDig][n2];
    n2 += n; n++; n2 += n;              // equivalent to  n++; n2 = n*n;
}

out.println(total);

Output: 215576406208883

This one is mostly straightforward, with a couple of tricky aspects. The first thing to see is that just "brute force" checking every possible 16-digit base-10 integer for the property isn't just inelegant, it's probably impractical unless you have a supercomputer handy. Instead, we take advantage of the fact that each sequence of digits is repeated many times, (e.g. 4413, 1344 and 4314 give equivalent answers). So, the abstract algorithm goes something like this:

Loop over all unique sequences of n-digits:
     check condition
     if condition satisfied:
          matches += number of permutations for sequence

Finding the unique digit sequences is easy to implement recursively (see below). There is one wrinkle that needs to be handled carefully: only numbers starting with non-zero digits count as n-digit numbers (i.e. 4430 counts as 4-digit number, but 0443 doesn't). This means that you need to apply the binomial theory a bit differently when accounting for the number of places that zeros can appear in a given sequence. Here is a bit of pseudocode with an algorithm for computing the number of permutations:

n = # of digits remaining in sequence
zc = number of zeros in sequence
permutations = (n-1)! / [(zc!)(n-1-zc)!]   # binomial coefficient (Note that 0!=1.)
n -= zc
Loop over digits from 1 to 9:
     c = number of times digit i appears in sequence
     permutations *= n! / [c!(n-c)!] # binomial coefficient (Note that 0!=1.)
     n -= c

Ok, here's the python code I used to get the answer. One detail is that, when searching for unique digit sequences, I go backwards from 9 to zero to simplify the aforementioned issues with counting zeroes properly. Also, I do the outermost loop separately, and loop from 9 down to 1 (not zero) for the same reason. Finally, note the semantics for making copies of the digit repetition pattern list within the recursive algorithm are a bit subtle.

import math
def is_sq(n):  # returns true if a digit is a square
    return int(math.sqrt(n) + 0.5) ** 2 == n

def degen(patt):     # returns degeneracy of digit pattern patt - list of digit repetitions
    n= sum(patt)
    zc = patt[0]     # Note: first element of patt must contain # of zeroes 
    perms = fac(n-1) // fac(zc) // fac(n-1-zc)  # binomial coeff
    n -= zc
    for i in patt[1:]:       # loop over remaining elements of patt
        perms *= fac(n) // fac(i) // fac(n-i)
        n -= i
    return perms

def count_sq(n, i, patt, tot):  # recursive function to identify unique digit sequences 
                               # and keep running tally of numbers matching condition that sum 
                               # of squares of all digits is also a perfect square
                               # n:     number of digits remaining to be found
                               # i:     index of current digit value
                               # patt:  ordered list of repetition counts for digits 0-9
                               # tot:   sum of squares of digits found so far

    if n<1 or !(i in range(10)) or tot <0 or len(patt)!=10:  
        # check partial list of possible failure conditions
        print "Error: at least one parameter out of acceptable range"
        print n, i, patt, val
        exit(1)

    cnt = 0     # total number of matches found, up to an including current recursion level
    for j in range(i, -1, -1): # reverse loop over remaining possible digits from i down to 0
        pattcpy = patt[:]      # create local copy of digit pattern to modify
        pattcpy[j]+=1          # increment pattern count for current digit
        if n>1:                                          # if at bottom recursion level
            cnt += count_sq(n-1, j pattcpy[:], tot+j*j)  # make recursive call for next level
        else:
            if is_sq(tot+j*j):            # if sum of squares of digits matches condition
                cnt += degen(pattcpy[:])  # increment count by degeneracy of pattern
    return cnt


# main body
initpatt = [0,0,0,0,0,0,0,0,0]      # initialize ordered list of digit repetitions
cnt_4_dig=cnt_16_dig=0              # accumulator variables for demonstration

for i in range (9,0,-1): # outer loop for leading digit; reverse order simplifies counting of zeroes
    patt = initpatt[:]   # create local copy of initial digit pattern
    patt[k] += 1         # increment count for current digit
    cnt_4_dig += count_sq(3, k, patt[:], k*k)  
    cnt_16_dig += count_sq(15, k, patt[:], k*k) 

print cnt_4_dig    # outputs 332
print cnt_16_dig   # outputs 215576406208883