Compatible Numbers
January 5, 2016
One solution involves factoring the two numbers, but that can be difficult. A better solution involves calculating the greatest common divisor of the two numbers, which must necessarily include all the factors of the numbers if the two numbers are compatible:
(define (compatible? a b)
(if (= a b) #t
(if (or (= a 1) (= b 1)) #f
(let ((g (gcd a b)))
(if (= g 1) #f
(and (reducible? g a)
(reducible? g b)))))))
First we consider the simple cases. If the two numbers are equal, or if either is 1, or if their greatest common divisor is 1, then we know the answer. Otherwise, we check if both numbers are reducible to 1 when repeatedly dividing by the greatest common divisor:
(define (reducible? g x)
(let ((d (gcd g x)))
(if (= d 1) #f
(if (= d x) #t
(reducible? g (/ x d))))))
It may be confusing, but there are two greatest common divisors here. The first is the greatest common divisor g of the two input numbers, and never changes. The second is the greatest common divisor d that is recomputed at each successive reduction of x; d will eventually equal some reduction of x if the two numbers have the same factors, or will equal 1 if there is a factor not included in g. The reducible? function will recur as many times as the greatest multiplicity of any of the factors of g in x. Here are some examples:
> (compatible? 15 75) #t > (compatible? (* 2 3 5 7 11) (* 2 3 5 7 11 13)) #f > (compatible? (* 2 3 5 7) (* 2 2 3 3 3 5 5 5 5 5 7 7 7 7 7 7 7)) #t
You can run the program at http://ideone.com/DrTp1q.
Learning a new language (Perl6) – so thought I’d try and solve it in that … syntactically it is a bit terse
sub compatible($a,$b) { return (2..sqrt($a <$b??$a!!$b)) .grep(&is-prime). .first(sub a($i){$a%$i&&$b%%$i||$a%%$i&&$b%$i}) .WHICH eq 'Nil' }Notes:
* $a??$b!!$c is perl6’s ternary operator
* $a%%$b returns true if $a is a multiple of $b
* first returns the first entry for which the condition is true o/w returns an object of type “Nil” which is an empty list
* WHICH returns the type of the object…
In Python.
def is_compatible(a, b): if a < 2 or b < 2: raise ValueError("a and b should be larger than 1") def reduce(a, g): while g != 1: a //= g g = gcd(g, a) return a gg = gcd(a, b) return 1 == reduce(a, gg) == reduce(b, gg)January 5th, 2016.cpp:
#include "seal_list.h" /* <http://GitHub.com/sealfin/C-and-C-Plus-Plus/blob/master/seal_list.h> */ #include <stdlib.h> #include <stdio.h> #include <string.h> #include <limits.h> char *f_ReadStringFromFile( FILE * const p_file, bool * const p_endOfFileEncountered ); char *f_ReadStringFromFile( FILE * const p_file, bool * const p_endOfFileEncountered ) { char c, *s = ( char* )malloc( sizeof( char )); size_t s_length = 1; *p_endOfFileEncountered = true; while( fscanf( p_file, "%c", &c ) != EOF ) { if( c == '\n' ) { *p_endOfFileEncountered = false; break; } s[ s_length - 1 ] = c; s = ( char* )realloc( s, sizeof( char ) * ++ s_length ); } s[ s_length - 1 ] = '\0'; return s; } bool f_StringToNumber( const char * const p_string, unsigned int * const p_number ); bool f_StringToNumber( const char * const p_string, unsigned int * const p_number ) /* Returns true if: * p_number != NULL; * p_string != NULL; * p_string points to a string comprised of – and only of – one or more digits in the range [ 0, 9 ]; * and the number represented by the string pointed to by p_string is in the range [ 0, UINT_MAX ]. */ { if( p_number == NULL ) return false; size_t i = 0; // The index of the first non-zero digit in p_string. if( p_string == NULL ) return false; if( strlen( p_string ) == 0 ) return false; for( ; i < strlen( p_string ); i ++ ) if( p_string[ i ] != '0' ) break; size_t k = strlen( p_string ); unsigned long long multiplier = 0, number = 0; for( ; k > i; k -- ) { if( multiplier == 0 ) multiplier = 1; else { multiplier *= 10; if( multiplier > UINT_MAX ) return false; } const char digit = p_string[ k - 1 ]; if(( digit >= '0' ) && ( digit <= '9' )) { number += (( digit - '0' ) * multiplier ); if( number > UINT_MAX ) return false; } else return false; } *p_number = number; return true; } struct t_PrimeFactor_struct { unsigned int m_primeFactor, m_multiplicity; }; class PrimeFactorList : public seal_List<struct t_PrimeFactor_struct*> { public: ~PrimeFactorList( void ) { p_Empty(); } private: void p_Delete( struct t_PrimeFactor_struct *p ) { free( p ); } public: void p_Set( const unsigned int p /* Prime factor. */ ) { size_t i = 0; struct t_PrimeFactor_struct *prime_factor; bool is_already_in_list = false; for( ; i < f_Number(); i ++ ) { prime_factor = f_GetByIndex( i ); if( prime_factor->m_primeFactor == p ) { is_already_in_list = true; prime_factor->m_multiplicity ++; break; } } if( !is_already_in_list ) { prime_factor = ( struct t_PrimeFactor_struct* )malloc( sizeof( struct t_PrimeFactor_struct )); prime_factor->m_primeFactor = p; prime_factor->m_multiplicity = 1; seal_List<struct t_PrimeFactor_struct*>::p_Set( prime_factor ); } } void p_Print( void ) { size_t i = 0; for( ; i < f_Number(); i ++ ) { const struct t_PrimeFactor_struct * const prime_factor = f_GetByIndex( i ); if( i > 0 ) printf( " * " ); printf( "%u", prime_factor->m_primeFactor ); if( prime_factor->m_multiplicity > 1 ) printf( " ^ %u", prime_factor->m_multiplicity ); } } }; PrimeFactorList *f_DecomposeNumberIntoPrimeFactors( unsigned int p ); PrimeFactorList *f_DecomposeNumberIntoPrimeFactors( unsigned int p ) { unsigned int i = 2; PrimeFactorList *prime_factor_list = new PrimeFactorList(); while( i * i <= p ) if( p % i == 0 ) { prime_factor_list->p_Set( i ); p /= i; i = 2; } else if( i == 2 ) i = 3; else i += 2; if( p != 1 ) prime_factor_list->p_Set( p ); return prime_factor_list; } bool f_AreCompatible( PrimeFactorList * const a, PrimeFactorList * const b ); bool f_AreCompatible( PrimeFactorList * const a, PrimeFactorList * const b ) { if( a->f_Number() != b->f_Number()) return false; size_t i = 0; for( ; i < a->f_Number(); i ++ ) { size_t k = 0; const struct t_PrimeFactor_struct * const prime_factor_a = a->f_GetByIndex( i ); bool prime_factor_found = false; for( ; k < b->f_Number(); k ++ ) { const struct t_PrimeFactor_struct * const prime_factor_b = b->f_GetByIndex( k ); if( prime_factor_a->m_primeFactor == prime_factor_b->m_primeFactor ) { prime_factor_found = true; break; } } if( !prime_factor_found ) return false; } return true; } size_t f_NumberOfDigits( const unsigned int p ); size_t f_NumberOfDigits( const unsigned int p ) { unsigned long long divisor = 10; size_t number_of_digits = 1; while( p / divisor != 0 ) { divisor *= 10; number_of_digits ++; } return number_of_digits; } void p_PrintSpaces( const size_t p_numberOfSpaces ); void p_PrintSpaces( const size_t p_numberOfSpaces ) { size_t i = 0; for( ; i < p_numberOfSpaces; i ++ ) printf( " " ); } void p_PrintCompatibleNumbersAndPrimeFactors( const unsigned int a, PrimeFactorList * const prime_factors_of_a, const unsigned int b, PrimeFactorList * const prime_factors_of_b ); void p_PrintCompatibleNumbersAndPrimeFactors( const unsigned int a, PrimeFactorList * const prime_factors_of_a, const unsigned int b, PrimeFactorList * const prime_factors_of_b ) { const size_t number_of_digits_in_a = f_NumberOfDigits( a ), number_of_digits_in_b = f_NumberOfDigits( b ); size_t longest_number_of_digits; if( number_of_digits_in_a > number_of_digits_in_b ) longest_number_of_digits = number_of_digits_in_a; else longest_number_of_digits = number_of_digits_in_b; printf( "%u ", a ); p_PrintSpaces( longest_number_of_digits - number_of_digits_in_a ); printf( "= " ); prime_factors_of_a->p_Print(); printf( "\n" ); printf( "%u ", b ); p_PrintSpaces( longest_number_of_digits - number_of_digits_in_b ); printf( "= " ); prime_factors_of_b->p_Print(); printf( "\n" ); } int main( const int argc, const char * const argv[] ) { char *s; bool end_of_file_encountered, error_occurred; unsigned int first; PrimeFactorList *prime_factors_of_first, *prime_factors_of_second; #ifndef __MWERKS__ printf( "\n" ); #endif printf( "This program will either –\n" ); printf( "i. determine if the two integers you enter are \"compatible\" – viz., if the two integers have the same prime factors, but not necessarily with the same multiplicities;\n" ); printf( "or ii. try to determine the least integer \"compatible\" with, but not equal to, the integer you enter.\n" ); do { printf( "\nPlease enter the first integer in the range [ 2, %u ], and press the Return key.\n", UINT_MAX ); printf( "\nYour input: " ); s = f_ReadStringFromFile( stdin, &end_of_file_encountered ); error_occurred = false; if( !f_StringToNumber( s, &first ) || ( first < 2 )) { error_occurred = true; printf( "\nSorry, an error occurred: you did not enter an integer in the range [ 2, %u ].\n", UINT_MAX ); printf( "\nPlease press the Return key to try again." ); free( f_ReadStringFromFile( stdin, &end_of_file_encountered )); } free( s ); } while( error_occurred ); prime_factors_of_first = f_DecomposeNumberIntoPrimeFactors( first ); do { printf( "\nPlease either enter –\n" ); printf( "i. the second integer in the range [ 2, %u ] to have this program determine if that integer is \"compatible\" with the integer %u;\n", UINT_MAX, first ); printf( "or ii. nothing to have this program try to determine the least integer \"compatible\" with, but not equal to, the integer %u;\n", first ); printf( "– and press the Return key.\n" ); printf( "\nYour input: " ); s = f_ReadStringFromFile( stdin, &end_of_file_encountered ); error_occurred = false; if( strlen( s ) == 0 ) { unsigned long long second = 2; bool are_compatible = false; do { if( second != first ) { prime_factors_of_second = f_DecomposeNumberIntoPrimeFactors( second ); are_compatible = f_AreCompatible( prime_factors_of_first, prime_factors_of_second ); if( !are_compatible ) { delete prime_factors_of_second; if( ++ second > UINT_MAX ) break; } } else if( ++ second > UINT_MAX ) break; } while( !are_compatible ); if( !are_compatible ) printf( "\nThere is no integer \"compatible\" with, but not equal to, the integer you entered, %u, in the range [ 2, %u ].\n", first, UINT_MAX ); else { printf( "\nThe least integer \"compatible\" with, but not equal to, the integer you entered, %u, is %u:\n", first, ( unsigned int )second ); p_PrintCompatibleNumbersAndPrimeFactors( first, prime_factors_of_first, second, prime_factors_of_second ); delete prime_factors_of_second; } } else { unsigned int second; if( !f_StringToNumber( s, &second ) || ( second < 2 )) { error_occurred = true; printf( "\nSorry, an error occurred: you entered neither an integer in the range [ 2, %u ] nor nothing.\n", UINT_MAX ); printf( "\nPlease press the Return key to try again." ); free( f_ReadStringFromFile( stdin, &end_of_file_encountered )); } else { prime_factors_of_second = f_DecomposeNumberIntoPrimeFactors( second ); printf( "\nThe two integers you entered, %u and %u, are ", first, second ); if( !f_AreCompatible( prime_factors_of_first, prime_factors_of_second )) printf( "not " ); printf( "\"compatible\":\n" ); p_PrintCompatibleNumbersAndPrimeFactors( first, prime_factors_of_first, second, prime_factors_of_second ); delete prime_factors_of_second; } } free( s ); } while( error_occurred ); delete prime_factors_of_first; printf( "\n" ); #ifdef __MWERKS__ printf( "This program will now quit.\n" ); #endif return 0; }The program is known to run on an Apple Power Mac G4 (AGP Graphics) (450MHz processor, 1GB memory) 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 Xcode 2.2.1).
The program is able to – in addition to what is specified in the description of the problem – try to determine the least integer “compatible” with, but not equal to, the integer entered by the user; however, the approach the program takes to do that – beginning with 2 testing if every integer ≤
UINT_MAX(besides the integer entered by the user) is “compatible” with the integer entered by the user until such an integer is found – is needlessly slow; a faster approach to take would be to decompose the integer entered by the user into its prime factors and then:if the multiplicity of every of those prime factors is 1, set the multiplicity of the least of those prime factors to 2;
or, if the multiplicity of any of those prime factors is not 1, set the multiplicity of every of those prime factors to 1.
(I’ve just completed a gig at London South Bank University and so I’m again just trying to solve the problems posed by this ‘site whilst I try to get a job (and I’ve solved this problem in particular to test my
seal_Listtemplate class I might use in the fourth version of my SDL2 joystick interrogator utility); 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 :/ )