# Matemática Discreta
###### Rafael Barsotti

###### Problem 1)
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

###### Esse problema foi fácil devido a clareza do problema e o baixo consumo computacional necessário. Assim mesmo com um algoritimo não tão eficiente, utilizando a função módulo por exemplo foi possível calcular a soma de todos os múltiplos de 3 ou 5 menores que 1000


```python
def mult_3_5(n):
    s = 0
    for i in range(n):
        if i%3 == 0 or i%5 == 0:
            s = s + i
    print("A soma de todos os números naturais múltiplos de 3 ou de 5 menores que {} é {}".format(n,s))
```


```python
mult_3_5(10**3)
```

    A soma de todos os números naturais múltiplos de 3 ou de 5 menores que 1000 é 233168


###### Problem 9)

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

###### Essa questão basta perceber que se você tentar escrever um algoritimo com 3 loops, para testar todos os casos e escrever todos os números pitagóricos e selecionar aquele que a soma é 1000 fica muito custoso computacionalmente, mas percebendo que dados a e b podemos calcular o c correspondente a complexidade cai de O(n3) para O(n2)


```python
def pythagorean_triplet():
    for a in range(1, 1000):
         for b in range(a, 1000):
            c = 1000 - a - b
            if c > 0:
                if c*c == a*a + b*b:
                    print("Os números pitagóricos são (a,b,c) = {} e seu produto é {}".format((a,b,c),a*b*c))
```


```python
pythagorean_triplet()
```

    Os números pitagóricos são (a,b,c) = (200, 375, 425) e seu produto é 31875000


###### Problem 10)
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

###### Esse problema é bem interessante e forma a base para quase todos os outros relacionados a números primos no project euler. Num primeiro momento tentei resolve-lo da mesma forma que resolvi a questão 1, com a modificação de que fosse testado o módulo como todos os números anteriores para verificar se o número era prim ou não. Porém essa solução era ineficente demais para lidar a dimensão desse problema. Então em vez de fazer o algoritimo olhando para trás, fiz ele olhando para frente, isto é, para cada número elimino todos os seus múltiplos menores que 2 milhões. (Sieve de Erasthoetenes)


```python
def sum_primes(n):
    s_p = 0
    sieve = [1] * n
    for p in range(2, n):
        if sieve[p] == 1:
            s_p += p
            for i in range(p*p, n, p):
                sieve[i] = False
    print("A soma de todos os números primos até {} é {}".format(n,s_p))
```


```python
n = 2*10**6
sum_primes(n)
```

    A soma de todos os números primos até 2000000 é 142913828922


###### Problem 13)
Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

###### Esse problema é relativamente simples, basta importarmos o número, quebra-lo em uma matriz onde cada casa é um dígito, depoi somamos todos os elementos dessa matriz e por último pegamos o valor da soma e novamente quebramos em uma lista onde retiramos os elementos de índice menor ou igual a 10.


```python
file = open('/home/nbuser/Number.txt', 'r')
text = file.read()
text = text.replace("\n","")

def palindrome(x):
    x = str(x)
    l = []
    palindrome = ''
    for i in x:
        l.append(i)
    l.reverse()
    for i in l:
        palindrome = palindrome+i
    return int(palindrome)

def sum_number_digits(text):
    s = 0
    s_10 = []
    for i in text:
        s += int(i)
    for i in range(10):
        n = palindrome[i]
        s_10.append(n)
    print("Os últimos 10 dígitos da soma são {}".format(s_10))
```


```python
sum_number_digits(text)
```

    Os últimos 10 dígitos da soma são 5537376230


###### Problem 20)

n! means n × (n − 1) × ... × 3 × 2 × 1

For example, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800,

and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

###### Para resolver esse problema precisei apenas criar uma função que calcula o fatorial de um n qualquer, que mesmo se foses implementado recursivamente dado a natureza linear da recursão ainda seria rápido, para então implementar uma função que recebe um número e conta seus digítos. Para fazer isso basta quebrar o número em um array onde cada elemento corresponde a um dígito e depois fazer a soma de todos os elementos do mesmo. Dado a linearidade de ambos os algoritimos é possível calcular a soma dos digítos de fatoriais bastante grande e uma vez que eles superem o tamnho reservado para "int" podemos usar "double int" etc...


```python
def n_factorial(n):
    factorial = 1
    for i in range(1,n+1):
        factorial = factorial * i
    return factorial

def sum_digits(x):
    x = str(x)
    s = 0
    for i in x:
        s += int(i)
    print("O fatorial de n é {}, e a soma dos seus digitos é {}".format(x,s))
```


```python
sum_digits(n_factorial(100))
```

    O fatorial de n é 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000, e a soma dos seus digitos é 648


##### Problem 25)
What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

###### Esse problema também pode ser quebrado em duas partes, na primeira precisamos implementar uma função que gere a sequência de números fibonacci prestando atenção para usarmos "memoização" e não uma recursão "naive" que teria um custo exponencial se tornando inviável calcular o vigésimo fibonacci por exemplo. Implementado o fibonacci basta fazer uma função que conte o número de dígitos de um número, que semelhante ao do problem anterior pode ser quebrado em um array de dígitos e depois basta descobrirmos o tamanho do array.


```python
def number_of_digits(x):
    x = str(x)
    s = 0
    for i in x:
        s += 1
    return s
    
def fibonacci_n_digits(n):
    x0 = 1
    x1 = 1
    fib = 0
    index = 2
    while number_of_digits(fib) < n:
        fib = x1 + x0
        x0 = x1 
        x1 = fib
        index += 1
    print("O índice do primeiro número da sequência de fibonacci a ter mil digitos é {}".format(index))
```


```python
fibonacci_n_digits(1000)
```

    O índice do primeiro número da sequência de fibonacci a ter mil digitos é 4782


##### Problem 36)
The decimal number, 585 = 1001001001(binary), is palindromic in both bases.
Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.
(Please note that the palindromic number, in either base, may not include leading zeros.)

###### Esse problema foi quebrado em duas partes, primeiro montamos uma função capaz de gerar o palíndromo de uma sequência de dígitos ou caractéres, onde dado um número ou uma palavra basta quebra-la em um array e depois re-escrever esse array lendo o índice de trás para frente. Depois precisamos criar uma função capaz de transformar um número em sua forma decimal para sua froma binária, e agora só precisamos iterar todos os números menores que 1 milhão para calcular o palíndromo da sua representação decimal e binária, e se ambas forem respectivamente iguais, basta aumentar aumentar o contador. Novamente, dado a complexidade linear do algoritimo não tive problemas com performance


```python
def palindrome(x):
    x = str(x)
    l = []
    palindrome = ''
    for i in x:
        l.append(i)
    l.reverse()
    for i in l:
        palindrome = palindrome+i
    return int(palindrome)

def decimal_to_binary(x):
    x = bin(x)
    x = x[2:]
    x = int(x)
    return int(x)

def sum_palindromes(n):
    s = 0
    for i in range(n+1):
        number_decimal = i
        number_binary = decimal_to_binary(number_decimal)
        palindrome_decimal = palindrome(number_decimal)
        palindrome_binary = palindrome(number_binary)
        if number_decimal == palindrome_decimal and number_binary == palindrome_binary:
            s = s + number_decimal
    print("A soma de todos os palíndromos em decimal e binário menores do que {} é {}".format(n,s))
```


```python
sum_palindromes(10**6)
```

    A soma de todos os palíndromos em decimal e binário menores do que 1000000 é 872187


###### Problem 48)
The series, $1^1 + 2^2 + 3^3 + ... + 10^{10} = 10405071317$.

Find the last ten digits of the series, $1^1 + 2^2 + 3^3 + ... + 1000^{1000}$.

###### Nesse problema primeiro precisamos calcular o resultado do somatório, o que é trivial (computacionalmente), depois implementamos uma função capaz de receber um número e fazer a soma dos seus últimos 10 dígitos, para isso basta pegarmos o palíndromo do número, quebra-lo em um array e depois somar os elementos de i == 0 até i == 10.


```python
def series(x):
    s = 0
    for i in range(x+1):
        ith = i**i
        s += ith
    return s

def last_n_digits(s,n):
    n = n-1 
    s = str(s)
    l = []
    last_n_digits = ''
    for i in s:
        l.append(i)
    l.reverse()
    l = l[0:n+1]
    l.reverse()
    for i in l:
        last_n_digits = last_n_digits+i
    last_n_digits = int(last_n_digits)
    print("Os últimos {} digitos da série são {}".format(n+1,last_n_digits))
```


```python
last_n_digits(series(1000) - 1,10)
```

    Os últimos 10 digitos da série são 9110846700


###### Problem 52)

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.
Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

###### Nesse problema primeiro implementamos uma função que recebe uma lista de n números e testa se todos tem o mesmo dígito. (Para esse problema específico o tamanho da lista será sempre dois mas implementei uma forma mais geral). Munidos dessa função e como queremos o menor número (não trivial), basta fazermos um "while" onde a condição é que enquanto os números de n forem diferentes de 2n, 3n, 4n, 5n e 6n teste o sucessor de n


```python
def same_digits(a):
    l = []
    for i in a:
        i = [int(i) for i in str(i)]
        i = set(i)
        l.append(i)
    set_0 = l[0]
    size = len(l)
    count = 0
    for i in l:
        if set_0 == i:
            count += 1
    if count == size:
        return True
    else:
        return False

def smallest_x():
    i = 3
    a = [1,2]
    while same_digits(a) == False:
        i +=1
        x2 = 2*i
        x3 = 3*i
        x4 = 4*i
        x5 = 5*i
        x6 = 6*i
        a = [x2,x3,x4,x5,x6]
    print("O menor número tal que 2x,3x,4x,5x,6x contém os mesmos dígitos é {}".format(i))
```


```python
smallest_x()
```

    O menor número tal que 2x,3x,4x,5x,6x contém os mesmos dígitos é 142857


###### Problem 104)
Given that $F_k$ is the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, find k.

###### Esse problema foi o de maior número que eu fiz o project euler e precisou ser quebrado em várias partes. Primeiro precisamos de uma função booleana que identifique se um número qual quer é pandigital ou não depois precisamos de duas funções que peguem os 10 primeiros e últimos dígitos de um número e por último precisamos de uma função que calcule a sequência fibonacci. Munido dessas funções basta iterarmos nos números da sequência fibonacci até que um satisfaça a condição de ter os 10 primeiros e últimos dígitos pandigitais. Apesar dos algoritimos não serem tão complexos, devido ao tamanho grande do número fibonacci que apresenta essa característica precisamos armazena-lo com double int. (Esse foi o problema de maior complexidade no ranking do project euler que eu já resolvi)


```python
def is_pandigital(x):
    x = [int(i) for i in str(x)]
    x = set(x)
    a = {1,2,3,4,5,6,7,8,9}
    if x == a:
        return True
    else:
        return False
    
def first_10_digits(x):
    x = [str(i) for i in str(x)]
    first_10_digits = ''
    for i in x[0:10]:
        first_10_digits = first_10_digits+i
    return int(first_10_digits)

def last_10_digits(x):
    x = [str(i) for i in str(x)]
    x.reverse()
    last_10_digits = ''
    for i in x[0:10]:
        last_10_digits = last_10_digits+i
    return int(last_10_digits)

def find_k():
    x0 = 1
    x1 = 1
    fib = 0
    while is_pandigital(first_10_digits(fib)) == False or is_pandigital(last_10_digits(fib)) == False:
        fib = x1 + x0
        x0 = x1
        x1 = fib
    return fib
    print("O {}ésimo número da sequência fibonacci".format(fib))
```


```python
find_k()
```

    O 329468ésimo número da sequência fibonacci


###### Problem 80)
It is well known that if the square root of a natural number is not an integer, then it is irrational. The decimal expansion of such square roots is infinite without any repeating pattern at all.

The square root of two is 1.41421356237309504880..., and the digital sum of the first one hundred decimal digits is 475.

For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.

###### Esse problema foi o primeiro onde utilizei funções de alguma biblioteca do python, sendo uma função para calcular a raíz quadrade de um número (Poderia ter implementado o método de Newton mas não vi necessidade) e uma para utilizar mais casas decimais em um número float. Com essas funções como base, implementei uma função que calcula se a raíz de um número é racional ou irracional e uma outra função que calcula a soma dos 100 primeiros digítos após a casa decimal. Agora basta iterar para os números naturais entre 1 e 100 e testar se sua raíz é racional ou não e se for irracional acumular a soma de seus 100 primeiros dígitos decimais. O maior problema nessa questão é sem dúvida a aproximação das 100 casas decimais, pois precisamos de uma biblioteca mais baixo nível que forneça essa aproximação


```python
from sympy import sqrt
    
def sqrt_is_rational(x):
    x = str(x)
    dot = x.find('.')
    s = 0
    for i in x[dot+1:]:
        s += int(i)
    if s == 0:
        return True
    else:
        return False
    
def sum_100_digits(x):
    x = str(x)
    dot = x.find('.')
    s = 0
    for i in x[dot+1:]:
        s += int(i)
    return s

def sum_sqrt_irrational(n):
    t = 0
    for i in range(n+1):
        sqrti = sqrt(i).evalf(101)
        if sqrt_is_rational(sqrti) == False:
            t += sum_100_digits(sqrti)
    print("O total da soma dos primeiros 100 dígitos das raízes de todos os números naturais menores que {} é {}".format(n,t))
```


```python
sum_sqrt_irrational(100)
```

    O total da soma dos primeiros 100 dígitos das raízes de todos os números naturais menores que 100 é 40886


###### Problem 92)
A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

44 → 32 → 13 → 10 → 1 → 1

85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

###### Esse problema me lembrou inicialmente ao problema da conjectura de Collatz, e apesar de eu não saber resolve-lo analíticamente, computacionalmente é bem menos complicado. Precisamos de três funções, uma que dado um número calcula o próximo da sequência, outra função que dado um número calcula a sequência até o momento que ela entra num loop seja em 1, 89 ou outro número, e depois basta iterarmos nos números menores que 10 milhões, gerarmos a sequência partindo desse número e verificarmos se ela de fato chega a 1 ou 89 e se sim incrementarmos o nosso contador.


```python
def next_number(x):
    x = str(x)
    next_number = 0
    for i in x:
        square_of_digit = int(i)**2
        next_number += square_of_digit
    return next_number

def seq(startingpoint):
    l = []
    i = startingpoint
    while i not in l and 89 not in l:
        l.append(i)
        i = next_number(i)
    return l

def starting_numbers_89(n):
    c = 0
    for i in range(1,n+1):
        if 89 in seq(i):
            c += 1
    print("O número de sequências que atingem 89 com valor inicial menor do que {} é {}".format(n,c))
```


```python
starting_numbers_89(10**7)
```

    O número de sequências que atingem 89 com valor inicial menor do que 10000000 é 8581146


###### Problem 74)

The number 145 is well known for the property that the sum of the factorial of its digits is equal to 145:

1! + 4! + 5! = 1 + 24 + 120 = 145

Perhaps less well known is 169, in that it produces the longest chain of numbers that link back to 169; it turns out that there are only three such loops that exist:

169 → 363601 → 1454 → 169

871 → 45361 → 871

872 → 45362 → 872

It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,

69 → 363600 → 1454 → 169 → 363601 (→ 1454)

78 → 45360 → 871 → 45361 (→ 871)

540 → 145 (→ 145)

Starting with 69 produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.

How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?

###### Esse problema também é de sequências de números porém apesar de ele vir antes do anterior na lista do project euler, eu achei ele mais difíficl. Mas a ideia em si é reutilizar a função fatorial que já implementamos, depois reutilizar a função next number modificando a regra para calcular a soma dos fatoriais dos dígitos e depois podemos reutilizar a função que gera a sequência de números apartir de um n. Depois basta iterarmos nos números menores que 1 milhão e incrementarmos o contador com o tamanho da maio sequência toda vez que o tamanho do termo seguinte for maior do que outro que já passamos. 

###### Esse problema é importante do ponto vista computacional por que no caso da minha solução ele mostra as vantagens de se modularizar bem o seu código e reaproveita-lo depois. Assim qualquer problema desse estilo agora cai no mesmo tipo de solução onde o código com pouquíssimas alterações resolve um problema aparentemente distinto.


```python
def factorial(x):
    factorial = 1
    for i in range(1,x+1):
        factorial = factorial*i
    return factorial

def next_number(x):
    x = str(x)
    next_number = 0
    for i in x:
        factorial_of_digit = factorial(int(i)) 
        next_number += factorial_of_digit
    return next_number

def seq(startingpoint):
    l = []
    i = startingpoint
    while i not in l and len(l) <= 60:
        l.append(i)
        i = next_number(i)
    return l

def seq_60(n):
    c = 0
    for i in range(1,n+1):
        length = len(seq(i))
        if length == 60:
            c += 1
    print("O número de sequências com 60 termos não repetidos com valor inicial menor do que {} é {}".format(n,c))
```


```python
seq_60(1000000)
```

    O número de sequências com 60 termos não repetidos com valor inicial menor do que 1000000 é 402


###### Problem 81)
Find the minimal path sum, in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by only moving right and down.

###### Esse problema é uma questão clássica de programação dinâmica de estrurua de dados e algoritimos, onde o truque é quebrar o caminho em subcaminhos ótimos. O seguinte vídeo explica bem a ideia :
https://www.youtube.com/watch?v=lBRtnuxg-gU

###### Basicamente, resolvemos o caminho passo a passo pegando sempre a menor soma possível dado o passo anterior assim o final temos uma matriz onde o elemento máximo do lado direito da matriz já representa a soma total. De todos os problemas que resolvi esse sem dúvida é o que requer melhor manejo computacional, para trabalharmos com a matriz e para termos a sacada de que o problema precisa de programção dinâmica devido a complexidade combinatorial do problema impossibilitando uma solução força bruta para matrizes mesmo pequenas


```python
import numpy as np
file = "/home/nbuser/Problem_81.csv"
m = np.loadtxt(file,dtype = 'int',delimiter=',')
```


```python
size = len(matrix)

def minimal_path():
    for i in range(1, size):
        matrix[i][0] += matrix[0][i-1]
        for j in range(1, size):
            matrix[i][j] += min(matrix[i-1][j], matrix[i][j-1])
    for i in range(1,size):
        for j in range(1,size):
            s += matrix[i][j]      
    print("A soma do menor caminho é {}".format(s))
```


```python
minimal_path()
```

    A soma do menor caminho é 427337


###### Problem 31)

How many different ways can £2 be made using any number of coins?

###### Esse problema é análogo ao anterior, no sentido que se formos fazer todas as combinações de trocos para depois vermos quais somam 2 libras se torna inviável computacionalmente. Porém basta perceber que o número total de trocados é dados pelo número total de trocados utilizando uma moeda i somado ao número total de trocados não utilizando a moeda i. Porém como essa recorrência tem complexidade computacional exponencial (Semelhante ao Fibonacci Naive) onde vários cálculos são feitos redundantemente, basta armazernamos o valor na lista sol e depois somarmos.


```python
def change():
    coins = [1, 2, 5, 10, 20, 50, 100, 200]
    sol = [1] + [0]*200
    for coin in coins:
        for i in range(coin, 201):
            sol[i] = sol[i] + sol[i-coin]
    solv = sol[200]
    print("O número total de trocados de 2 libras é {}".format(solv))
```


```python
change()
```

    O número total de trocados de 2 libras é 73682


###### Problem 76)

How many different ways can one hundred be written as a sum of at least two positive integers?

###### Esse problema e analogo ao das moedas, com a alteracao que agora as moedas sao todos os numeros menores que n 


```python
def sum_ways(n):
    coins = range(1, n)
    sol = [1] + [0]*n
    for i in coins:
        for j in range(i, n+1):
            sol[j] = sol[j] + sol[j-n]
    solv = sol[n]
    print("O número total de possibilidade de escrever {} é {}".format(n,solv))
```


```python
sum_ways(100)
```

    O número total de possibilidade de escrever 100 é 190569291


27f4574a043ccba87371f9d4eb4a4e17db745b64
ipynb
Jupyter Notebook
Discrete Mathematics/Discrete Mathematics.ipynb
rbarsotti/Emap
9d0cac683e1c02fc802e2099680772179118512f
MIT
Discrete Mathematics/Discrete Mathematics.ipynb
rbarsotti/Emap
9d0cac683e1c02fc802e2099680772179118512f
MIT
Discrete Mathematics/Discrete Mathematics.ipynb
rbarsotti/Emap
9d0cac683e1c02fc802e2099680772179118512f
MIT
Qwen/Qwen-72B
1. YES
2. YES