Search Results

Search found 11 results on 1 pages for 'collatz'.

Page 1/1 | 1 

• Code Golf: Collatz Conjecture

  - by Earlz

  Inspired by http://xkcd.com/710/ here is a code golf for it. The Challenge Given a positive integer greater than 0, print out the hailstone sequence for that number. The Hailstone Sequence See Wikipedia for more detail.. If the number is even, divide it by two. If the number is odd, triple it and add one. Repeat this with the number produced until it reaches 1. (if it continues after 1, it will go in an infinite loop of 1 -> 4 -> 2 -> 1...) Sometimes code is the best way to explain, so here is some from Wikipedia function collatz(n) show n if n > 1 if n is odd call collatz(3n + 1) else call collatz(n / 2) This code works, but I am adding on an extra challenge. The program must not be vulnerable to stack overflows. So it must either use iteration or tail recursion. Also, bonus points for if it can calculate big numbers and the language does not already have it implemented. (or if you reimplement big number support using fixed-length integers) Test case Number: 21 Results: 21 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1 Number: 3 Results: 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 Also, the code golf must include full user input and output.

  Read the article

• Project Euler Question 14 (Collatz Problem)

  - by paradox

  The following iterative sequence is defined for the set of positive integers: n -n/2 (n is even) n -3n + 1 (n is odd) Using the rule above and starting with 13, we generate the following sequence: 13 40 20 10 5 16 8 4 2 1 It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1. Which starting number, under one million, produces the longest chain? NOTE: Once the chain starts the terms are allowed to go above one million. I tried coding a solution to this in C using the bruteforce method. However, it seems that my program stalls when trying to calculate 113383. Please advise :) #include <stdio.h> #define LIMIT 1000000 int iteration(int value) { if(value%2==0) return (value/2); else return (3*value+1); } int count_iterations(int value) { int count=1; //printf("%d\n", value); while(value!=1) { value=iteration(value); //printf("%d\n", value); count++; } return count; } int main() { int iteration_count=0, max=0; int i,count; for (i=1; i<LIMIT; i++) { printf("Current iteration : %d\n", i); iteration_count=count_iterations(i); if (iteration_count>max) { max=iteration_count; count=i; } } //iteration_count=count_iterations(113383); printf("Count = %d\ni = %d\n",max,count); }

  Read the article

• The Collatz Sequence problem

  - by Gandalf StormCrow

  I'm trying to solve this problem, its not a homework question, its just code I'm submitting to uva.onlinejudge.org so I can learn better java trough examples. Here is the problem sample input : 3 100 34 100 75 250 27 2147483647 101 304 101 303 -1 -1 Here is simple output : Case 1: A = 3, limit = 100, number of terms = 8 Case 2: A = 34, limit = 100, number of terms = 14 Case 3: A = 75, limit = 250, number of terms = 3 Case 4: A = 27, limit = 2147483647, number of terms = 112 Case 5: A = 101, limit = 304, number of terms = 26 Case 6: A = 101, limit = 303, number of terms = 1 The thing is this has to execute within 3sec time interval otherwise your question won't be accepted as solution, here is with what I've come up so far, its working as it should just the execution time is not within 3 seconds, here is code : import java.util.Scanner; class Main { public static void main(String[] args) { Scanner stdin = new Scanner(System.in); int start; int limit; int terms; int a = 0; while (stdin.hasNext()) { start = stdin.nextInt(); limit = stdin.nextInt(); if (start > 0) { terms = getLength(start, limit); a++; } else { break; } System.out.println("Case "+a+": A = "+start+", limit = "+limit+", number of terms = "+terms); } } public static int getLength(int x, int y) { int length = 1; while (x != 1) { if (x <= y) { if ( x % 2 == 0) { x = x / 2; length++; }else{ x = x * 3 + 1; length++; } } else { length--; break; } } return length; } } And yes here is how its meant to be solved : An algorithm given by Lothar Collatz produces sequences of integers, and is described as follows: Step 1: Choose an arbitrary positive integer A as the first item in the sequence. Step 2: If A = 1 then stop. Step 3: If A is even, then replace A by A / 2 and go to step 2. Step 4: If A is odd, then replace A by 3 * A + 1 and go to step 2. And yes my question is how can I make it work inside 3 seconds time interval?

  Read the article

• Project Euler (P14): recursion problems

  - by sean mcdaid

  Hi I'm doing the Collatz sequence problem in project Euler (problem 14). My code works with numbers below 100000 but with numbers bigger I get stack over-flow error. Is there a way I can re-factor the code to use tail recursion, or prevent the stack overflow. The code is below: import java.util.*; public class v4 { // use a HashMap to store computed number, and chain size static HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>(); public static void main(String[] args) { hm.put(1, 1); final int CEILING_MAX=Integer.parseInt(args[0]); int len=1; int max_count=1; int max_seed=1; for(int i=2; i<CEILING_MAX; i++) { len = seqCount(i); if(len > max_count) { max_count = len; max_seed = i; } } System.out.println(max_seed+"\t"+max_count); } // find the size of the hailstone sequence for N public static int seqCount(int n) { if(hm.get(n) != null) { return hm.get(n); } if(n ==1) { return 1; } else { int length = 1 + seqCount(nextSeq(n)); hm.put(n, length); return length; } } // Find the next element in the sequence public static int nextSeq(int n) { if(n%2 == 0) { return n/2; } else { return n*3+1; } } }

  Read the article

• 3n+1 problem at UVa

  - by ShahradR

  Hello, I am having trouble with the first question in the Programming Challenges book by Skiena and Revilla. I keep getting a "Wrong Answer" error message, and I don't know why. I've ran my code against the sample input, and I keep getting the right answer. Anyways, if anyone could help me, I would really appreciate it :) Here is the problem URL: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=29&page=show_problem&problem=36 And here is the code:` import java.util.Scanner; public class Main { static Scanner kb = new Scanner(System.in); public static void main(String[] args) { while (kb.hasNext()) { long[] numericalInput = {0, 0}; long i = kb.nextLong(); long j = kb.nextLong(); if (i > j) { numericalInput[0] = i; numericalInput[1] = j; } else { numericalInput[0] = j; numericalInput[1] = i; } long maxIterations = 0; for (long n = numericalInput[0]; n <= numericalInput[1]; n += 1) { if (maxIterations < returnIterations(n)) maxIterations = returnIterations(n); } System.out.println(i + " " + j + " " + maxIterations); } System.exit(0); } public static long returnIterations(long num) { long iterations = 0; while (num != 1) { if (num % 2 == 0) num = num / 2; else num = 3 * num + 1; iterations += 1; } iterations += 1; return iterations; } } ` EDIT: I think the problem is with the output. I tried to make it accept all the input first and then display all the answers at once, but I didn't know the terminating condition. I resorted to this method, but I'm not sure that's what the judge wants...

  Read the article

• why is my 3n+1 problem solution wrong?

  - by nunos

  I have recently started reading "Programming Challenges" book by S. Skiena and believe or not I am kind of stuck in the very first problem. Here's a link to the problem: 3n+1 problem Here's my code: #include <iostream> #include <vector> #include <algorithm> using namespace std; unsigned long calc(unsigned long n); int main() { int i, j, a, b, m; vector<int> temp; while (true) { cin >> i >> j; if (cin.fail()) break; if (i < j) { a = i; b = j; } else { a = j; b = i; } temp.clear(); for (unsigned int k = a; k != b; k++) { temp.push_back(calc(k)); } m = *max_element(temp.begin(), temp.end()); cout << i << ' ' << j << ' ' << m << endl; } } unsigned long calc(unsigned long n) { unsigned long ret = 1; while (n != 1) { if (n % 2 == 0) n = n/2; else n = 3*n + 1; ret++; } return ret; } I know the code is inefficient and I should not be using vectors to store the data. Anyway, I still would like to know what it's wrong with this, since, for me, it makes perfect sense, even though I am getting WA (wrong answer at programming challenges judge and RE (Runtime Error) at UVa judge). Thanks.

  Read the article

• Why doesn't this loop terminate?

  - by David

  Here's the sample code: public static void col (int n) { if (n % 2 == 0) n = n/2 ; if (n % 2 != 0) n = ((n*3)+1) ; System.out.println (n) ; if (n != 1) col (n) ; } this works just fine until it gets down to 2. then it outputs 2 4 2 4 2 4 2 4 2 4 infinitely. it seems to me that if 2 is entered as n then (n % 2 == 0) is true 2 will be divided by 2 to yeild 1. then 1 will be printed and since (n != 1) is false the loop will terminate. Why doesn't this happen?

  Read the article

• Lazy Sequences that "Look Ahead" for Project Euler Problem 14

  - by ivar

  I'm trying to solve Project Euler Problem 14 in a lazy way. Unfortunately, I may be trying to do the impossible: create a lazy sequence that is both lazy, yet also somehow 'looks ahead' for values it hasn't computed yet. The non-lazy version I wrote to test correctness was: (defn chain-length [num] (loop [len 1 n num] (cond (= n 1) len (odd? n) (recur (inc len) (+ 1 (* 3 n))) true (recur (inc len) (/ n 2))))) Which works, but is really slow. Of course I could memoize that: (def memoized-chain (memoize (fn [n] (cond (= n 1) 1 (odd? n) (+ 1 (memoized-chain (+ 1 (* 3 n)))) true (+ 1 (memoized-chain (/ n 2))))))) However, what I really wanted to do was scratch my itch for understanding the limits of lazy sequences, and write a function like this: (def lazy-chain (letfn [(chain [n] (lazy-seq (cons (if (odd? n) (+ 1 (nth lazy-chain (dec (+ 1 (* 3 n))))) (+ 1 (nth lazy-chain (dec (/ n 2))))) (chain (+ n 1)))))] (chain 1))) Pulling elements from this will cause a stack overflow for n2, which is understandable if you think about why it needs to look 'into the future' at n=3 to know the value of the tenth element in the lazy list because (+ 1 (* 3 n)) = 10. Since lazy lists have much less overhead than memoization, I would like to know if this kind of thing is possible somehow via even more delayed evaluation or queuing?

  Read the article

• Uva's 3n+1 problem

  - by dmindreader

  I'm solving Uva's 3n+1 problem and I don't get why the judge is rejecting my answer. The time limit hasn't been exceeded and the all test cases I've tried have run correctly so far. import java.io.*; public class NewClass{ /** * @param args the command line arguments */ public static void main(String[] args) throws IOException { int maxCounter= 0; int input; int lowerBound; int upperBound; int counter; int numberOfCycles; int maxCycles= 0; int lowerInt; BufferedReader consoleInput = new BufferedReader(new InputStreamReader(System.in)); String line = consoleInput.readLine(); String [] splitted = line.split(" "); lowerBound = Integer.parseInt(splitted[0]); upperBound = Integer.parseInt(splitted[1]); int [] recentlyused = new int[1000001]; if (lowerBound > upperBound ) { int h = upperBound; upperBound = lowerBound; lowerBound = h; } lowerInt = lowerBound; while (lowerBound <= upperBound) { counter = lowerBound; numberOfCycles = 0; if (recentlyused[counter] == 0) { while ( counter != 1 ) { if (recentlyused[counter] != 0) { numberOfCycles = recentlyused[counter] + numberOfCycles; counter = 1; } else { if (counter % 2 == 0) { counter = counter /2; } else { counter = 3*counter + 1; } numberOfCycles++; } } } else { numberOfCycles = recentlyused[counter] + numberOfCycles; counter = 1; } recentlyused[lowerBound] = numberOfCycles; if (numberOfCycles > maxCycles) { maxCycles = numberOfCycles; } lowerBound++; } System.out.println(lowerInt +" "+ upperBound+ " "+ (maxCycles+1)); } }

  Read the article

• Project Euler 14: (Iron)Python

  - by Ben Griswold

  In my attempt to learn (Iron)Python out in the open, here’s my solution for Project Euler Problem 14.  As always, any feedback is welcome. # Euler 14 # http://projecteuler.net/index.php?section=problems&id=14 # The following iterative sequence is defined for the set # of positive integers: # n -> n/2 (n is even) # n -> 3n + 1 (n is odd) # Using the rule above and starting with 13, we generate # the following sequence: # 13 40 20 10 5 16 8 4 2 1 # It can be seen that this sequence (starting at 13 and # finishing at 1) contains 10 terms. Although it has not # been proved yet (Collatz Problem), it is thought that all # starting numbers finish at 1. Which starting number, # under one million, produces the longest chain? # NOTE: Once the chain starts the terms are allowed to go # above one million. import time start = time.time() def collatz_length(n): # 0 and 1 return self as length if n <= 1: return n length = 1 while (n != 1): if (n % 2 == 0): n /= 2 else: n = 3*n + 1 length += 1 return length starting_number, longest_chain = 1, 0 for x in xrange(1, 1000001): l = collatz_length(x) if l > longest_chain: starting_number, longest_chain = x, l print starting_number print longest_chain # Slow 31 seconds print "Elapsed Time:", (time.time() - start) * 1000, "millisecs" a=raw_input('Press return to continue')

  Read the article

• Project Euler Problem 14

  - by MarkPearl

  The Problem The following iterative sequence is defined for the set of positive integers: n n/2 (n is even) n 3n + 1 (n is odd) Using the rule above and starting with 13, we generate the following sequence: 13 40 20 10 5 16 8 4 2 1 It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1. Which starting number, under one million, produces the longest chain? NOTE: Once the chain starts the terms are allowed to go above one million. The Solution   public static long NextResultOdd(long n) { return (3 * n) + 1; } public static long NextResultEven(long n) { return n / 2; } public static long TraverseSequence(long n) { long x = n; long count = 1; while (x > 1) { if (x % 2 == 0) x = NextResultEven(x); else x = NextResultOdd(x); count++; } return count; } static void Main(string[] args) { long largest = 0; long pos = 0; for (long i = 1000000; i > 1; i--) { long temp = TraverseSequence(i); if (temp > largest) { largest = temp; pos = i; } } Console.WriteLine("{0} - {1}", pos, largest); Console.ReadLine(); }

  Read the article

1