For extra credit, prove that the sequence will terminate for any n. You should spend 5 minutes on this problem.
Name:
Anonymous2007-09-04 19:14 ID:8WJGrSko
(define (longest-sequence n)
(define length-seq
(memoize (lambda (x)
(cond ((= x 1) 0)
((even? x) (+ (length-seq (/ x 2)) 1))
(else (+ (length-seq (+ (* 3 x) 1)) 1))))))
(define (find-longest i start length)
(cond ((>= i n) (display `(longest sequence starts with ,start and has length ,length)))
((> (length-seq i) length) (find-longest (+ i 1) i (length-seq i)))
(else (find-longest (+ i 1) start length))))
(find-longest 1 0 0))
Name:
Anonymous2007-09-04 19:16 ID:ez68s2X/
tl;dr read sicp
Name:
Anonymous2007-09-04 19:40 ID:EZ4jcteU
I think the implication is that the sequence terminates when it starts to loop back to numbers it's already had.
For example 1 -> 4 -> 2 is a sequence (as then 2 -> 1 again)
Some interesting characteristics of this problem:
- if your sequence hits a power of two it will inevitably end up at 1, which then terminates the sequence
- an odd number is always followed by an even number ( 3n + 1 => odd * odd + odd = odd + odd = even )
Name:
Anonymous2007-09-05 3:56 ID:lmR0Mh+D
The answer is 837799 for one and 8400511 for ten million.
Name:
Anonymous2007-09-05 4:13 ID:rABwucbx
memo = {}
def seq(n):
m, i = n, 0
while m != 1:
if m in memo:
i += memo[m]
m = 1
else:
if m%2 == 0:
m /= 2
else:
m = 3*m+1
i += 1
memo[n] = i
return i
maximum, max_x = 0, None
for x in range(1, 10**6):
length = seq(x)
if length > maximum:
maximum, max_x = length, x
print max_x
Name:
Anonymous2007-09-05 5:19 ID:7QgTXC0R
1. you don't have to test a number if it's a member of a sequence you've already tested.
2. when a sequence reaches a power of two, the number of bits in the binary representation of that number plus the sequence 1, 4, 2, 1 is the number of terms left in the sequence.
3. A number which is two raised to an odd power can only appear at the start of a sequence, hence odd powers of two don't need to be tested since we can just set the initial known maximum sequence length to 24.
I think we'll all agree that these are all pretty trivial points, the thing that bothers me is that noone even tried to implement them (except 1).
>>24
Besides, considering the abundance of powers of two under one million, points #2 and #3 would be a massive waste of time, even if implementing them took only a few minutes. And they would needlessly clutter the code.
Name:
Anonymous2007-09-05 6:32 ID:N3V2WcCD
>>24
Your second point is incorrect. Power-of-two sequences, starting at 20:
I haven't written anything in Java for over five years, but I wanted to use the arbitrary precision integer library. I forgot how disgustingly verbose it is.
I assumed that the only cycle present is 1 -> 2 -> 4, and special cased those three starting positions to 3 (though I needn't have done so for 4). Everything else therefore must terminate at 1.
Well, here is the code anyway:
import java.math.BigInteger;
public class World4ChProgPuzzle {
private static int calculateSequenceLength(int start)
{
switch(start)
{
case 1:
case 2:
case 4:
return 3;
default:
{
int Length = 1;
BigInteger n = BigInteger.valueOf(start);
while (!n.equals(BigInteger.ONE))
{
if (n.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO))
{
n = n.divide(BigInteger.valueOf(2));
}
else
{
n = n.multiply(BigInteger.valueOf(3)).add(BigInteger.valueOf(1));
}
++Length;
}
return Length;
}
}
}
public static void main(String[] args)
{
int UpperLimit = 1000000;
int LongestSequenceLength = 0;
int CurrentSequenceLength;
>>36
Time-space tradeoff. If I cached the results of earlier calculations it would (often) be quicker to look them up rather than recalculate so many times. But as the bruteforce program took only a minute to run on my PC, I would surely be making unnecessary optimizations.
>>39
That hardly explains it. If we disable the memoization in the pythonfag's example, we get:
$ time python 23.py > /dev/null
real 2m40.108s
user 1m55.251s
sys 0m1.248s
Name:
Anonymous2007-09-05 9:17 ID:N3V2WcCD
>>40
I managed to get the Java one running 4.6% faster by precalculating the BigInteger values of 2 and 3 (it went from an average of 57.9s to 55.2s running time on my PC)
Apart from that, I don't know what else to check. Perhaps Python just has a more efficient arbitrary precision integer implementation than Sun's JVM.
Name:
Anonymous2007-09-05 9:38 ID:N3V2WcCD
I modified the above Python program to be equivalent to my Java one, and it has an average run time of 45.1s. Almost 20% faster - nice!
Average run time is 162.9 seconds (running on same PC as Python and Java measurements from earlier)
Am I doing it wrong, or is Ruby indeed slow as fuck?
This is the first Ruby program I've ever written, so maybe I'm missing some fundamentals.
Code below:
def sequencelength(n)
if n == 1 or n == 2 or n == 4
len = 3
else
len = 1
while n > 1
if n%2 == 0
n = n/2
else
n = 3*n + 1
end
len = len + 1
end
end
return len
end
longestseqlen = 0
starttime = Time.now()
for n in 1..1000000
curseqlen = sequencelength(n)
if curseqlen > longestseqlen
longestseqlen = curseqlen
end
end
print "longest sequence is ",longestseqlen,"\n"
print "run time is ",Time.now()-starttime,"s\n"
Ok that doesn't overflow on the brute force one with longs (and it takes 72.4 seconds), but it does cause Java to run out of heap pretty quickly on my Hashtable one. I can't seem to find the necessary combination of switches to give the JVM more memory to work in though.
Here's some more code (longs+hashtable):
import java.util.Hashtable;
public class World4ChProgPuzzleOpt2 {
static Hashtable<Long, Integer> LengthCache = new Hashtable<Long, Integer>();
private static int calculateSequenceLength(int start) {
switch(start) {
case 1:
case 2:
case 4:
return 3;
default:
{
int Length = 1;
Integer CachedLength = null;
long n = start;
while (!(n==1||CachedLength!=null)) {
CachedLength = LengthCache.get(n);
if (CachedLength != null) {
Length = Length + CachedLength - 1;
} else {
if (n%2==0) {
n /= 2;
} else {
n = 3*n+1;
}
++Length;
}
}
LengthCache.put((long)start, Length);
return Length;
}
}
}
public static void main(String[] args) {
int UpperLimit = 1000000;
int LongestSequenceLength = 0;
int CurrentSequenceLength;
long StartTime = System.currentTimeMillis();
for (int n=1; n<=UpperLimit; n++) {
CurrentSequenceLength = calculateSequenceLength(n);
if (CurrentSequenceLength > LongestSequenceLength) {
LongestSequenceLength = CurrentSequenceLength;
}
}
long ElapsedTime = System.currentTimeMillis()-StartTime;
System.out.println("Longest sequence for numbers up to " + UpperLimit + " is " + LongestSequenceLength);
System.out.println("(took "+ElapsedTime+"ms to run)");
I just realised how stupid I was using a hashtable. I mean, what the fuck? Completely retarded data structure for this application. This next one just allocates a huge array instead.
Average 0.34 seconds for one million items and 4.0 seconds for ten million. Here's the code:
public class World4ChProgPuzzleOpt3 {
static int[] LengthCache;
static final int UpperLimit = 1000000;
private static int calculateSequenceLength(int start) {
switch(start) {
case 1:
case 2:
case 4:
return 3;
default:
{
int Length = 1;
int CachedLength = 0;
long n = start;
while (!(n==1||CachedLength!=0)) {
if (n<=UpperLimit) {
CachedLength = LengthCache[(int)n-1];
}
if (CachedLength != 0) {
Length = Length + CachedLength - 1;
} else {
if (n%2==0) {
n /= 2;
} else {
n = 3*n+1;
}
++Length;
}
}
LengthCache[start-1] = Length;
return Length;
}
}
}
public static void main(String[] args) {
int LongestSequenceLength = 0;
int CurrentSequenceLength;
long StartTime = System.currentTimeMillis();
LengthCache = new int[UpperLimit];
for (int n=1; n<=UpperLimit; n++) {
CurrentSequenceLength = calculateSequenceLength(n);
if (CurrentSequenceLength > LongestSequenceLength) {
LongestSequenceLength = CurrentSequenceLength;
}
}
long ElapsedTime = System.currentTimeMillis()-StartTime;
System.out.println("Longest sequence for numbers up to " + UpperLimit + " is " +
LongestSequenceLength);
System.out.println("(took "+ElapsedTime+"ms to run)");