Hailstone sequence: Difference between revisions
Content added Content deleted
(New task and Python solution. (second time lucky)) |
(→Tcl: Added implementation (second time lucky)) |
||
Line 28: | Line 28: | ||
'''Sample Output''' |
'''Sample Output''' |
||
<pre>Maximum length 351 was found for hailstone(77031) for numbers <100,000</pre> |
<pre>Maximum length 351 was found for hailstone(77031) for numbers <100,000</pre> |
||
=={{header|Tcl}}== |
|||
<lang tcl>proc hailstone n { |
|||
while 1 { |
|||
lappend seq $n |
|||
if {$n == 1} {return $seq} |
|||
set n [expr {$n & 1 ? $n*3+1 : $n/2}] |
|||
} |
|||
} |
|||
set h27 [hailstone 27] |
|||
puts "h27 len=[llength $h27]" |
|||
puts "head4 = [lrange $h27 0 3]" |
|||
puts "tail4 = [lrange $h27 end-3 end]" |
|||
set maxlen [set max 0] |
|||
for {set i 1} {$i<100000} {incr i} { |
|||
set l [llength [hailstone $i]] |
|||
if {$l>$maxlen} {set maxlen $l;set max $i} |
|||
} |
|||
puts "max is $max, with length $maxlen"</lang> |
|||
Output: |
|||
<pre> |
|||
h27 len=112 |
|||
head4 = 27 82 41 124 |
|||
tail4 = 8 4 2 1 |
|||
max is 77031, with length 351 |
|||
</pre> |
Revision as of 00:55, 8 March 2010
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
The Hailstone sequence of numbers can be generated from a starting positive integer, n by:
- If n is 1 then the sequence ends.
- If n is even then the next n of the sequence
= n/2
- If n is odd then the next n of the sequence
= (3 * n) + 1
The (unproven), Collatz conjecture is that the hailstone sequence for any starting number always terminates.
The task is to:
- Create a routine to generate the hailstone sequence for a number.
- Use the routine to show that the hailstone sequence for the number 27 has 112 elements starting with
27, 82, 41, 124
and ending with8, 4, 2, 1
- Show the number less than 100,000 which has the longest hailstone sequence together with that sequences length.
(But don't show the actual sequence)!
Python
<lang python>def hailstone(n):
seq = [n] while n>1: n = 3*n + 1 if n & 1 else n//2 seq.append(n) return seq
if __name__ == '__main__':
h = hailstone(27) assert len(h)==112 and h[:4]==[27, 82, 41, 124] and h[-4:]==[8, 4, 2, 1] print("Maximum length %i was found for hailstone(%i) for numbers <100,000" % max((len(hailstone(i)), i) for i in range(1,100000)))</lang>
Sample Output
Maximum length 351 was found for hailstone(77031) for numbers <100,000
Tcl
<lang tcl>proc hailstone n {
while 1 {
lappend seq $n if {$n == 1} {return $seq} set n [expr {$n & 1 ? $n*3+1 : $n/2}]
}
}
set h27 [hailstone 27] puts "h27 len=[llength $h27]" puts "head4 = [lrange $h27 0 3]" puts "tail4 = [lrange $h27 end-3 end]"
set maxlen [set max 0] for {set i 1} {$i<100000} {incr i} {
set l [llength [hailstone $i]] if {$l>$maxlen} {set maxlen $l;set max $i}
} puts "max is $max, with length $maxlen"</lang> Output:
h27 len=112 head4 = 27 82 41 124 tail4 = 8 4 2 1 max is 77031, with length 351