Hailstone sequence: Difference between revisions
add ABC
(→{{header|Python}}: Added a version with a generator function) |
Not a robot (talk | contribs) (add ABC) |
||
| (21 intermediate revisions by 12 users not shown) | |||
Line 275:
</pre>
=={{header|ABC}}==
<syntaxhighlight lang="abc">HOW TO RETURN hailstone n:
PUT {} IN seq
WHILE 1=1:
PUT n IN seq[#seq]
SELECT:
n=1: RETURN seq
n mod 2=0: PUT floor(n/2) IN n
n mod 2=1: PUT 3*n+1 IN n
RETURN seq
PUT hailstone 27 IN h27
WRITE "Length of Hailstone sequence for 27:", #h27/
WRITE "First 4 elements:", h27[0], h27[1], h27[2], h27[3]/
WRITE "Last 4 elements:", h27[#h27-4], h27[#h27-3], h27[#h27-2], h27[#h27-1]/
PUT 0, 0 IN longest, length
FOR n IN {1..100000}:
PUT hailstone n IN hn
IF #hn > length:
PUT n, #hn IN longest, length
WRITE longest, "has the longest hailstone sequence < 100,000, of length:", length/</syntaxhighlight>
{{out}}
<pre>Length of Hailstone sequence for 27: 112
First 4 elements: 27 82 41 124
Last 4 elements: 8 4 2 1
77031 has the longest hailstone sequence < 100,000, of length: 351</pre>
=={{header|ACL2}}==
<syntaxhighlight lang="lisp">(defun hailstone (len)
Line 767 ⟶ 795:
27: length 112, first: [27 82 41 124] last: [8 4 2 1]
Maximum sequence length: 351 for: 77031
</pre>
=={{header|Amazing Hopper}}==
<syntaxhighlight lang="c">
#include <basico.h>
#proto Hailstone(_X_,_SW_)
algoritmo
valor=27, máxima secuencia=0, vtemp=0
imprimir ( _Hailstone(27,1) ---copiar en 'máxima secuencia'--- , NL )
i=28
iterar
_Hailstone(i,0), copiar en 'vtemp'
cuando( sea mayor que 'máxima secuencia' ) {
máxima secuencia = vtemp
valor=i
}
++i
hasta que ' #(i==100000) '
imprimir ( #(utf8("Máxima longitud ")),máxima secuencia,\
" fue encontrada para Hailstone(",valor,\
#(utf8(") para números <100,000")), NL )
terminar
subrutinas
Hailstone(n, sw)
largo_de_secuencia = 0
v={}, n, mete(v)
iterar
tomar si ( es par(n), #(n/2), \
tomar si ( #(n<>1), #(3*n+1), 1) )
---copiar en 'n'--- mete(v)
hasta que ' #(n==1) '
#(length(v)), mover a 'largo_de_secuencia'
cuando (sw){
decimales '0'
#( v[1:4] ), ",...,",
#( v[largo_de_secuencia-4 : largo_de_secuencia] )
NL, #(utf8("Tamaño de la secuencia: "))
imprime esto; decimales normales
}
retornar ' largo_de_secuencia '
</syntaxhighlight>
{{out}}
<pre>
27,82,41,124,...,16,8,4,2,1
Tamaño de la secuencia: 112
Máxima longitud 351 fue encontrada para Hailstone(77031) para números <100,000
</pre>
Line 843 ⟶ 925:
set end of nums to n
end if
end repeat
return {|number(s) giving longest sequence length|:nums, |length of sequence|:longestLength}</syntaxhighlight>
{{output}}
Line 2,155 ⟶ 2,238:
Longest so far: 77031 @ 351 elements
Longest was starting from 77031 and was of length 351</pre>
=={{header|Bruijn}}==
<syntaxhighlight lang="bruijn">
:import std/Combinator .
:import std/List .
:import std/Math M
:import std/Number/Binary .
# hailstone sequence using binary shifts
hailstone y [[(0 =? (+1b)) {}0 go]]
go 0 : (=²?0 (1 /²0) (1 (↑¹0 + 0)))
# --- tests ---
seq-27 hailstone (+27b)
:test (∀seq-27) ((+112))
:test (take (+4) seq-27) ((+27b) : ((+82b) : ((+41b) : {}(+124b))))
:test (take (+4) <~>seq-27) ((+1b) : ((+2b) : ((+4b) : {}(+8b))))
below-100000 [0 : ∀(hailstone 0)] <$> seq
seq take (+99999) (iterate ++‣ (+1b))
main [head (max-by (M.compare ⋔ tail) below-100000)]
</syntaxhighlight>
=={{header|Burlesque}}==
Line 3,394 ⟶ 3,503:
true
number: 77031, length: 351</pre>
=={{header|EasyLang}}==
<syntaxhighlight lang=easylang>
proc hailstone n . list[] .
list[] = [ ]
while n <> 1
list[] &= n
if n mod 2 = 0
n = n / 2
else
n = 3 * n + 1
.
.
list[] &= 1
.
hailstone 27 l[]
write "27 has length " & len l[] & " with "
for i to 4
write l[i] & " "
.
write "... "
for i = len l[] - 3 to len l[]
write l[i] & " "
.
print ""
for i = 1 to 100000
hailstone i l[]
if len l[] >= max_iter
max_i = i
max_iter = len l[]
end
end
print max_i & " has length " & max_iter
</syntaxhighlight>
=={{header|EchoLisp}}==
Line 3,867 ⟶ 4,010:
=={{header|Elena}}==
ELENA
<syntaxhighlight lang="elena">import system'collections;
import extensions;
Line 3,906 ⟶ 4,049:
auto recursiveLengths := new Map<int,int>(4096,4096);
for(int i := 1
{
var chainLength := Hailstone(i, recursiveLengths);
Line 3,952 ⟶ 4,095:
Hailstone(27) has 112 elements: [27, 82, 41, 124, ..., 8, 4, 2, 1]
Longest sequence starting under 100000 begins with 77031 and has 351 elements.
</pre>
=={{header|EMal}}==
<syntaxhighlight lang="emal">
fun hailstone = List by int n
List h = int[n]
while n != 1
n = when((n % 2 == 0), n / 2, 3 * n + 1)
h.append(n)
end
return h
end
int NUMBER = 27
int LESS_THAN = 100000
List sequence = hailstone(NUMBER)
writeLine("The hailstone sequence for the number " + NUMBER +
" has " + sequence.length + " elements")
writeLine("starting with " +
sequence.extractStart(4).join(", ") + " and ending with " +
sequence.extractEnd(4).join(", ") + ".")
int number = 0
sequence = int[]
for int i = 1; i < LESS_THAN; ++i
List current = hailstone(i)
if current.length > sequence.length
sequence = current
number = i
end
end
writeLine("The number less than 100000 with longest hailstone sequence is " +
number + ", with length of " + sequence.length + ".")
</syntaxhighlight>
{{out}}
<pre>
The hailstone sequence for the number 27 has 112 elements
starting with 27, 82, 41, 124 and ending with 8, 4, 2, 1.
The number less than 100000 with longest hailstone sequence is 77031, with length of 351.
</pre>
Line 4,634 ⟶ 4,814:
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Collatz_conjecture}}
'''Part 1.''' Create a routine to generate the hailstone sequence for a number
[[File:Fōrmulæ - Collatz conjecture 01.png]]
'''Part 2.''' Use the routine to show that the hailstone sequence for the number 27 has 112 elements starting with {27, 82, 41, 124} and ending with {8, 4, 2, 1}
[[File:Fōrmulæ - Collatz conjecture 02.png]]
[[File:Fōrmulæ - Collatz conjecture 03.png]]
[[File:Fōrmulæ - Collatz conjecture 04.png]]
[[File:Fōrmulæ - Collatz conjecture 05.png]]
'''Part 3.''' Show the number less than 100,000 which has the longest hailstone sequence together with that sequence's length
[[File:Fōrmulæ - Collatz conjecture 06.png]]
[[File:Fōrmulæ - Collatz conjecture 07.png]]
The sequence for the number 77,031 is the longest one, with 351 terms
[[File:Fōrmulæ - Collatz conjecture 08.png]]
[[File:Fōrmulæ - Collatz conjecture 09.png]]
'''Part 4.''' (Additional, not a requirement) Show the number less than 100,000 which has the highest value in its hailstone sequence together with that highest value
[[File:Fōrmulæ - Collatz conjecture 10.png]]
[[File:Fōrmulæ - Collatz conjecture 11.png]]
The sequence for the number 77,671 has the highest term: 1,570,824,736
[[File:Fōrmulæ - Collatz conjecture 12.png]]
[[File:Fōrmulæ - Collatz conjecture 13.png]]
=={{header|GAP}}==
Line 5,821 ⟶ 6,035:
=={{header|Kotlin}}==
<syntaxhighlight lang="kotlin">
fun hailstone(start: Int) = generateSequence(start) { n ->
when {
n == 1 -> null
n % 2 == 0 -> n / 2
else -> n * 3 + 1
}
}
fun main() {
val hail27 = hailstone(27).toList()
println("The hailstone sequence for 27 has ${hail27.size} elements:\n$hail27")
val (n, length) = (1..100000).asSequence()
.map { it to hailstone(it).count() }
.maxBy { it.second }
println("The number between 1 and 100000 with the longest hailstone sequence is $n, of length $length")
}
</syntaxhighlight>
Alternative, doing it manually:
<syntaxhighlight lang="kotlin">import java.util.ArrayDeque
Line 6,543 ⟶ 6,780:
Thus we know that the correct sequences and values were generated
without bothering to print them out.
=={{header|MiniScript}}==
===Non-cached version===
Calculates sequence without using previous calculated sequences.
<syntaxhighlight lang="miniscript">
getSequence = function(n)
results = [n]
while n > 1
if n % 2 then
n = 3 * n + 1
else
n = n / 2
end if
results.push n
end while
return results
end function
h = getSequence(27)
print "The hailstone sequence for 27 has 112 elements starting with"
print h[:4]
print "and ending with"
print h[-4:]
maxSeqLen = 0
maxSeqVal = 0
for i in range(1,100000)
h = getSequence(i)
if h.len > maxSeqLen then
maxSeqLen = h.len
maxSeqVal = i
end if
end for
print
print "The number < 100,000 which has the longest hailstone sequence is " + maxSeqVal + "."
print "This sequence has " + maxSeqLen + " elements."
</syntaxhighlight>
{{out}}
<pre>The hailstone sequence for 27 has 112 elements starting with
[27, 82, 41, 124]
and ending with
[8, 4, 2, 1]
The number < 100,000 which has the longest hailstone sequence is 77031.
This sequence has 351 elements.</pre>
===Cached version===
Calculations are stored for used in later calculations.
<syntaxhighlight lang="miniscript">
cache = {}
calc = function(n)
if cache.hasIndex(n) then return
items = [n]
origNum = n
while n > 1 and not cache.hasIndex(n)
if n % 2 then
n = 3 * n + 1
else
n = n /2
end if
items.push n
end while
cache[origNum] = {"len": items.len,"items":items}
end function
getLen = function(n)
if not cache.hasIndex(n) then calc n
if n == 1 then return 1
return cache[n].len + getLen(cache[n].items[-1]) - 1
end function
getSequence = function(n)
if not cache.hasIndex(n) then calc n
if n == 1 then return [1]
return cache[n].items[:-1] + getSequence(cache[n].items[-1])
end function
h = getSequence(27)
print "The hailstone sequence for 27 has " + h.len + " elements starting with"
print h[:4]
print "and ending with"
print h[-4:]
longSeq = 0
longSeqVal =0
for i in range(2, 100000)
seq = getLen(i)
if longSeq < seq then
longSeq = seq
longSeqVal = i
end if
end for
print "The number < 100,000 which has the longest hailstone sequence is " + longSeqVal + "."
print "This sequence has " + longSeq + " elements."
</syntaxhighlight>
{{out}}Output is the same as the non-cached version above.
<pre>The hailstone sequence for 27 has 112 elements starting with
[27, 82, 41, 124]
and ending with
[8, 4, 2, 1]
The number < 100,000 which has the longest hailstone sequence is 77031.
This sequence has 351 elements.</pre>
=={{header|ML}}==
Line 7,009 ⟶ 7,351:
[351, 77031]
</pre>
=={{header|Onyx (wasm)}}==
<syntaxhighlight lang="C">
use core { * }
hailstone :: (n: u32) -> [..]u32 {
seq: [..]u32;
array.push(&seq, n);
while n > 1 {
n = n/2 if n%2 == 0 else (n*3)+1;
array.push(&seq, n);
}
return seq;
}
Longest :: struct { num, len : u32; }
main :: () {
// -------
// task 1:
// -------
// "Create a routine to generate the hailstone
// sequence for a number."
i := 27;
seq := hailstone(i);
printf("Task 1:\n{}: {}\n\n",
i,
seq
);
// -------
// task 2:
// -------
// "Use the routine to show that the hailstone
// sequence for the number 27 has
// 112 elements starting with
// 27, 82, 41, 124 and ending with 8, 4, 2, 1"
slice_size := 4;
len := seq.length;
slice_first := seq[0..slice_size];
slice_last := seq[seq.length-slice_size..seq.length];
printf("Task 2:\nlength: {}, first: {}, last: {}\n\n",
len,
slice_first,
slice_last
);
// -------
// task 3:
// -------
// "Show the number less than 100,000
// which has the longest hailstone sequence
// together with that sequences length."
l : Longest;
for i in 1..100000 {
seq := hailstone(i);
if l.len < seq.length { l = .{num = i, len = seq.length}; }
}
printf("Task 3:\nLongest Num: {}, Sequence Length: {}\n", l.num, l.len);
}
</syntaxhighlight>
=={{header|ooRexx}}==
Line 8,564 ⟶ 8,971:
<pre>the hail sequence of 27 has length 112 and has the form 27 82 41 ... 4 2 1
the number less than 100000 with the longest hail sequence is 77031 with length 351</pre>
=={{header|Refal}}==
<syntaxhighlight lang="refal">$ENTRY Go {
= <ShowHailstone 27>
<ShowLongest 100000>;
}
Hailstone {
1 = 1;
s.N, <Mod s.N 2>: {
0 = s.N <Hailstone <Div s.N 2>>;
1 = s.N <Hailstone <+ 1 <* 3 s.N>>>;
};
};
ShowHailstone {
s.N, <Hailstone s.N>: e.Seq,
<Lenw e.Seq>: s.Len s.1 s.2 s.3 s.4 e.X s.D4 s.D3 s.D2 s.D1
= <Prout 'The hailstone sequence for the number '
<Symb s.N> ' has ' <Symb s.Len> ' elements,\n'
'starting with ' s.1 s.2 s.3 s.4
'and ending with ' s.D4 s.D3 s.D2 <Symb s.D1>'.'>;
}
FindLongest {
s.Max = <FindLongest s.Max 1 1 1>;
s.Max s.Max s.Long s.Len = s.Long s.Len;
s.Max s.Cur s.Long s.Len,
<Hailstone s.Cur>: e.CurSeq,
<Lenw e.CurSeq>: s.CurLen e.X,
<+ s.Cur 1>: s.Next,
<Compare s.CurLen s.Len>: {
'+' = <FindLongest s.Max s.Next s.Cur s.CurLen>;
s.X = <FindLongest s.Max s.Next s.Long s.Len>;
};
};
ShowLongest {
s.Max, <FindLongest s.Max>: s.Long s.Len
= <Prout 'The number < ' <Symb s.Max> ' which has the longest'
' hailstone sequence is ' <Symb s.Long> '.\n'
'The length of its Hailstone sequence is '
<Symb s.Len> '.'>;
};</syntaxhighlight>
{{out}}
<pre>The hailstone sequence for the number 27 has 112 elements,
starting with 27 82 41 124 and ending with 8 4 2 1.
The number < 100000 which has the longest hailstone sequence is 77031.
The length of its Hailstone sequence is 351.</pre>
=={{header|REXX}}==
Line 9,237 ⟶ 9,693:
Maximum length 351 at number=77031
</pre>
=={{header|SETL}}==
<syntaxhighlight lang="setl">program hailstone_sequence;
hail27 := hailstone(27);
print("The hailstone sequence for the number 27 has", #hail27, "elements,");
print("starting with", hail27(..4), "and ending with", hail27(#hail27-3..));
sizes := [#hailstone(n) : n in [1..99999]];
maxsize := max/sizes;
maxelem := [n : n in [1..#sizes] | sizes(n) = maxsize](1);
print("The number < 100,000 with the longest hailstone sequence is",maxelem);
print("The length of its sequence is",sizes(maxelem));
proc hailstone(n);
seq := [];
loop doing seq with:= n; while n/=1 do
if even n then
n div:= 2;
else
n := 3*n + 1;
end if;
end loop;
return seq;
end proc;
end program;</syntaxhighlight>
{{out}}
<pre>The hailstone sequence for the number 27 has 112 elements,
starting with [27 82 41 124] and ending with [8 4 2 1]
The number < 100,000 with the longest hailstone sequence is 77031
The length of its sequence is 351</pre>
=={{header|Sidef}}==
Line 10,094 ⟶ 10,581:
=={{header|Wren}}==
<syntaxhighlight lang="
if (n < 1) Fiber.abort("Parameter must be a positive integer.")
var h = [n]
| |||