### “Square Digit Chains”

19Oct18

The following is my solution to the “Square Digit Chains” problem posed by Programming Praxis; I’d usually post my solution as a comment on that ‘site, but I learned after I posted as a comment on that ‘site my solution to the “Emirps” problem posed by that ‘site that that ‘site doesn’t support images in comments.

Lacking a “recent-vintage personal computer” – my solutions to the problems posed by the aforementioned ‘site are programmed- and run- on an Apple Power Mac G4 (AGP Graphics) (450MHz processor, 1GB memory) – and wanting to test my understanding of: compiling a project using a Metrowerks CodeWarrior IDE 2.1 (Discover Programming Edition) project with multiple targets; compiling a project using the command line; and compiling a project using a makefile with multiple targets; understanding that might be necessary if I’m to release an executable of my SDL2 joystick interrogator utility, or of my entry for Ludum Dare 5, for the Raspberry Pi, I interpreted the instruction that I should abide by “the usual Project Euler rule that your computation may take no more than a minute of computation on a recent-vintage personal computer” as an invitation to compare two methods for arriving at the result:

1. a “brute force” method: if $n$ is a starting number in the range $\left[ 1,9999999 \right]$, the number chains beginning with $n$ are formed, so determining the number of chains beginning with $n$ that will eventually arrive at $89$;
2. and what I thought would be a more-optimised method: if $n$ is a starting number in the range $\left[ 1,9999999 \right]$ then the minimum sum of the squares of the digits of $n$ is $1\cdot 1^{2}=1$ and the maximum sum of the squares of the digits of $n$ is $7\cdot 9^{2}=567$; therefore, a binary tree is populated with pairs of the starting numbers in the range $\left[ 1,567 \right]$ and the numbers that those starting numbers will eventually arrive at, and – rather than forming the number chains beginning with $n$ as in the “brute force” method – that binary tree is used to look up the numbers that the sum of the squares of the digits of $n$ will eventually arrive at, so determining the number of chains beginning with $n$ that will eventually arrive at $89$.

The results were surprising: not only was the first, “brute force”, method faster than the second, more-optimised, method (when running on both Mac OS 9.2.2 (International English), the program compiled using Metrowerks CodeWarrior IDE 2.1 (Discover Programming Edition), and Mac OS X 10.4.11, the program compiled using the command line: make method_1 and make method_2), but the first method arrived at the result in less than a minute (when running on Mac OS X 10.4.11) in spite of running on my aforementioned far from “recent-vintage personal computer”.

(I’m just trying to solve the problems posed by the aforementioned ‘site whilst I try to get a job; I’m well-aware that my solutions are far from the best – but, in my defence, I don’t have any traditional qualifications in computer science )

Output:

It is stated that a number chain is formed by continuously summing together the squares of the digits of a number to form a new number, terminating when the "new" number so formed has already been encountered earlier in the chain.

Eg.
44 -> 32 -> 13 -> 10 -> 1 -> 1
Or eg.
85 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89

Furthermore, it is stated that any starting number will eventually arrive at either 1 or 89.

Fri Oct 19 09:00:00 2018

8581146 starting numbers in the range [ 1, 9999999 ] will eventually arrive at 89.

Fri Oct 19 09:00:18 2018

October 19th, 2018.cpp:

#include "printDateAndTime.h" /* <http://Gist.GitHub.com/sealfin/6d35f3a3958bd6797a0f> */
#include <stdio.h>
#include <stdlib.h>

unsigned int g_limit = 9999999;

unsigned int f_SumOfSquaresOfDigits( unsigned int p )
{
unsigned int sum_of_squares_of_digits = 0;

while( p > 0 )
{
const unsigned int digit = p % 10;

p /= 10;
sum_of_squares_of_digits += ( digit * digit );
}
return sum_of_squares_of_digits;
}

unsigned int g_numberOfStartingNumbersThatArriveAt89 = 0;

void p_DetermineNumberOfStartingNumbersThatArriveAt89( void );

int main( const int argc, const char * const argv[] )
{
#ifndef __MWERKS__
printf( "\n" );
#endif

printf( "It is stated that a number chain is formed by continuously summing together the squares of the digits of a number to form a new number, terminating when the \"new\" number so formed has already been encountered earlier in the chain.\n\n" );
printf( "Eg.\n" );
printf( "\t44 -> 32 -> 13 -> 10 -> 1 -> 1\n" );
printf( "Or eg.\n" );
printf( "\t85 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89\n\n" );
printf( "Furthermore, it is stated that any starting number will eventually arrive at either 1 or 89.\n\n" );

p_PrintDateAndTime();
p_DetermineNumberOfStartingNumbersThatArriveAt89();
printf( "\n" );
if( g_numberOfStartingNumbersThatArriveAt89 == 0 )
printf( "No" );
else
printf( "%u", g_numberOfStartingNumbersThatArriveAt89 );
printf( " starting number%s in the range [ 1, %u ] will eventually arrive at 89.\n\n", ( g_numberOfStartingNumbersThatArriveAt89 != 1 )?"s":"", g_limit );
p_PrintDateAndTime();

#ifndef __MWERKS__
printf( "\n" );
#endif

exit( EXIT_SUCCESS );
}

method #1.cpp:

extern unsigned int g_limit;

unsigned int f_SumOfSquaresOfDigits( unsigned int p );

extern unsigned int g_numberOfStartingNumbersThatArriveAt89;

void p_DetermineNumberOfStartingNumbersThatArriveAt89( void )
{
unsigned int i = 1;

for( ; i <= g_limit; i ++ )
{
unsigned int k = i;

while(( k != 1 ) && ( k != 89 ))
k = f_SumOfSquaresOfDigits( k );
if( k == 89 )
g_numberOfStartingNumbersThatArriveAt89 ++;
}
}

method #2.cpp:

#include "seal_tree.h" /* <http://GitHub.com/sealfin/C-and-C-Plus-Plus/blob/master/seal_tree.h> */

static size_t f_NumberOfDigits( unsigned int p )
{
if( p == 0 )
return 1;

size_t number_of_digits = 0;

do
{
number_of_digits ++;
p /= 10;
}
while( p > 0 );
return number_of_digits;
}

extern unsigned int g_limit;

typedef struct t_NumberArrivesAt_TreeNode_struct
{
unsigned int m_number;
bool m_arrivesAtSet;
unsigned int m_arrivesAt;
}
t_NumberArrivesAt_TreeNode;

class NumberArrivesAt_Tree : public seal_Tree<t_NumberArrivesAt_TreeNode, unsigned int>
{
public:
NumberArrivesAt_Tree( void )
{
p_SetNumber( 1 );
p_SetArrivesAt( 1 );
p_SetNumber( 89 );
p_SetArrivesAt( 89 );
}

void p_SetNumber( unsigned int p )
{
t_NumberArrivesAt_TreeNode n;

n.m_number = p;
n.m_arrivesAtSet = false;
seal_Tree<t_NumberArrivesAt_TreeNode, unsigned int>::p_Set( n );
}

void p_SetArrivesAt( unsigned int p )
{
p_SetArrivesAt( m_root, p );
}

private:
void p_SetArrivesAt( struct t_seal_TreeNode<t_NumberArrivesAt_TreeNode> * const p_n, const unsigned int p_arrivesAt )
{
if( p_n != NULL )
{
p_SetArrivesAt( p_n->m_l, p_arrivesAt );
if( !p_n->m_content.m_arrivesAtSet )
{
p_n->m_content.m_arrivesAtSet = true;
p_n->m_content.m_arrivesAt = p_arrivesAt;
}
p_SetArrivesAt( p_n->m_r, p_arrivesAt );
}
}

public:
unsigned int f_GetArrivesAt( unsigned int p )
{
return f_Get( p ).m_arrivesAt;
}

private:
t_seal_TREE_BRANCH_DIRECTION f_Compare_TT( t_NumberArrivesAt_TreeNode p_old, t_NumberArrivesAt_TreeNode p_new )
{
if( p_new.m_number < p_old.m_number )
return k_seal_TREE_BRANCH_DIRECTION__LEFT;
if( p_new.m_number == p_old.m_number )
return k_seal_TREE_BRANCH_DIRECTION__STRAIGHT;
return k_seal_TREE_BRANCH_DIRECTION__RIGHT;
}

t_seal_TREE_BRANCH_DIRECTION f_Compare_TU( t_NumberArrivesAt_TreeNode p_content, unsigned int p_identifier )
{
if( p_identifier < p_content.m_number )
return k_seal_TREE_BRANCH_DIRECTION__LEFT;
if( p_identifier == p_content.m_number )
return k_seal_TREE_BRANCH_DIRECTION__STRAIGHT;
return k_seal_TREE_BRANCH_DIRECTION__RIGHT;
}

t_NumberArrivesAt_TreeNode f_IsNotInTree( unsigned int p )
{
}
};

unsigned int f_SumOfSquaresOfDigits( unsigned int p );

extern unsigned int g_numberOfStartingNumbersThatArriveAt89;

void p_DetermineNumberOfStartingNumbersThatArriveAt89( void )
{
unsigned int i = 1;
const unsigned int limit = f_NumberOfDigits( g_limit ) * 9 * 9;
NumberArrivesAt_Tree number_arrives_at;

for( ; i <= limit; i ++ )
{
unsigned int k = i;

while( !number_arrives_at.f_IsInTree( k ))
{
number_arrives_at.p_SetNumber( k );
k = f_SumOfSquaresOfDigits( k );
}
number_arrives_at.p_SetArrivesAt( number_arrives_at.f_GetArrivesAt( k ));
}
for( i = 1; i <= g_limit; i ++ )
if( number_arrives_at.f_GetArrivesAt( f_SumOfSquaresOfDigits( i )) == 89 )
g_numberOfStartingNumbersThatArriveAt89 ++;
}

Makefile:

error:
echo "Sorry, an error occurred: you must specify either \"method_1\" or \"method_2\"."

common: printDateAndTime.h printDateAndTime.c October\ 19th,\ 2018.cpp
g++ -c printDateAndTime.c
g++ -c October\ 19th,\ 2018.cpp

method_1: common method\ \#1.cpp
g++ -c method\ \#1.cpp
g++ printDateAndTime.o method\ \#1.o October\ 19th,\ 2018.o -o Method\ \#1
rm printDateAndTime.o
rm method\ \#1.o
rm October\ 19th,\ 2018.o

method_2: common seal_tree.h method\ \#2.cpp
g++ -c method\ \#2.cpp
g++ printDateAndTime.o method\ \#2.o October\ 19th,\ 2018.o -o Method\ \#2
rm printDateAndTime.o
rm method\ \#2.o
rm October\ 19th,\ 2018.o