The Collatz Conjecture is a conjecture that a certain algorithm always terminates. The algorithm is stated as follows: starting with some positive integer n, divide n by two if it is even and otherwise triple n and add one. The algorithm terminates when n reaches one. It is currently an open problem whether this terminates for all positive integers. It is also called the Hailstone Sequence.
Questions tagged [collatz]
284 questions
86
votes
70 answers
Code Golf: Collatz Conjecture
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,…
Earlz
- 62,085
- 98
- 303
- 499
38
votes
1 answer
Collatz Conjecture Python - Incorrect Output Above 2 Trillion (Only!)
I've written a basic script in Python3 that calculates the Collatz Conjecture. It takes a positive integer as an input and returns the number the steps until the sequence drops down to 1.
My script works perfectly for any integer inputs less than ~2…
ronster1000
- 570
- 4
- 13
19
votes
3 answers
Why is this simple haskell algorithm so slow?
Spoiler alert: this is related to Problem 14 from Project Euler.
The following code takes around 15s to run. I have a non-recursive Java solution that runs in 1s. I think I should be able to get this code much closer to that.
import…
Xavier Shay
- 4,067
- 1
- 30
- 54
14
votes
8 answers
Project Euler Question 14 (Collatz 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…
paradox
- 1,248
- 5
- 20
- 32
10
votes
1 answer
why is this memoized Euler14 implementation so much slower in Raku than Python?
I was recently playing with problem 14 of the Euler project: which number in the range 1..1_000_000 produces the longest Collatz sequence?
I'm aware of the issue of having to memoize to get reasonable times, and the following piece of Python code…
grobber
- 1,083
- 1
- 9
- 20
9
votes
1 answer
Collatz Conjecture related interview
This was an interview question, which seems related to Project Euler Problem 14
Collatz conjecture says that if you do the following
If n is even, replace n by n/2.
If n is odd, replace n by 3n+1.
You ultimately end up with 1.
For instance, 5 -> …
Anony
- 91
- 2
7
votes
3 answers
Lazy Sequences that "Look Ahead" for Project Euler Problem 14
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…
ivar
- 1,484
- 12
- 20
6
votes
2 answers
Why is tail recursive Collatz conjecture causing stack overflow in Scheme?
I've written Collatz conjecture in Scheme:
(define C
(lambda (n)
(cond
((eq? n 1) 1)
((even? n) (C (/ n 2)))
(else (C (+ (* n 3) 1))))))
This is a tail recursive call, yet I get stack overflow when I call (C 121):
guile> (trace…
Jan Stolarek
- 1,409
- 1
- 11
- 21
6
votes
0 answers
Why does this Python program run 3x faster than an identical Julia program
I wanted to try the Julia programming language, as I heard it is supposed to be faster than Python. I decided to try a dynamic program for Project Euler #14, as it dealt with a lot of computation (finding the longest Collatz sequence).
I wrote a…
Arya
- 1,382
- 2
- 15
- 36
6
votes
1 answer
collatz sequence - optimising code
As an additional question to an assignment, we were asked to find the 10 starting numbers (n) that produce the longest collatz sequence. (Where 0 < n < 10,000,000,000) I wrote code that would hopefully accomplish this, but I estimate that it would…
spyr03
- 864
- 1
- 8
- 27
6
votes
3 answers
Keeping a variable alive across multiple function calls in rust
I am trying to memoize a recursive collatz sequence function in rust, however I need the hashmap of memoized values to keep its contents across separate function calls. Is there an elegant way to do this in rust, or do I have to declare the hashmap…
picklebobdogflog
- 179
- 2
- 11
5
votes
1 answer
Numba jitting changes result when adding certain kind of 0 to local variable
Consider the following function for calculating the number of steps for a given input to the 3 n + 1 problem:
def num_steps(b, steps):
e = b
d = 0
while True:
if e == 1:
d += steps[e]
return d
if e…
fuglede
- 17,388
- 2
- 54
- 99
5
votes
8 answers
Implementing the collatz function using Python
I am currently having trouble completing this challenge in "Automate the boring stuff":
My code is:
def collatz(number):
global seqNum
if (seqNum % 2 == 0):
return seqNum // 2
elif (seqNum % 2 == 1):
return 3 * seqNum…
Xert01998
- 99
- 1
- 5
5
votes
8 answers
Project Euler (P14): recursion problems
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…
sean mcdaid
5
votes
2 answers
finding the lowest collatz sequence that gives more that 65 primes
I have a task where I need to find the lowest Collatz sequence that contains more than 65 prime numbers in Python.
For example, the Collatz sequence for 19 is:
19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8,
4, 2, 1
This…
spørreren
- 75
- 3