#!/usr/bin/env python
# coding: utf-8

# # Programming with Python
# #### Stefan Güttel, [guettel.com](http://guettel.com)
# 
# 
# ## Lab classes: Loops and conditionals

# **Problem 1.** Write a program that loads one integer $n$, a digit $d$, and two nonnegative integers $a$ and $b$ such that $a > b$ (verify that the input satisfies these conditions) and prints the largest integer $x$ such that:
# 
# 1. $0 \le x \le n$,
# 
# 2. $x$ is a perfect square of some integer (i.e., there exists $y \in \mathbb{Z}$ such that $x = y^2$),
# 
# 3. the last digit of $x$ is $d$,
# 
# 4. the remainder of the division of $x$ by $a$ is equal to $b$.
# 
# If there is no such number, the program has to print an appropriate message.

# **Hints:**
# 
# 1. Verifying the input means checking that $0 \le d \le 9$ and that $a > b \ge 0$. There is no need to check that any of the loaded numbers are integers. This will be handled by the `int` funtion that crashes the program if something other than integer is given.
# 
# 2. Checking that a certain number is a perfect square is not very hard, but there can be far too many candidates. For example, if $n = 1024 = 32^2$, there are only $33$ perfect squares in the set $\{0, 1, \dots, n\}$, but we would have to check all $1025$ nonnegative integers smaller than or equal to $n$.  
#    A better approach is to loop through the possible values of $y$ (from zero to $\lfloor \sqrt{n} \rfloor$), compute $x = y^2$, and then check the conditions 3 and 4.

# **Some running examples**
# 
# Input \#1:
# 
#     n = 73
#     d = 9
#     a = 3
#     b = 1
#     The desired number: 49
# 
# Input \#2:
# 
#     n = 200
#     d = 9
#     a = 3
#     b = 1
#     The desired number: 169
# 
# Input \#3:
# 
#     n = 47
#     d = 9
#     a = 3
#     b = 1
#     No such number exists!

# **Problem 2.** Using the idea from the second hint for the previous problem, write a program that loads an integer $n$ and prints how many integers $x$ there are such that
# 
# * $x$ is a perfect square,
# 
# * $1 < x \le n$,
# 
# * $n$ is divisible by $x$.

# **Problem 3.** Write a program that loads a natural number $n$ and prints in how many ways can $n$ be written as a sum of consecutive natural numbers (including the one-element sum of $n$ alone).
# 
# For example, $15$ can be written as $15$, $7+8$, $4+5+6$, or $1+2+3+4+5$, so the program should print `4`.

# **Hint:** You may use the formula for the sum of the first $n$ natural numbers:
# 
# $$1 + 2 + 3 + \cdots + n = \frac{n}{2}(n+1).$$

# **Problem 4.** Write a program that loads two integers and computes their greatest common divisors using the [Euclid's algorithm](http://en.wikipedia.org/wiki/Euclidean_algorithm) (for example, the one from [MATH10101](http://www.maths.manchester.ac.uk/~mdc/MATH10101.htm#LectureNotes)) and prints it.

# **Problem 5.** Write a program that loads two integers and computes their [lowest common multiplier](http://en.wikipedia.org/wiki/Least_common_multiple).

# **Hint:** The simplest approach comes from the formula:
# $$\operatorname{lcm}(m, n) \operatorname{gcd}(m,n) = |mn|.$$
# Using this is generally not advisable, as $mn$ can be too big for most of the programming languages (while $\operatorname{lcm}(m, n)$ is still small enough). Fortunately  Python doesn't impose a limit on the size of integers, so you can use this here.
# 
# However, do try to avoid computing anything that is bigger than $\operatorname{lcm}(m,n)$ (a hint within a hint: commutativity).

# **Problem 6.** Write a program that loads a natural number and checks if it is a [palindrome](http://en.wikipedia.org/wiki/Palindrome).

# **Hint:** How would you reverse the order of the digits in a number?

# **Problem 7.** Write a program that loads a natural number and checks if its digits come in
# 
# 1. a descending order (for example: $731$, but not $331$ or $713$)?
# 
# 2. a non-increasing order (for example: $731$ or $331$, but not $713$)?

# **Hint:** We know how to read a number digit by digit. So, if we save the previous digit when getting the next one, we shall have both and we'll be able to compare them.

# **Problem 8.** Write a program that loads an integer and prints its
# 
# 1. second digit from the left,
# 
# 2. third digit from the right.
# 
# If the number doesn't have two digits, then its second digit from the left doesn't exist and the program should print an informative message instead of that nonexistent digit. On the other hand, if the number has less than tree digits, its third digit from the right is zero.

# **Problem 9.** Write a program that loads a natural number $n$ and prints Fibonacci numbers $F_0, F_1, \dots, F_n$, defined by
# $$F_0 = 0, \quad F_1 = 1, \quad F_{k+2} = F_{k+1} + F_{k}, \quad k \in \mathbb{N}_0.$$