.. escape-backslashes
.. default-role:: math

Chapter 6: More advanced exercises
==================================

You will find in this tutorial a collection of more advanced exercises. You
might also want to have a look at the worksheets on "Collatz conjecture",
"Dictionaries and graph theory" and "Strings and the Burrows-Wheeler
transform".

Exercise 6.1
~~~~~~~~~~~~

How many strings of length `n` containing only letters ``a`` and ``b`` but not
containing ``aa`` are there? Compute the value for each `n=1,2,...,10`

.. sagecell

Do you know this sequence?

.. sagecell

Could you find the corresponding entry in the `OEIS <https://oeis.org/>`_

.. sagecell

Exercise 6.2 (Goldbach conjecture)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Verify experimentally the following statement: « For each even integer `n \geq
4`, there exist two prime number `p \geq 2` and `q \geq 2` such that `n = p +
q` ». 

.. sagecell

Up to which value of `n` are you able to verify this conjecture?

.. sagecell

Exercise 6.3
~~~~~~~~~~~~

Does there exist two positive integer numbers `x` and `y` such that `x^2 -
61y^2 = 1` ?

.. sagecell

Exercise 6.4
~~~~~~~~~~~~

Write a function that given positive integers `(p,q,n)` return
the number of solutions in positive integers `(a_1, a_2, \ldots, a_n)`
to the equation

.. MATH::

    \frac{1}{a_1} + \frac{1}{a_2} + \ldots + \frac{1}{a_n} = \frac{p}{q}

How many solutions are there for `(p,q,n) = (13, 12, 3)`?

.. sagecell

A sample of Euler problems
~~~~~~~~~~~~~~~~~~~~~~~~~~

Solve the following Euler problems

- `problem 26 <https://projecteuler.net/problem=26>`_ (decimal expansions)
- `problem 31 <https://projecteuler.net/problem=31>`_ (coin sums)
- `problem 45 <https://projecteuler.net/problem=45>`_ (triangular, pentagonal and hexagonal numbers)
- `problem 46 <https://projecteuler.net/problem=46>`_ (odd composite number that
  can not be written as the sum of a prime and twice a square)
- `problem 50 <https://projecteuler.net/problem=50>`_ (sum of consecutive primes that are primes)