7) Decomposition in prime factors

6) Ramanujan and the scanning method

Find all the positive integers p and q such that :
p³ + q³ = 1 729.

Method : one method consists in trying all the possibilities, by replacing p and q by all the possible values of integers of a well determined set. This method is called the "Scanning method".

Limitation of the set of solutions : if a couple (p ; q) is solution of the equation, each of the two integers p and q has a cube which cannot be greater than 1 729 ; we check that 12³ = 1 728. Each of these numbers is therefore inferior to 12.

Cultural complement : The mathematician Ramanujan (1887 - 1920) is considered as one of the greatest specialists of number theory of the 20th century. He is attributed the following result :

"The integer 1 729 is the smallest natural integer to be decomposed in sum of two cubes in two different ways".

The programs :

Main instructions in Python :
     * we write == to test an equality ;
    * the sequence "While != 13" means "While p is different from 13".

Scratch : We start from p = 0, we try the equality for q varying from 0 to 12. We add 1 to p, we try again from q = 0 to q = 12. We continue the same process until
p = 12.

Algobox : in the Algobox program, it is necessary to define beforehand the variables p and q. To show the answers, we'll be careful to add spaces, for the answer to be readable.

Extension : The famous swiss mathematician Leonhard Euler (1707-1783) has affirmed : "635 318 657 is the smallest integer which can be written in two different ways as a sum of two fourth powers of integers". Which are those two ways ?

Solution (Python) : we want to solve the equation :
p + q = 635 318 657 where p and q are integers. We restraint the range of research of solutions to : [0 ; 160[ x [0 ; 160[.
The integers p and q playing symmetrical roles, we search all the couples (p ; q) with p ≤ q.

     5) Cubic root

In the same way that we define the square root of a positive real number a (which is the positive number which, when squared, gives a) we define the cubic root of a number a, which is the number, noted ³a, such that its cube gives a.

     Method : we're going to use a scanning method. We start from an initial value x which approaches the searched value from below, and we calculate x³. If it is greater than a, we stop, otherwise we add a quantity to x, until we find a greater value than a.

     Programs :

     Python : we define the function cubicroot(x) with two arguments. The first one, a, is the number of which we want to calculate an approached value of the cubic root ; the second x₀, is the starting value of the algorithm.

>>> cubicroot(2,1)

     Scratch : at the beginning, we ask the user to give a value of a. We then start from the value x = 0 (default value which we could change if necessary in the program).
     The rest is identical to the Python program : we calculate the cube of x and we test if x³ > a. If it is the case, the program gives the value of x, if not, it adds 0,001 to x and it starts again.

     Algobox : we define the variables a and x beforehand. The variable a is affected during the execution. We give 0 to the variable x.
    Like in the other programs, while x³ is inferior or equal to the real a, the variable x is incremented by 0,0001.

     Extension : Isaac Newton (1643-1727) has invented a general method for solving equations that we call "Newton's method" : to solve the equation x³ = we consider the function :
f : x x³ - a .
       We start from an approximation of its root u , that we try to improve by the following way : from the point (u; f(u)) of graphic of f, we draw the tangent (T) to the curve, and we assimilate the curve to its tangent to deduce a new approximation of the root.
        This new value will be the abscissa of the intersection of (T) with the (Ox) axis. We call it u+ ₁ .

       Execution : the slope of the tangent (T) is f ' (uⱼ) = 3 uⱼ ² , derivative of  f in uⱼ .
      The sequence of finer and finer approximations will be obtained starting from u₀ , a fixed number (if possible relatively close to a solution : in the program "newton" , we'll take by default u₀ = 1) and from the relation of induction :
uⱼ + ₁ = (uⱼ - f(u)) / f ' (u) which, for
f (x) = x³ - a , gives : uⱼ + ₁ = (2 / 3) uⱼ + a uⱼ ².

>>> newton(2,20)

4) Primality test

It is important in number theory to know if an integer is prime or if it's not. For this, we use what we call a "Primality test".

Solution : We always decide that 1 is not prime. An integer superior or equal to 2 is prime if it has no divisor other than 1 and itself.

To know if a number is prime or not, it is enough to test its divisibility by each of the prime integers inferior or equal to its square root.

Since there is no simple formula to have a list of primes, we test if the number is divisible by 2 and by all the odd numbers inferior or equal to its square root.

Extension : At the beginning of the 17th century, Pierre de Fermat states his "Small theorem" :

"If an integer N is prime, then, for all integer a non multiple of N, the remainder of the euclidean division of a^(N-1) by N equals to 1".

The reciprocal of this theorem is false : if we take the integer 1729, the remainder of the division of 2^1728 by 1729 is 1, but 1729 is not prime (1729 = 7 x 13 x 19).

We can therefore construct, from this property, a test which eliminates a few non prime numbers, but which does not guarantee at 100% that a number is prime.

We let you program this test which could show, for example :

>>> primfermat(2001)
'il est possible que N soit premier'
>>> primfermat(1623)
(1623, 'non premier')

3) Monty Hall problem

The television game takes place in front of three identical doors. They have placed a car behind one of them, and a goat behind one of the other doors.
     The candidate the chooses one door and goes in front of it.
     The presenter opens then one of the other two doors, behind which there is the goat, and he asks the candidate :
     "Would you like to change your choice ?"
     The candidate then has two possibilities :
          * either he opens the door he had first chosen ;
          * or he opens the other door (which has not yet been opened).
Which is the best strategy for the candidate ?

Cultural complement : this television game has really existed in the United States in the 1970. The candidate went away with a beautiful car, with nothing or with a beautiful goat. The probabilistic paradox associated to this game is known as the "Monty Hall problem" (Monty Hall was the presenter of the game).

The programs : a probabilistic reasoning may give the solution. Without such a reasoning, we can "Make experiments". With Python, we have access to very large samples. We can for example play the program "thegoat" hereafter ten million times :
(n = 10 000 000).

>>> thegoat(10000000)

Extension : Imagine a new version of the game, with four doors, a car behind one of them, donkeys behind the others. The presenter plays the same role than in the previous version.
      Should the candidate change his first choice ?

2) Ellipse

An ellipse is given by its center I, the length a of its great axis and that of b, its small axis.
When the axes are parallel to those of x and y, it's the set of points (xM ; yM) such that :
xM = xI + a cos t
yM = yI + b sin t
where t describes the interval [0 ; 360[ if it is expressed in degrees, [0 ; 2π[ if it is expressed in radians. We ask to program the drawing of this ellipse.

1) Flocon de Von Koch

En deux minutes, le programme dessine ceci :

Aucun commentaire:

Enregistrer un commentaire

La parole est à vous :)