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