The greatest common divisor (GCD) or the highest common factor (HCF) of two numbers is the largest positive integer that perfectly divides the two given numbers. Solving this problem for a specific set of numbers is easy. For example, find the GCD of 12 and 18. The The divisors of 12 are 1, 2, 3, 4, 6, 12 and for 18 are 1, 2, 3, 6, 9, 18. The common factors are 1, 2, 3, and 6. So the greatest common factor is 6. How would you find the GCD for any number? Here the problem is more challenging. Here is one solution. Let's take two integers a and b passed to a function which returns the GCD. In the function, we first determine the smaller of the two number since the GCD (HCF) can only be less than or equal to the smallest number. For example, the GCD of 12 and 14 can only be less than 12 and not greater. We then use a for loop to go from 1 to that number. In each iteration, we check if our number perfectly divides both the input numbers. If so, we store the number as the GCD. At the completion of the loop we end up with the largest number that perfectly divides both the numbers. Below is the algorithm in python. def computeGCD(a, b): if a < b: smaller = a else: smaller = b for i in range(1, smaller+1): if (a % i == 0) & (b % i == 0): gcd = i return gcd print(computeGCD(24, 16)) print(computeGCD(48, 256)) N.B: Do not cut and paste the above code. Make sure the indentation is correct. The above method is easy to understand and implement but not efficient. A much more efficient method to find the GCD (HCF) is the Euclidean algorithm. The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. That is a mouthful! Let's make it simple by taking an example. 21 is the GCD of 252 and 105 (as 252 = 21 × 12 and 105 = 21 × 5), and the same number 21 is also the GCD of 105 and 147 (252 − 105). Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, they are the GCD of the original two numbers. A more efficient version of the algorithm shortcuts these steps, instead we divide the greater by smaller and take the remainder. Now, divide the smaller by this remainder. Repeat until the remainder is 0. For example, if we want to find the H.C.F. of 54 and 24, we divide 54 by 24. The remainder is 6. Now, we divide 24 by 6 and the remainder is 0. Hence, 6 is the required GCD. Python code for Euclidean Algorithm def euclidAlgo(a, b): while (b): a, b = b, a % b return a print(euclidAlgo(24, 16)) print(euclidAlgo(48, 256)) Python code for Euclidean Algorithm using recursion: def euclidAlgo(a, b): if (b == 0): return a else: return euclidAlgo(b, a % b) print(euclidAlgo(24, 16)) print(euclidAlgo(48, 256)) Sources: Wikipedia; https://www.programiz.com/pythonprogramming/examples/hcf
0 Comments
Free Image from Pixabay Finding Prime NumbersPrime numbers are very important, yet many students do not see the value of learning them. Primes have several applications, most importantly in information technology, such as publickey cryptography, which relies on the difficulty of factoring large numbers into their prime factors. One key challenge is to find prime numbers. Interestingly, Prime numbers and their properties were first studied extensively by the ancient Greek mathematicians. Euclid, for example, proved that there are infinitely many prime numbers. Just to refresh our memory, a number greater than 1 is called a prime number, if it has only two factors, namely 1 and the number itself. Proof by Contradiction One of the first known proofs is the method of contradiction. It is used to calculate prime factors of large numbers. Calculating prime factors of small numbers is easy. For example, the factors of 17 is 1 and 17, so it is a prime number. What about large numbers? Let's look at the proof by contradiction method. If a number n is not a prime, it can be factored into two factors a and b, such that n = a*b. For example, let's say a * b = 100, for various pairs of a and b. If a = b, then they are equal, we have a*a = 100, or a^2 = 100, or a = 10, the square root of 100. If one of the numbers is less than 10, then the other has to be greater to make it to 100. For example, take 4 x 25 = 100. 4 is less than 10, the other number has to be greater than 10. In other words, if a * b, if one of them goes down, the other number has to get bigger to compensate so the product stays at 100. Put mathematically, the numbers revolve around the square root of their product. Let's test if 101 is prime number. You could start dividing 101 by 2, 3, 5, 7, etc, but that is very tedious. A better way is to take the square root of 101, which is roughly equal to 10.049875621. So you only need to try the integers up through 10, including 10. 8, 9, and 10 are not themselves prime, so you only have to test up through 7, which is prime. Because if there's a pair of factors with one of the numbers bigger than 10, the other of the pair has to be less than 10. If the smaller one doesn't exist, there is no matching larger factor of 101. Let's now build an algorithm using this method to test any number for primality. Algorithm in Pythonimport math def isPrime(num): if (num < 2): return False else: for i in range(2, int(math.sqrt(num)) + 1): if num % i == 0: return False return True print(isPrime(33)) print(isPrime(0)) print(isPrime(47)) print(isPrime(1047)) print(isPrime(11)) print(isPrime(59392847)) N.B: Do not just copy the code because you have to be careful with indentation in python. Try the above algorithm and let us know if you found it useful or have alternative solutions.
Free Image from Pixabay
Problem
N.B: This problem is for SAT Subject Math Level 2
\(If \quad x_0 \quad and \quad x_{x+1} = \sqrt {4 + x_n}, \quad then \quad x_3 = \)
(A) 2.65
(B) 2.58 (C) 2.56 (D) 2.55 (E) 2.54 Solution
Answer is C.
This is a simple but tricky problem. It is simple to apply but you have to think recursively. For n = 0, we have:
\(x_{0+1} = \sqrt {4 + x_0} \)
\(x_1 \quad = \quad \sqrt {4 + 3} \quad = \quad \sqrt{7} \quad = \quad 2.65 \)
\(x_2 \quad = \quad \sqrt {4 + x_1} \quad = \quad \sqrt {4 + 2.65} \quad = \quad 2.58 \)
\(x_3 \quad = \quad \sqrt {4 + x_2} \quad = \quad \sqrt{4 + 2.58} \quad = \quad 2.56\)
Problem:In the equation r = 4/(2 + k), k represents a positive integer. As k gets larger without bound, the value of r: F. gets closer and closer to 4. G. gets closer and closer to 2. H. gets closer and closer to 0. J. remains constant. K. gets larger and larger Answer:Answer is H.
As k gets larger and larger without bound, the expression 4/(2+k) becomes 4 divided by an increasingly large number. For example, think about the trend between the following fractions: 4/100, 4/10,000, 4/1,000,000, ... Looking at it this way, you can see that the expression for r gets closer and closer to zero. Free Image from Pixabay Seeing me, she roused herself: she made a sort of effort to smile, and framed a few words of congratulations; but the smile expired, and the sentence was abandoned unfinished. She put up her spectacles and pushed her chair back from the table. “I feel so astonished,” she began, “I hardly know what to say to you, Miss Eyre. I have surely not been dreaming, have I? Sometimes I half fall asleep when I am sitting alone and fancy things that have never happened. It has seemed to me more than once when I have been in a doze, that my dear husband, who died fifteen years since, has come in and sat down beside me; and that I have even heard him call me by my name, Alice, as he used to do. Now, can you tell me whether it is actually true that Mr. Rochester has asked you to marry him? Don’t laugh at me. But I really thought he came in here five minutes ago, and said that in a month you would be his wife.” [10] “He has said the same thing to me,” I replied. “He has! Do you believe him? Have you accepted him?” “Yes.” She looked at me bewildered. “I could never have thought it. He is a proud man; all the Rochesters were proud: and his father at least, liked money. He, too, has always been called careful. He means to marry you?” “He tells me so.” She surveyed my whole person: in her eyes I read 30 that they had there found no charm powerful enough to solve the enigma. “It passes me!” she continued; “but no doubt it is true since you say so. How it will answer I cannot tell: I really don’t know. Equality of position and fortune is often advisable in such cases; and there are twenty years of difference in your ages. He might almost be your father.” [22] “No, indeed, Mrs. Fairfax!” I exclaimed, nettled; “he is nothing like my father! No one, who saw us 40 together, would suppose it for an instant. Mr. Rochester looks as young, and is as young, as some men at five and twenty.” “Is it really for love he is going to marry you?” she asked. I was so hurt by her coldness and skepticism, that the tears rose to my eyes. “I am sorry to grieve you,” pursued the widow; “but you are so young, and so little acquainted with men, I wished to put you on your guard. It is an old saying that ‘all is not gold that glitters’; and in this case I do fear there will be something found to be different to what either you or I expect.” [30] “Why?—am I a monster?” I said: “Is it impossible that Mr. Rochester should have a sincere affection for me?” “No: you are very well; and much improved of late; and Mr. Rochester, I dare say, is fond of you. I have always noticed that you were a sort of pet of his. There are times when, for your sake, I have been a little uneasy at his marked preference, and have wished to put you on your guard; but I did not like to suggest even the possibility of wrong. I knew such an idea would shock, perhaps offend you; and you were so discreet, and so thoroughly modest and sensible, I hoped you might be trusted to protect yourself. Last night I cannot tell you what I suffered when I sought all over the house, and could find you nowhere, nor the master either; and then, at twelve o’clock, saw you come in with him. “Well never mind that now,” I interrupted impatiently; “it is enough that all was right.” [40] “I hope all will be right in the end,” she said: “but, believe me, you cannot be too careful. Try and keep Mr. Rochester at a distance: distrust yourself as well as him. Gentlemen in his station are not accustomed to marry their governesses.” Questions:1. When Mrs. Fairfax says, “Gentlemen in his station are not accustomed to marry their governesses,” she is expressing her belief that: A. Mr. Rochester is incapable of loving Miss Eyre. B. Mr. Rochester will treat Miss Eyre like a governess when they are married. C. Mr. Rochester may not be sincere about his feeling towards Miss Eyre D. Mr. Rochester may not really have asked Miss Eyre to marry him. 2. It can be reasonably inferred from the conversation that Mrs. Fairfax believes Miss Eyre will: F. recognize that Mr. Rochester actually wants to marry Mrs. Fairfax. G. marry Mr. Rochester much sooner than originally planned. H. no longer desire to marry Mr. Rochester. J. potentially regret her decision to agree to marry Mr. Rochester. 3. Mrs. Fairfax’s opinion about Miss Eyre and Mr. Rochester’s relationship can best be exemplified by which of the following quotations from the passage? A. “Mr. Rochester looks as young, and is as young, as some men at five and twenty.” B. “How it will answer I cannot tell: I really don’t know.” C. “He is a proud man; all the Rochesters were proud.” D. “But I really thought he came in here five minutes ago, and said that in a month you would be his wife.” 4. The phrase “you were so discreet, and so thor oughly modest and sensible” (lines 36–37) is used by Mrs. Fairfax to: F. explain why Miss Eyre should not marry Mr. Rochester. G. explain why it is likely that Mr. Rochester really does not plan on marrying Miss Eyre. H. explain why Mrs. Fairfax had not discussed Mr. Rochester’s feelings toward Miss Eyre before. J. insult Miss Eyre and let her know that Mrs. Fairfax was disappointed in her. 5. The passage makes it clear that Miss Eyre and Mr. Rochester: A. get married. B. do not really know each other well enough to become engaged. C. will not live happily because they will be shunned by society. D. have a relationship that is not typical in their society. Answers:
Ref: McGraw Hill

AuthorWrite something about yourself. No need to be fancy, just an overview. Archives
November 2018
Categories
All
