Número Ulam - Ulam number

Em matemática , os números Ulam compreendem uma sequência inteira concebida e nomeada em homenagem a Stanislaw Ulam , que a introduziu em 1964. A sequência Ulam padrão (a sequência (1, 2) -Ulam) começa com U 1  = 1 e U 2  = 2 Então, para n  > 2, U n é definido como o menor inteiro que é a soma de dois termos anteriores distintos exatamente de uma maneira e maior do que todos os termos anteriores.

Exemplos

Como consequência da definição, 3 é um número Ulam (1 + 2); e 4 é um número Ulam (1 + 3). (Aqui 2 + 2 não é uma segunda representação de 4, porque os termos anteriores devem ser distintos.) O inteiro 5 não é um número Ulam, porque 5 = 1 + 4 = 2 + 3. Os primeiros termos são

1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 82, 87, 97, 99, 102, 106, 114, 126, 131, 138, 145, 148, 155, 175, 177, 180, 182, 189, 197, 206, 209, 219, 221, 236, 238, 241, 243, 253, 258, 260, 273, 282, ... (sequência A002858 no OEIS ).

Existem infinitos números de Ulam. Pois, depois que os primeiros n números na sequência já foram determinados, é sempre possível estender a sequência por mais um elemento: U n −1 + U n é representado exclusivamente como uma soma de dois dos primeiros n números, e pode haver outros números menores que também são representados exclusivamente dessa maneira, de modo que o próximo elemento pode ser escolhido como o menor desses números representáveis ​​de forma única.

Diz-se que Ulam conjeturou que os números têm densidade zero , mas parecem ter uma densidade de aproximadamente 0,07398.

Propriedades

Além de 1 + 2 = 3, qualquer número Ulam subsequente não pode ser a soma de seus dois números Ulam consecutivos anteriores.

Prova: Suponha que para n > 2, U n −1 + U n = U n +1 é a soma necessária de apenas uma maneira, então U n −2 + U n produz uma soma de apenas uma maneira e fica entre U n e U n +1 . Isso contradiz a condição de que U n +1 é o próximo menor número de Ulam.

Para n > 2, quaisquer três números Ulam consecutivos ( U n −1 , U n , U n +1 ) como lados inteiros formarão um triângulo.

Prova: A propriedade anterior afirma que para n > 2, U n −2 + U n ≥ U n + 1 . Consequentemente U n −1 + U n > U n +1 e porque U n −1 < U n < U n +1 a desigualdade do triângulo é satisfeita.

A seqüência de números Ulam forma uma seqüência completa .

Prova: Por definição U n = U j + U k onde j < k < n e é o menor inteiro que é a soma de dois números Ulam menores distintos de exatamente uma maneira. Isso significa que para todo U n  com n > 3, o maior valor que U j pode ter é U n −3 e o maior valor que U k pode ter é U n −1 .
Logo, U n ≤ U n −1 + U n −3 <2 U n −1 e U 1 = 1, U 2 = 2, U 3 = 3. Esta é uma condição suficiente para que os números de Ulam sejam uma sequência completa.

Para cada inteiro n > 1 há sempre pelo menos um número Ulam U j tal que n ≤ U j <2 n .

Prova: Foi provado que existem infinitos números Ulam e eles começam em 1. Portanto, para todo inteiro n > 1 é possível encontrar j tal que U j −1 ≤ n ≤ U j . Da prova acima para n > 3, U j  ≤  U j −1  +  U j −3  <2 U j −1 . Portanto, n  ≤  U j  <  2U j −1  ≤ 2 n . Também para n = 2 e 3, a propriedade é verdadeira por cálculo.

Em qualquer sequência de 5 inteiros positivos consecutivos { i , i + 1, ..., i + 4}, i > 4 pode haver no máximo 2 números Ulam.

Prova: Suponha que a sequência { i , i + 1, ..., i + 4} tenha seu primeiro valor i = U j um número Ulam, então é possível que i + 1 seja o próximo número Ulam U j +1 . Agora considere i + 2, este não pode ser o próximo número Ulam U j +2 porque não é uma soma única de dois termos anteriores. i + 2 = U j +1 + U 1 = U j + U 2 . Um argumento semelhante existe para i + 3 e i + 4.

Desigualdades

Os números Ulam são pseudoaleatórios e muito irregulares para terem limites estreitos. No entanto, a partir das propriedades acima, ou seja, na pior das hipóteses, o próximo número Ulam U n +1 ≤ U n + U n −2 e em quaisquer cinco inteiros positivos consecutivos no máximo dois podem ser números Ulam, pode-se afirmar que

5 / 2 n −7 ≤ U n ≤ N n +1 para n > 0,

onde N n são os números na sequência de vacas de Narayana : 1,1,1,2,3,4,6,9,13,19, ... com a relação de recorrência N n = N n −1 + N n −3 que começa em N 0 .

Estrutura oculta

Foi observado que os primeiros 10 milhões de números de Ulam satisfazem, exceto para os quatro elementos (isso agora foi verificado para os primeiros números de Ulam). Desigualdades desse tipo geralmente são verdadeiras para sequências que exibem alguma forma de periodicidade, mas a sequência de Ulam não parece ser periódica e o fenômeno não é compreendido. Ele pode ser explorado para fazer um cálculo rápido da sequência Ulam (consulte # Links externos ).

Generalizações

A ideia pode ser generalizada como números ( u ,  v ) -Ulam selecionando diferentes valores iniciais ( u ,  v ). Uma sequência de números ( u ,  v ) -Ulam é regular se a sequência de diferenças entre os números consecutivos na sequência for eventualmente periódica. Quando v é um número ímpar maior que três, os números (2,  v ) -Ulam são regulares. Quando v é congruente com 1 (mod 4) e pelo menos cinco, os números (4,  v ) -Ulam são novamente regulares. No entanto, os próprios números de Ulam não parecem ser regulares.

Uma seqüência de números é dita s - aditiva se cada número na seqüência, após os 2 s iniciais da seqüência, tiver exatamente s representações como a soma de dois números anteriores. Assim, os números Ulam e os números ( u ,  v ) -Ulam são sequências 1-aditivas.

Se uma sequência é formada anexando o maior número com uma representação única como uma soma de dois números anteriores, em vez de anexar o menor número exclusivamente representável, então a sequência resultante é a sequência de números de Fibonacci .

Notas

Referências


links externos