How to resolve the algorithm Hailstone sequence step by step in the Picat programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Hailstone sequence step by step in the Picat programming language
Table of Contents
Problem Statement
The Hailstone sequence of numbers can be generated from a starting positive integer, n by:
The (unproven) Collatz conjecture is that the hailstone sequence for any starting number always terminates.
This sequence was named by Lothar Collatz in 1937 (or possibly in 1939), and is also known as (the):
The hailstone sequence is also known as hailstone numbers (because the values are usually subject to multiple descents and ascents like hailstones in a cloud).
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Hailstone sequence step by step in the Picat programming language
Source code in the picat programming language
import util.
go =>
println("H27:"),
H27 = hailstoneseq(27),
H27Len = H27.len,
println(len=H27.len),
println(take(H27,4)++['...']++drop(H27,H27Len-4)),
nl,
println("Longest sequence < 100_000:"),
longest_seq(99_999),
nl.
% The Hailstone value of a number
hailstone(N) = N // 2, N mod 2 == 0 => true.
hailstone(N) = 3*N+1, N mod 2 == 1 => true.
% Sequence for a number
hailstoneseq(N) = Seq =>
Seq := [N],
while (N > 1)
N := hailstone(N),
Seq := Seq ++ [N]
end.
%
% Use a map to cache the lengths.
% Here we don't care about the actual sequence.
%
longest_seq(Limit) =>
Lens = new_map(), % caching the lengths
MaxLen = 0,
MaxN = 1,
foreach(N in 1..Limit-1)
M = N,
CLen = 1,
while (M > 1)
if Lens.has_key(M) then
CLen := CLen + Lens.get(M) - 1,
M := 1
else
M := hailstone(M), % call the
CLen := CLen + 1
end
end,
Lens.put(N, CLen),
if CLen > MaxLen then
MaxLen := CLen,
MaxN := N
end
end,
println([maxLen=MaxLen, maxN=MaxN]),
nl.
go2 =>
time(max_chain(MaxN,MaxLen)),
printf("MaxN=%w,MaxLen=%w%n",MaxN,MaxLen).
table (-,max)
max_chain(N,Len) =>
between(2,99_999,N),
gen(N,Len).
table (+,-)
gen(1,Len) => Len=1.
gen(N,Len), N mod 2 == 0 =>
gen(N div 2,Len1),
Len=Len1+1.
gen(N,Len) =>
gen(3*N+1,Len1),
Len=Len1+1.
You may also check:How to resolve the algorithm Cantor set step by step in the Action! programming language
You may also check:How to resolve the algorithm Square-free integers step by step in the Perl programming language
You may also check:How to resolve the algorithm Read entire file step by step in the Quackery programming language
You may also check:How to resolve the algorithm Fivenum step by step in the Perl programming language
You may also check:How to resolve the algorithm Catamorphism step by step in the OCaml programming language