Trabalho na Ideia #164

Um Script para Gerar e Testar Fórmulas para Números Primos

Na Ideia #164, foi proposto gerar expressões aleatórias e testar se estas são capazes de gerar os números primos. Aqui, eu apresento um destes scripts feito em Python. Também produzi um executável que pode ser útil. Você pode baixá-lo no fim desta página.

As expressões algébricas que ele gera são feitas de polinômios inteiros de n, que são unidos por operações como soma, subtração, multiplicação ou divisão. Parênteses, até mesmo parênteses aninhados, adicionam mais possibilidades. Sinais positivos ou negativos são também gerados aleatóriamente. 

Naturalmente, testar todos os primos seria impraticável, então o programa testa apenas os primeiros 9592 números primos. É desenhado para parar de testar uma expressão assim que esta falha a gerar os primos, e passar para a próxima, o que torna a testagem um processo bastante rápido. 


Aqui estão os parâmetros de execução padrão do programa, mais está livre para customização no script Python:


Note que as possibilidades são vastas. Não posso nem começar a calcular as probabilidades. Ele pode encontrar a expressão certa nos próximos 5 minutos, ou pode nunca encontrá-la. Isto é por que isto não é nada diferente de uma loteria. Exceto talvez que é uma loteria pelo avanço da Ciência. A ideia é só que você sente para trabalhar e enquanto isto, deixe o programa rodando no fundo. Pelo menos a gente se sente bem de saber que o computador está trabalhando para você tentando resolver este quebra-cabeças antigo.

A cada 5000 expressões testadas ele printa na tela do programa só para avisá-lo de que o programa está vivo. 

Se ele encontrar uma expressão, vai escrever "Eureka" na tela e escrever a expressão, além de registrá-la no arquivo de saída Prime_Function.txt para uma investigação posterior. Isto significa que de tempos em tempos, cheque este arquivo para ver se algo surgiu. Uma expressão registrada no arquivo significa que é uma candidata, isto não garante que esta possa gerar todos os primos, apenas os primeiros 9592. Isto em si mesmo já é um feito e tanto. Testes subsequentes precisam ser realizados com um número maior de primos em tal caso. 

Certamente espero que a parte do código que registra a expressão no arquivo esteja funcionando. Eu nunca encontrei uma expressão, por razões óbvias, para testar esta porção do código. O programa é fundamentado no uso de Eval(), o que algumas pessoas dizem ser pouco confiável, mas honestamente não tive grandes problemas quando esta é cuidadosamente estruturada em um bloco try-except.


A tabela de números primos, primes.txt, deve sempre estar presente no mesmo local do script ou executável ou um erro irá ocorrer. 

Questões de Performance

Rodando testes bastante simples de performance no script, determinei que rodá-lo não afeta significativamente a performance do computador e ele pode ser usado com segurança no plano de fundo. Você pode perceber contudo problemas de performance se rodar atividades que requerem muito CPU, como edição de vídeo, renderizar imagens, processamento intenso de dados, mas isto seria verdade para qualquer tipo de multi-tasking. No meu computador, um velho Intel Core i7-4710HQ CPU @2,50GHz, o programa sozinho consumiu 15% do CPU total, com todas as tarefas nunca excedendo as coisas acima de 65% da potência da CPU. 

O Código Completo

random_attempt_v4.py

# This script generates a randomized algebraic expression and evaluates it, checking if

# the first 9592 prime numbers were produced by the expression.


# The expression is rational, formed by integer polynomials, with random brackets.


# If the expression did indeed produced the prime numbers, it is registered for further

# studies in the output file Prime_Function.txt.


# Note that being able to reproduce the first 9592 prime numbers makes it a Prime Number

# Function candidate, nothing more. There are plenty other prime numbers out there.


# Every 5000 attempts it outputs in the screen the current screen, otherwise it is a very

# silent program, designed to be run in the background. It also indicates in the screen

# if it by chance ran into a Prime Number expression.


# Note that the possibities are vast. It could find an expression in  the next 5 min,

# it could take the age of the Universe, or it even may never find it because it is

# impossible.



import math

import random


# Execution Parameters

max_number_of_terms = +25

max_numeric_term = +1000000000

min_literal_exponent = -50

max_literal_exponent = +50

max_literal_coefficient = +1000000000

number_of_attempts = +1000000000


print("PROGRAM STARTING..")


# Seeds the pseudo-random number generator:

random.seed()


# This function sorts out if the term is going to be numeric (a constant) or literal (a polynomial of n).

def integer_or_numeric_term():

    # type_term = 0 --> Numeric

    # type_term = 1 --> Literal


    random_float = random.random()


    if random_float <= 0.5:

        type_term = 0

    if random_float > 0.5:

        type_term = 1


    return type_term


# This function sorts if a sign will be positive or negative.

def sort_sign():

    random_float = random.random()


    if random_float <= 0.5:

        sign_str = '-'

    if random_float > 0.5:

        sign_str = '+'


    return sign_str


# This function generates a randomized expression that could be the Prime Function Generator:

def genExpression():


    number_of_terms = random.randint(2, max_number_of_terms)


    collected_terms = []

    for item in range(number_of_terms):


        type_term = integer_or_numeric_term()


        # Numeric Term

        if type_term == 0:

            sign_str = sort_sign()

            coefficient = random.randint(0, max_numeric_term+1)

            coefficient_str = '{:20d}'.format(coefficient)

            #coefficient_str = '{:d}'.format(coefficient)

            term_str = '(' + sign_str + coefficient_str + '*n**( +0))'


        # Literal Term

        if type_term == 1:

            sign_str = sort_sign()

            coefficient = random.randint(0, max_literal_coefficient+1)

            coefficient_str = '{:20d}'.format(coefficient)

            #coefficient_str = '{:d}'.format(coefficient)

            exponent = random.randint(min_literal_exponent, max_literal_exponent+1)

            exponent_str = '{:+3d}'.format(exponent)

            term_str = '(' + sign_str + coefficient_str + '*n**(' + exponent_str + '))'


        collected_terms.append(term_str)


    number_of_operations = number_of_terms-1


    # Collects the operations (+,-,*,/) betweeen terms, all generated randomly.

    operations = []

    for operation in range(number_of_operations):

        random_float = random.random()


        if random_float < 0.25:

            operation_str = '+'

        if random_float >= 0.25 and random_float < 0.5:

            operation_str = '-'

        if random_float >= 0.5 and random_float < 0.75:

            operation_str = '*'

        if random_float > 0.75:

            operation_str = '/'


        operations.append(operation_str)


    # Assembles the expression:

    expression = ''

    brackets_opened = 0

    for item in range(number_of_operations):


        open_bracket = ''

        closed_bracket = ''


        # The possibility of a bracket to open:

        random_float = random.random()


        if random_float <= (0.5):

            open_bracket = '('

            brackets_opened = brackets_opened + 1

        else:

            bracket = ''


        # The possibility of a bracket to close:

        random_float = random.random()


        if random_float <= (0.5) and (brackets_opened > 0):

            closed_bracket = ')'

            brackets_opened = brackets_opened - 1

        else:

            bracket = ''


        expression = expression + open_bracket + collected_terms[item] + closed_bracket + operations[item]


    # Adds the final term:

    expression = expression + collected_terms[item+1]


    # Closes any un-closed bracket:

    while brackets_opened > 0:

        expression = expression + ')'

        brackets_opened = brackets_opened - 1


    return expression


# Evaluate expression:

# Opens output file:

resultsFile = open('Prime_Function.txt', 'a')


# Loads up prime numbers table:

with open('primes.txt', 'r') as primesFile:

    content = primesFile.readlines()


# Clears input of garbage:

primes = []

for item in content:

    prime = item.strip('\n')

    primes.append(int(prime))


# Attempts to find an expression for the prime numbers:

for run in range(number_of_attempts):

    expression = genExpression()


    #print(run ,  ':',  expression)

    if (run % 5000 == 0) : print("RUN: ", run)


    # Tries, for every prime, to see if there is a match, and stops trying that expression in negative case:

    is_possible_p_function = True

    for integer in range(len(primes)):


        n = integer+1


        if is_possible_p_function == True:

            try:

                expression_value = eval(expression)


                if expression_value != primes[integer]:

                    is_possible_p_function = False

                    #print('Not prime function.')

            except:

                #print('Error: EVAL() failed.')

                is_possible_p_function = False

                #print('Not prime function')


    if is_possible_p_function == True:

        print('Eureka!!')

        print(expression)


        #Writes to file:

        resultsFile.write(expression)

        resultsFile.write('\n')


resultsFile.close()


print("END PROGRAM..")


# Note:

# The genExpression() function sometimes generate expressions with 0 on the denominator.

# This is catched by the try-except block of Eval. They cannot be evaluated.

# It was easier to simply ignore the problem.


ARQUIVOS PARA DOWNLOAD

Prime Function Project Files

BANNER IMAGE CREDITS: ESA/Hubble & NASA, A. Filippenko, R. Jansen 

Want to know more about this image? Follow this external link.