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.