A faster and leaner version, exploiting the fact
that the sequence length for 2*k is 1 + the
sequence length for k :
cnv1=: 3 : 0
f=. 2^ m=. i.<.@(2&^.)&.<:y
C=. _1 ,~ (1+m) f} y{._1 1
j=. i=. I. (0=}:C)*.2|i.y
k=. 1
while. #i do.
j=. collatzv j
b=. 0<(j<.y){C
p=. , f */ b#i
q=. , m +/ k+(b#j){C
i=. (-.b)#i
j=. (-.b)#j
b=. y>p
C=. (b#q) (b#p)}C
k=. >:k
end.
}:C
)
(cnv -: cnv1) 1e6
1
ts 'cnv 1e6'
5.32365 7.23556e7
ts 'cnv1 1e6'
3.72328 5.13844e7
----- Original Message -----
From: Roger Hui <[EMAIL PROTECTED]>
Date: Saturday, February 3, 2007 3:03 pm
Subject: Re: [Jprogramming] Collatz Problem again
> A vector approach: For the basic iteration,
> instead of
> collatz=: -:`(>:@(3&*))`1: @. (1&= + 2&|)
> use
> collatzv=: 3 : '<. (2|y)} 0 1 + 0.5 3 */y'
>
> The latter version requires y>1.
>
> collatz"0 y=: 2+i.20
> 1 10 2 16 3 22 4 28 5 34 6 40 7 46 8 52 9 58 10 64
> collatzv y
> 1 10 2 16 3 22 4 28 5 34 6 40 7 46 8 52 9 58 10 64
>
> Then the cn routine
>
> cn=: 3 : 0
> C=. y{._1 1
> for_i. i.y do.
> if. 0=i{C do.
> b=. y>j=. collatz^:(i&<:)^:a: i
> C=. ((b#i.-#j)+(_1{j){C) (b#j)}C
> end.
> end.
> )
>
> can be replaced by:
>
> cnv=: 3 : 0
> C=. _1 ,~ (1+i.m) (2^i.m=. <.2^.y)} y{._1 1
> j=. i=. 0 I.@:= C
> k=. 1
> while. #i do.
> j=. collatzv j
> b=. 0<(j<.y){C
> C=. (k+(b#j){C) (b#i)}C
> i=. (-.b)#i
> j=. (-.b)#j
> k=. >:k
> end.
> }: C
> )
>
> (cn -: cnv) 1e4
> 1
> ts 'cn 1e4'
> 0.214307 147264
> ts 'cnv 1e4'
> 0.0321217 1.13434e6
>
> ts 'cn 1e6'
> 21.535 8.41882e6
> ts 'cnv 1e6'
> 5.30616 7.23556e7
>
> Thus, cnv is faster than cn but uses more space.
>
>
>
> ----- Original Message -----
> From: June Kim <[EMAIL PROTECTED]>
> Date: Saturday, February 3, 2007 7:39 am
> Subject: [Jprogramming] Collatz Problem again
>
> > Have a look at this problem:
> > http://www.programming-
> > challenges.com/pg.php?page=downloadproblem&probid=110101&format=html
> > In short, you need to calculate the maximum cycle length in a
> > given range.
> >
> > Roger wrote an essay which is related to this problem.
> > http://www.jsoftware.com/jwiki/Essays/Collatz_Conjecture
> >
> > Suppose we want to calculate the maximum cycle length of collatz
> > sequences for 1, ..., 1e6.
> >
> > It would be defined, using Roger's definition, as >./ cn 1e6
> >
> > It currently takes around 40 secs on the computer I'm using.
> Could you
> > improve its efficiency?
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
