Skip to content

Instantly share code, notes, and snippets.

@tarsisazevedo
Created July 8, 2011 04:50
Show Gist options
  • Save tarsisazevedo/1071172 to your computer and use it in GitHub Desktop.
Save tarsisazevedo/1071172 to your computer and use it in GitHub Desktop.
euler 12
from unittest import TestCase, main
import math
class TestNumerosTriangulares(TestCase):
def test_numero_28_deve_ter_5_divisores(self):
"""docstring for test_numero_28_deve_ter_5_divisores"""
self.assertEquals(primeiro_numero_triangular_com(divisores=5), 28)
def test_numero_x_deve_ter_500_divisores(self):
"""docstring for test_numero_x_deve_ter_500_divisores"""
self.assertEquals(primeiro_numero_triangular_com(divisores=500), 76576500)
def primeiro_numero_triangular_com(divisores):
divisores_numero = 0
posicao_na_sequencia = 1
while divisores_numero <= divisores:
posicao_na_sequencia += 1
proximo_numero = sum(range(1, posicao_na_sequencia + 1))
numero = int(math.sqrt(proximo_numero))
divisores_numero = len([i for i in range(1, numero + 1 ) if proximo_numero % i == 0]) * 2
return proximo_numero
main()
@tarsisazevedo
Copy link
Author

O @cabello me ajudou nessa solucao, no canal do #cobrateam no irc. Obrigado cara!

ele demonstrou uma propriedade muito interessante:

O numero 28 tem 6 divisores. Se voce tirar a raiz quadrada dele, terá ~5.3, levando em conta só os numeros naturais, teremos 5.

de 1 a 5, o numero 28 tem 3 divisores, 1, 2, 4. Calculando, temos: 1_28, 2_14 e 4*7. Se olharmos com calma, deduzimos que os divisores andam em pares!

Dada esta propriedade, eu posso usar a raiz do numero 76576500, calcular somente seus primeiros 250 divisores e consigo validar que ele é o primeiro numero triangular que tem mais de 500 divisores muito mais rapido! (11 seg)

falei merda @cabello?!

Obrigado mais uma vez cara!

@juanplopes
Copy link

Eu fiz de forma diferente. Sei que existe uma propriedade que diz que

dado que x possa ser fatorado (em fatores primos) como x1^k1 + ... + xm^km

o número x tem exatamente

(k1 + 1) * ... * (km + 1) divisores próprios

Com isso, tenho essa solução: https://github.com/juanplopes/euler/blob/master/0012.boo

Que sai em 0.4s (mas é compilado)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment