Hailstone sequence: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: added syntax colouring, marked p2js compatible) |
|||
Line 7,421: | Line 7,421: | ||
Number < 100000 with longest Hailstone seq.: 77031 with length of 351 |
Number < 100000 with longest Hailstone seq.: 77031 with length of 351 |
||
</pre> |
</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}}== |
=={{header|PicoLisp}}== |