Hailstone sequence: Difference between revisions
→{{header|Picat}}
m (→{{header|Phix}}: added syntax colouring, marked p2js compatible) |
|||
Line 7,421:
Number < 100000 with longest Hailstone seq.: 77031 with length of 351
</pre>
=={{header|Picat}}==
<lang Picat>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.</lang>
Output:
<pre>H27:
len = 112
[27,82,41,124,...,8,4,2,1]
Longest sequence < 100_000:
[maxLen = 351,maxN = 77031]
</pre>
If we just want to get the length of the longest sequence - and are not forced to the same Hailstone function as for the H27 task - then this version using model directed tabling is faster than longest_seq/1: 0.055s vs 0.127s. (Original idea by Neng-Fa Zhou.)
<lang Picat>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.
</lang>
=={{header|PicoLisp}}==
| |||