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
