The following iterative sequence is defined for the set of positive integers:
$n \to n/2$ ($n$ is even)
$n \to 3n + 1$ ($n$ is odd)
Using the rule above and starting with $13$, we generate the following sequence: $$13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1.$$
It can be seen that this sequence (starting at $13$ and finishing at $1$) contains $10$ terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at $1$.
Which starting number, under one million, produces the longest chain?
NOTE: Once the chain starts the terms are allowed to go above one million.
Potremmo semplicemente scorrere sui numeri da uno a un milione, usare questa funzione per generare la sequenza di numeri prodotti, e guardare il numero che produce quella più lunga.
function simple_collatz(n; verbose=false)
steps = 1
if verbose println("(step=$steps) $n") end
while true
if iseven(n)
n = div(n,2)
else
n = 3n+1
end
steps += 1
if verbose println("(step=$steps) $n") end
if n==1
break
end
end
return steps
end
simple_collatz(50, verbose=true)
max_len = 1
max_idx = 1
@time for i in 1:1_000_000
cur_len = simple_collatz(i)
if cur_len > max_len
global max_len = cur_len
global max_idx = i
end
end
@show max_len, max_idx
Questo metodo in effetti funziona, ma diventerebbe molto lento se il limite fosse ben più alto di un milione. In tal caso, l'idea sarebbe di passare ad una versione ricorsiva: per calcolare la lunghezza della sequenza generata, ad esempio, da 50, consideriamo \(1 + \) la lunghezza della sequenza generata dal numero a cui conduce 50, ovvero 25. Se questo valore ci è già noto lo usiamo, altrimenti lo calcoliamo e ce lo salviamo (se c'è una cella disponibile per lui nell'array di appoggio, altrimenti lo calcoliamo al volo e basta) in modo che sarà eventualmente utile al calcolo della lunghezza delle sequenze generate dai numeri successivi.
function collatz(n, lens; verbose=false)
if n <= length(lens) && lens[n] != 0
if verbose println(" lui ci conduce a $n che sappiamo già produrre una sequenza lunga $(lens[n])") end
return lens[n]
end
if verbose println("Incontriamo $n per la prima volta, continuiamo con la ricorsione") end
nextn = iseven(n) ? div(n,2) : 3n+1
val = 1 + collatz(nextn, lens; verbose=verbose)
if n <= length(lens)
lens[n] = val
end
return val
end
collatz (generic function with 1 method)
Esempio didattico:
lens = zeros(Int, 20)
lens[1] = 1
for i in 2:20
collatz(i, lens; verbose=true)
end
Incontriamo 2 per la prima volta, continuiamo con la ricorsione
lui ci conduce a 1 che sappiamo già produrre una sequenza lunga 1
Incontriamo 3 per la prima volta, continuiamo con la ricorsione
Incontriamo 10 per la prima volta, continuiamo con la ricorsione
Incontriamo 5 per la prima volta, continuiamo con la ricorsione
Incontriamo 16 per la prima volta, continuiamo con la ricorsione
Incontriamo 8 per la prima volta, continuiamo con la ricorsione
Incontriamo 4 per la prima volta, continuiamo con la ricorsione
lui ci conduce a 2 che sappiamo già produrre una sequenza lunga 2
lui ci conduce a 4 che sappiamo già produrre una sequenza lunga 3
lui ci conduce a 5 che sappiamo già produrre una sequenza lunga 6
Incontriamo 6 per la prima volta, continuiamo con la ricorsione
lui ci conduce a 3 che sappiamo già produrre una sequenza lunga 8
Incontriamo 7 per la prima volta, continuiamo con la ricorsione
Incontriamo 22 per la prima volta, continuiamo con la ricorsione
Incontriamo 11 per la prima volta, continuiamo con la ricorsione
Incontriamo 34 per la prima volta, continuiamo con la ricorsione
Incontriamo 17 per la prima volta, continuiamo con la ricorsione
Incontriamo 52 per la prima volta, continuiamo con la ricorsione
Incontriamo 26 per la prima volta, continuiamo con la ricorsione
Incontriamo 13 per la prima volta, continuiamo con la ricorsione
Incontriamo 40 per la prima volta, continuiamo con la ricorsione
Incontriamo 20 per la prima volta, continuiamo con la ricorsione
lui ci conduce a 10 che sappiamo già produrre una sequenza lunga 7
lui ci conduce a 8 che sappiamo già produrre una sequenza lunga 4
Incontriamo 9 per la prima volta, continuiamo con la ricorsione
Incontriamo 28 per la prima volta, continuiamo con la ricorsione
Incontriamo 14 per la prima volta, continuiamo con la ricorsione
lui ci conduce a 7 che sappiamo già produrre una sequenza lunga 17
lui ci conduce a 10 che sappiamo già produrre una sequenza lunga 7
lui ci conduce a 11 che sappiamo già produrre una sequenza lunga 15
Incontriamo 12 per la prima volta, continuiamo con la ricorsione
lui ci conduce a 6 che sappiamo già produrre una sequenza lunga 9
lui ci conduce a 13 che sappiamo già produrre una sequenza lunga 10
lui ci conduce a 14 che sappiamo già produrre una sequenza lunga 18
Incontriamo 15 per la prima volta, continuiamo con la ricorsione
Incontriamo 46 per la prima volta, continuiamo con la ricorsione
Incontriamo 23 per la prima volta, continuiamo con la ricorsione
Incontriamo 70 per la prima volta, continuiamo con la ricorsione
Incontriamo 35 per la prima volta, continuiamo con la ricorsione
Incontriamo 106 per la prima volta, continuiamo con la ricorsione
Incontriamo 53 per la prima volta, continuiamo con la ricorsione
Incontriamo 160 per la prima volta, continuiamo con la ricorsione
Incontriamo 80 per la prima volta, continuiamo con la ricorsione
Incontriamo 40 per la prima volta, continuiamo con la ricorsione
lui ci conduce a 20 che sappiamo già produrre una sequenza lunga 8
lui ci conduce a 16 che sappiamo già produrre una sequenza lunga 5
lui ci conduce a 17 che sappiamo già produrre una sequenza lunga 13
Incontriamo 18 per la prima volta, continuiamo con la ricorsione
lui ci conduce a 9 che sappiamo già produrre una sequenza lunga 20
Incontriamo 19 per la prima volta, continuiamo con la ricorsione
Incontriamo 58 per la prima volta, continuiamo con la ricorsione
Incontriamo 29 per la prima volta, continuiamo con la ricorsione
Incontriamo 88 per la prima volta, continuiamo con la ricorsione
Incontriamo 44 per la prima volta, continuiamo con la ricorsione
Incontriamo 22 per la prima volta, continuiamo con la ricorsione
lui ci conduce a 11 che sappiamo già produrre una sequenza lunga 15
lui ci conduce a 20 che sappiamo già produrre una sequenza lunga 8
Vera soluzione:
lens = zeros(Int, 1_000_000)
lens[1] = 1
@time for i in 2:1_000_000
collatz(i, lens)
end
0.052356 seconds (1.00 M allocations: 15.278 MiB, 6.70% compilation time)
risp = findmax(lens)
@show risp
risp = (525, 837799)
println("La catena più lunga parte da n=$(risp[2]) ed è lunga $(risp[1])")
La catena più lunga parte da n=837799 ed è lunga 525
