Programming Problem Set: 99 Problems Chapter 2

Home / Programming Problem Set: 99 Problems Chapter 2

Programming Problem Set: 99 Problems Chapter 2

December 9, 2015 | Labs | No Comments

Ninety-nine Problems is generalized version to famous P-99: Ninety-Nine Prolog Problems collection used for teaching programming. The problems initially set for prolog but later many solutions come from various programming language. The purpose of this problem is to give us opportunity to practice our skills in logic programming. The goal is to find the most elegant solution of the given problem. Efficiency is important, but logical clarity is even more crucial.

The problem set are divided into seven categories / chapters: Lists, Arithmetic, Logic and Codes, Binary Trees, Multiway Trees, Graphs, and Miscellaneous.

In this chapter you will be only given a problem set. The solution might come however it would be on different page.

This chapter will cover about Arithmetic. A list is either empty or it is composed of a first element (head) and a tail, which is a list itself. As a continuation from previous chapter, the problem will be started from last previous number.

29. Determine whether a given integer number is prime.

Example: is_prime_p( 7 ) -> Yes

30. Determine the prime factors of a given positive integer.

Construct a list containing the prime factors in ascending order

Example: prime_factor_p( 315 ) -> [ 3, 3, 5, 7 ]

31. DetermineĀ  the prime factors of a given positive integer (2)

Construct a list containing the prime factors and their multiplicity.

Example: prime_factor2_p( 315 ) -> [ [3,2], [5,1], [7,1] ]

Hint: The solution of problem 10 may be helpful.

32. A list of prime number

Given a range of integers by its lower and upper limit, construct
a list of all prime numbers in that range.

Example: prime_list_p( 3, 15 ) -> [3, 5, 7, 11, 13 ]

33. Goldbach’s conjecture

Goldbach's conjecture says that every positive even number greater
than 2 is the sum of two prime numbers. Example: 28 = 5 + 23.
It is one of the most famous facts in number theory that has not
been proved to be correct in the general case. It has been numerically
confirmed up to very large numbers.
Find the two prime numbers that sum up to a given even integer

Example: goldbach_p( 28 ) -> [ 5, 23]

34. A list of Goldbach compositions

Given a range of integers by its lower and upper limit, print a
list of all even numbers and their Goldbach composition

Example: goldbach_list_p( 9, 20 )
10 = 3 + 7
12 = 5 + 7
14 = 3 + 11
16 = 3 + 13
18 = 5 + 13
20 = 3 + 17

In most case, if an even number is written as the sum of two prime
numbers, one of them is very small. Very rarely, the primes are
both bigger than say 50. Try to find out how many such cases
there are in the range 2..3000.

35. Determine the greatest common divisor of two positive integer number

Use Euclid's algorithm

Example: gcd_p( 36, 63 ) -> 9

36. Determine whether two positive integer numbers are coprime

Two numbers are coprime if their greates common divisor equals 1

Example: coprime_p( 35, 64 ) -> Yes

37. Calculate Euler’s totient function phi(m)

Euler's so-called totient phi(m) is defined as the number of pisitive
integers r (1 <= r < m) that are coprime to m.
If m = 10 then r = 1, 3, 7, 9; thus phi(m) = 4. Note the special case
phi(1) = 1

Example: phi_p( 10 ) -> 4

38. Calculate Euler’s totient function phi(m) (2)

See the previous problem for definition of Euler's totient function.
If the list of the prime factors of a number m is known in the form
of problem 32 then the function phi(m) can be efficiently calculated
as follows:

Let [[p1, m1], [p2, m2], [p3, m3], ...] be the list of prime factors
(and their multiplicities) of a given number m. Then phi(m) can be
calculated with following formula:

phi(m) = (p1-1)* p1^(m1-1) *(p2-1)* p2^(m2-1)*(p3-1)* p3^(m3-1)

Note that a^b stands for the b'th power of a.

39. Compare the two methods of calculating Euler’s totient function.

Use the solution of problem 37 and 38 to compare algorithm. Take
the number of logical inferences as a measure for efficiency. Try to
calculate phi(10090) as an example

Solution:

  1. Haskell
  2. Lisp
  3. Prolog
  4. Python

, ,

About Author

about author

xathrya

A man who is obsessed to low level technology.

Leave a Reply

Your email address will not be published. Required fields are marked *

Social media & sharing icons powered by UltimatelySocial