O método middle-square é um método para a geração de sequências de números pseudo-aleatórios. Para gerar a seguência, escolha um número de n dígitos e o eleve ao quadrado. Geralmento, isso irá produzir um número de 2n digitos. Caso o quadrado tenha menos de 2n dígitos, acrescentamos zeros na frente até o quadrado atingir 2n dígitos. Após isso selecionamos os n dígitos centrais do quadrado e usamos como o novo número para o próximo termo da sequência.
Por exemplo, se escolhermos o número 44, então \(n=2\) assim esperamos que \(n^2\)produza um número de \(2n =4\) dígitos. Como \(44^2=1936\), selecionamos os n dígitos centrais de \(44^2\) (93) e o elevamos ao quadrado novamente, continuando o ciclo.
Porém se o número for 11, então \(11^2=121\), que tem 3 dígitos. Note que nesse caso, \(2n=4 \neq 3\). Assim, colocaremos zeros na frente de 121 até atingirmos 4 dígitos. Nosso número será 0121. Os n dígitos centrais são 12, e é esse o novo número usado na sequência.
O exemplo completo com o número 11 é:
Square: 0121 Seed: 12
Square: 0144 Seed: 14
Square: 0196 Seed: 19
Square: 0361 Seed: 36
Square: 1296 Seed: 29
Square: 0841 Seed: 84
Square: 7056 Seed: 5
Square: 0025 Seed: 2
Square: 0004 Seed: 0
A partir daí o ciclo se repete com zeros.
Uma função para calcular uma sequência gerada pelo método middle-square para números de dois dígitos é:
def middleSquare2(seed):
numbers_dic = {}
counter = 0
while seed not in numbers_dic.values():
numbers_dic[counter] = seed
counter += 1
square = str(seed * seed).zfill(4)
seed = int(square[1:3])
return numbers_dic
Ela retorna um dicionário onde as chaves são os contadores (número de vezes que o algorítimo foi aplicado) e os valores são os números pseudo-aleatórios gerados.
Por exemplo, se seed = 11:
print(middleSquare2(11))
{0: 11, 1: 12, 2: 14, 3: 19, 4: 36, 5: 29, 6: 84, 7: 5, 8: 2, 9: 0}
O comprimento dos ciclos e os últimos valores das sequências são:
for i in range(0, 100):
a = middleSquare2(i)
max_key = max(list(a.keys()))
print("Number:", i, "Cycle length:", max_key, "Last Value:", a[max_key])
Number: 0 Cycle length: 0 Last Value: 0
Number: 1 Cycle length: 1 Last Value: 0
Number: 2 Cycle length: 1 Last Value: 0
Number: 3 Cycle length: 1 Last Value: 0
Number: 4 Cycle length: 2 Last Value: 0
Number: 5 Cycle length: 2 Last Value: 0
Number: 6 Cycle length: 2 Last Value: 0
Number: 7 Cycle length: 3 Last Value: 0
Number: 8 Cycle length: 3 Last Value: 0
Number: 9 Cycle length: 4 Last Value: 0
Number: 10 Cycle length: 0 Last Value: 10
Number: 11 Cycle length: 9 Last Value: 0
Number: 12 Cycle length: 8 Last Value: 0
Number: 13 Cycle length: 7 Last Value: 0
Number: 14 Cycle length: 7 Last Value: 0
Number: 15 Cycle length: 5 Last Value: 10
Number: 16 Cycle length: 6 Last Value: 0
Number: 17 Cycle length: 6 Last Value: 0
Number: 18 Cycle length: 3 Last Value: 0
Number: 19 Cycle length: 6 Last Value: 0
Number: 20 Cycle length: 2 Last Value: 60
Number: 21 Cycle length: 8 Last Value: 0
Number: 22 Cycle length: 4 Last Value: 10
Number: 23 Cycle length: 4 Last Value: 10
Number: 24 Cycle length: 1 Last Value: 57
Number: 25 Cycle length: 5 Last Value: 0
Number: 26 Cycle length: 5 Last Value: 10
Number: 27 Cycle length: 5 Last Value: 0
Number: 28 Cycle length: 5 Last Value: 0
Number: 29 Cycle length: 4 Last Value: 0
Number: 30 Cycle length: 2 Last Value: 10
Number: 31 Cycle length: 10 Last Value: 0
Number: 32 Cycle length: 2 Last Value: 0
Number: 33 Cycle length: 4 Last Value: 0
Number: 34 Cycle length: 6 Last Value: 10
Number: 35 Cycle length: 5 Last Value: 10
Number: 36 Cycle length: 5 Last Value: 0
Number: 37 Cycle length: 6 Last Value: 0
Number: 38 Cycle length: 8 Last Value: 0
Number: 39 Cycle length: 4 Last Value: 10
Number: 40 Cycle length: 1 Last Value: 60
Number: 41 Cycle length: 6 Last Value: 0
Number: 42 Cycle length: 14 Last Value: 0
Number: 43 Cycle length: 4 Last Value: 0
Number: 44 Cycle length: 7 Last Value: 0
Number: 45 Cycle length: 2 Last Value: 0
Number: 46 Cycle length: 10 Last Value: 0
Number: 47 Cycle length: 3 Last Value: 60
Number: 48 Cycle length: 3 Last Value: 10
Number: 49 Cycle length: 2 Last Value: 60
Number: 50 Cycle length: 0 Last Value: 50
Number: 51 Cycle length: 1 Last Value: 60
Number: 52 Cycle length: 3 Last Value: 10
Number: 53 Cycle length: 3 Last Value: 60
Number: 54 Cycle length: 7 Last Value: 0
Number: 55 Cycle length: 2 Last Value: 0
Number: 56 Cycle length: 8 Last Value: 0
Number: 57 Cycle length: 1 Last Value: 24
Number: 58 Cycle length: 6 Last Value: 0
Number: 59 Cycle length: 4 Last Value: 10
Number: 60 Cycle length: 0 Last Value: 60
Number: 61 Cycle length: 5 Last Value: 0
Number: 62 Cycle length: 4 Last Value: 0
Number: 63 Cycle length: 10 Last Value: 0
Number: 64 Cycle length: 5 Last Value: 0
Number: 65 Cycle length: 5 Last Value: 10
Number: 66 Cycle length: 6 Last Value: 10
Number: 67 Cycle length: 4 Last Value: 10
Number: 68 Cycle length: 5 Last Value: 0
Number: 69 Cycle length: 14 Last Value: 0
Number: 70 Cycle length: 2 Last Value: 10
Number: 71 Cycle length: 3 Last Value: 0
Number: 72 Cycle length: 4 Last Value: 0
Number: 73 Cycle length: 3 Last Value: 0
Number: 74 Cycle length: 4 Last Value: 60
Number: 75 Cycle length: 5 Last Value: 0
Number: 76 Cycle length: 13 Last Value: 0
Number: 77 Cycle length: 12 Last Value: 0
Number: 78 Cycle length: 4 Last Value: 0
Number: 79 Cycle length: 2 Last Value: 57
Number: 80 Cycle length: 2 Last Value: 60
Number: 81 Cycle length: 9 Last Value: 0
Number: 82 Cycle length: 5 Last Value: 0
Number: 83 Cycle length: 6 Last Value: 60
Number: 84 Cycle length: 3 Last Value: 0
Number: 85 Cycle length: 5 Last Value: 10
Number: 86 Cycle length: 5 Last Value: 10
Number: 87 Cycle length: 9 Last Value: 0
Number: 88 Cycle length: 5 Last Value: 60
Number: 89 Cycle length: 12 Last Value: 0
Number: 90 Cycle length: 1 Last Value: 10
Number: 91 Cycle length: 6 Last Value: 0
Number: 92 Cycle length: 11 Last Value: 0
Number: 93 Cycle length: 6 Last Value: 0
Number: 94 Cycle length: 7 Last Value: 60
Number: 95 Cycle length: 2 Last Value: 0
Number: 96 Cycle length: 9 Last Value: 0
Number: 97 Cycle length: 2 Last Value: 60
Number: 98 Cycle length: 1 Last Value: 60
Number: 99 Cycle length: 3 Last Value: 60
(a) 62 números levam a um ciclo de zeros. São eles:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 25, 27, 28, 29, 31, 32, 33, 36, 37, 38, 41, 42, 43, 44, 45, 46, 54, 55, 56, 58, 61, 62, 63, 64, 68, 69, 71, 72, 73, 75, 76, 77, 78, 81, 82, 84, 87, 89, 91, 92, 93, 95, 96]
(b) Há 6 ciclos possíveis. Eles terminam em [0, 10, 60, 57, 50, 24]. Já o ciclo mais longo é de tamanho 14. São eles os ciclos iniciados em 42 e 69
(c) As sequências que gerarão o maior número de elementos distintos antes de se repetir são as iniciadas em 42 e 69. São elas:
42: {0: 42, 1: 76, 2: 77, 3: 92, 4: 46, 5: 11, 6: 12, 7: 14, 8: 19, 9: 36, 10: 29, 11: 84, 12: 5, 13: 2, 14: 0}
69: {0: 69, 1: 76, 2: 77, 3: 92, 4: 46, 5: 11, 6: 12, 7: 14, 8: 19, 9: 36, 10: 29, 11: 84, 12: 5, 13: 2, 14: 0}