Project Euler Problem 92

Solve Project Euler Problem 92.

Hints

• Think about the looping structure of your solution. For a brute force solution we need to test each starting number between 1 and 9,999,999. That’s one loop (is a for-loop or a while-loop more appropriate?).

  Then for each starting number we need to test whether its digit chain ends at 89. That involves another loop (is a for-loop or a while-loop more appropriate?)

  Then for each number within the chain we need to isolate each digit, square it, and add it to a running total. That’s another loop (is a for-loop or a while loop more appropriate?)

• One thing you need to be able to do is to take a multi-digit integer, and be able to square each digit, and add that to a running total. There are many ways of achieving this in code.

  One way to approach this is to use MATLAB’s built-in function num2str() to convert an integer into a character string, then for each character convert that character back to an integer, square it, and add it to a running total. This is fine but turns out to be very slow (because the num2str() function is slow). If you prefer this approach that’s fine it will just take a while to complete.

  n = 145;
  ss = 0;
  nstr = num2str(n);        % nstr = '145'
  digit = str2num(nstr(1)); % digit = 1
  ss = ss + digit^2;        % ss = 1
  digit = str2num(nstr(2)); % digit = 4
  ss = ss + digit^2;        % ss = 17
  digit = str2num(nstr(3)); % digit = 5
  ss = ss + digit^2;        % ss = 42

  Another approach is to use MATLAB’s modulo operator (remainder after division) to take the modulus of a multi-digit integer by 10, which has the effect of isolating the last digit. Then you can square the digit, and add it to a running total. To slice off the last digit you could then subtract that digit from the integer, and divide by 10. For example let’s say the digit is 145:

  n = 145;
  ss = 0;
  digit = mod(n, 10); % digit = 5
  ss = ss + digit^2;  % ss = 25
  n = (n-digit)/10;   % n = 14
  digit = mod(n, 10); % digit = 4
  ss = ss + digit^2;  % ss = 41
  n = (n-digit)/10;   % n = 1
  digit = mod(n, 10); % digit = 1
  ss = ss + digit^2;  % ss = 42
  n = (n-digit)/10;   % n = 0
  % stop when n < 1

This approach is much faster (about 500x faster on my machine). My solution runs in about 3.5 seconds compared to over 30 minutes with the first approach.

Of course if you have another approach feel free to use it.