### “Square Digit Chains”

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:

- a “brute force” method: if is a starting number in the range , the number chains beginning with are formed, so determining the number of chains beginning with that will eventually arrive at ;
- and what I thought would be a more-optimised method: if is a starting number in the range then the minimum sum of the squares of the digits of is and the maximum sum of the squares of the digits of is ; therefore, a binary tree is populated with pairs of the starting numbers in the range and the numbers that those starting numbers will eventually arrive at, and – rather than forming the number chains beginning with 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 will eventually arrive at, so determining the number of chains beginning with that will eventually arrive at .

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

Filed under: Uncategorized | Leave a Comment

Tags: C plus plus, CodeWarrior, make, makefile, Metrowerks CodeWarrior IDE 2.1 (Discover Programming Edition), Programming Praxis

## No Responses Yet to ““Square Digit Chains””