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
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.
January 5th, 2016.cpp:
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_List
template 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 :/ )