The winner is whoever names the number with

Programming
1

…the longest path that reaches 1 following the Collatz Conjecture.

This is an attempt to improve on the last post, where an approach was quite quickly found to maximize the number (just a high power of 2). This time we’ve got a challenge which I think is more interesting and hopefully not as easy to exploit.

For the unaware, the Collatz Conjecture works as follows:

def collatz(n):
  while n != 1:
    if n % 2 == 0: # If even, divide by 2
      n /= 2
    else:          # If odd, multiply by 3 and add 1
      n = 3 * n + 1

The actual conjecture is that any positive integer will eventually end up at 1 following those steps.

There are, of course, a few actual requirements to keep this reasonable and interesting:

  • Numbers have to be fully written in the reply and 24 characters or less. The format of the number is up to you, as long as others can reasonably be expected to understand it without additional explanation. This means writing something like “10^10000” or “The 127th prime” or “27*6+123456789/3” are allowed, assuming the other rules are followed.

  • The path cannot have more than 99% of the steps be even ones. Under 1 million, only 19 starting values have paths with more than 99% even steps and I’m sure you can guess which those are.

  • You have to run a program to verify the number reaches 1 in the reported number of steps

  • Path length will include both the starting value and the first time it reaches 1. This means staring with 3 would give you a path of [3, 10, 5, 16, 8, 4, 2, 1] which has a length of 8 (This is also my first submitted value to start us off)

The rules are subject to change if I’ve once again missed an easy workaround or somehow made things too hard.

Since people are going to find workarounds whatever I do, I’m going to make a column specifically marking the ones that felt like they were intentionally doing that (The “Workaround Mark”). You can take it as a badge of honor or a mark of shame. They still need to follow the rules either way, so keep that in mind.

I may as well make a submission here to start things off again, so I’m submitting a starting value of 69^420 which has a path length of 19,214 and about 66.48% even steps.

The Leaderboard

Placement Path Length Starting Value Poster Peer Reviewed Workaround Mark
:1st_place_medal: 2,057,797,126,475 (2^2^32 - 1) * 4^10^12 Gii2000
:2nd_place_medal: 514,448,571,769 (2^2^30-1)<<(5*10^11) ShayHi :white_check_mark:
:3rd_place_medal: 48,189,251,001 2^46843576932*(2^10^8-1) Gii2000 :white_check_mark:
4th 7,639,603,701 2^7410423559*3^20000000 Gii2000 :white_check_mark:
5th 1,276,807,624 8^9^9*3^10^7 Kuggo :white_check_mark:
6th 177,725,668 10 ^ 10,000,000 Gii2000 :white_check_mark:
7th 126,888,562 2^(10^8)*(2^(2*10^6)-1) FoxNerdSaysMoo :white_check_mark:
8th 35,634,191 2^34680486+2^34526886 FEARLESS_Z :white_check_mark:
9th 17,805,058 10^1000000 Imated :white_check_mark:
10th 120,353 10^4000-1 Amelium :white_check_mark:
11th 39,596 6969^420 Imated :white_check_mark:
12th 19,214 69^420 Amelium :white_check_mark:

I’ll update this section with any submissions that I feel meet all the rules. I encourage verifying other replies and stating that you’ve done so to keep us all more confident in the leaderboard. Submissions which have been verified by at least one other person will get the “Peer Reviewed” check mark.

3 Likes
2

6969^420: 39,596 total path length

3

I have verified it :+1:

1 Like
4

10^4000-1 got 120,353 :smiling_face_with_sunglasses:

5

10^1000000: 17,805,058 total path length
beat that noobs

6

2^34529286+2^34526886
35,596,000 iterations with exactly 99% of the steps being even

7

Updated the leaderboard accordingly

8

34,526,886 is the number of even steps when factoring out the giant power of 2, leaving us with 2^2400 + 1 which has another 16,983 steps. No matter what happens on those remaining steps, it’s not enough to outweigh the prior even ones. The path is well over 99% even steps.

If anyone else wants to do their own verification lmk, I wanna make sure we’ve got this correct.

9 
➜  Test ./collatz                     
k = 2^100000000 * (2^2000000 - 1)
Total length of Collatz sequence for 2^100000000 * 3^2000000 is 126888562
Percent of even steps is 92.41%
Time taken: 271.31 seconds

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>
#include <gmp.h>

typedef struct {
    unsigned long long even_steps;
    unsigned long long odd_steps;
} CollatzResult;

CollatzResult collatz(mpz_t n) {
    CollatzResult result = {0, 0};
    mpz_t temp;
    mpz_init(temp);
    
    mpz_t one;
    mpz_init_set_ui(one, 1);
    
    while (mpz_cmp(n, one) != 0) {
        if (mpz_even_p(n)) {
            // divide by the largest power of 2 at once
            unsigned long trailing_zeros = mpz_scan1(n, 0);
            
            // divide by 2^trailing_zeros
            mpz_fdiv_q_2exp(n, n, trailing_zeros);
            result.even_steps += trailing_zeros;
        } else {
            // n = 3 * n + 1
            mpz_mul_ui(temp, n, 3);
            mpz_add_ui(n, temp, 1);
            result.odd_steps++;
        }
    }
    
    mpz_clear(temp);
    mpz_clear(one);
    
    return result;
}

int main() {
    unsigned long j = 100000000;
    
    clock_t start_time, end_time;
    double cpu_time_used;
    
    mpz_t k, two;
    mpz_init(k);
    mpz_init(two);
    
    mpz_set_ui(two, 2);
    
    printf("k = 2^%lu * (2^%lu - 1)\n", j, j / 50);
    mpz_pow_ui(k, two, j);
    
    mpz_t temp;
    mpz_init(temp);
    mpz_pow_ui(temp, two, j / 50);
    mpz_sub_ui(temp, temp, 1);
    mpz_mul(k, k, temp);
    mpz_clear(temp);
    
    start_time = clock();
    CollatzResult result = collatz(k);
    end_time = clock();
    
    cpu_time_used = ((double) (end_time - start_time)) / CLOCKS_PER_SEC;
    
    unsigned long long total_steps = result.even_steps + result.odd_steps;
    double percent_even = 100.0 * (double)result.even_steps / (double)total_steps;
    
    printf("Total length of Collatz sequence for 2^%lu * 3^%lu is %llu\n", 
           j, j / 50, total_steps);
    printf("Percent of even steps is %.2f%%\n", percent_even);
    printf("Time taken: %.2f seconds\n", cpu_time_used);
    
    mpz_clear(k);
    mpz_clear(two);
    
    return 0;
}

To compile it, run gcc -o collatz collatz.c -lgmp.

1 Like
10 
➜  Test ./collatz                     
k = 2^1000000000 * (2^2500000 - 1)
Total length of Collatz sequence for 2^1000000000 * 3^2500000 is 1033678055
Percent of even steps is 98.83%
Time taken: 426.03 seconds
11

oh i did a dumb. forgot to multiply the 2400 by 64

2^34680486+2^34526886 or 2^34526886*(1+2^153600)

with this you get 34526886 even steps and then 1+2^153600 which has 713154 even and 355960 odd steps for a total of 35240040 even and 355960 odd which is exactly 99% even.

12 
const SIZE: usize = 4800;
fn main() {

    let mut num: [usize; SIZE] = [0; SIZE];

    num[0] = 1;
    num[2399] = 0x8000000000000000;

    let mut count = 0;
    let mut div_count = 0;
    let mut mult_count = 0;
    
    while !done(&num) {
        if (num[0] & 0x1) == 0x0 {
            divide_by_2(&mut num);
            div_count += 1;
        }
        else {
            times_3_plus_1(&mut num);
            mult_count += 1;
        }
        count += 1;
        
    }

    println!("steps:{count}\neven:{div_count}\nodd:{mult_count}");
}

fn divide_by_2(num: &mut [usize; SIZE]) {

    let mut carry = false;

    // starts at the top and shifts right by 1
    for byte in num.iter_mut().rev() {

        // temp carry down value
        let temp = (*byte & 0x1) == 1;

        // update value based on prev carry
        *byte = (*byte >> 1) | if carry {0x8000000000000000} else {0x0};

        // update carry
        carry = temp;
    }
}

fn times_3_plus_1(num: &mut [usize; SIZE]) {

    let mut x2: usize; // temp times 2 value

    let mut shift_carry = false;
    let mut add_carry = false;

    // calculates both the x2 and adds it to the number for x3
    for (i, byte) in num.iter_mut().enumerate() {

        // temp shift carry for x2
        let temp = (*byte & 0x8000000000000000) == 1;

        // calculates the x2 based on prev carry and adds 1 if first value
        x2 = (*byte << 1) | if shift_carry {0x1} else {0x0} + if i == 0 {0x1} else {0x0};

        // calculates x3 by adding num and x2
        let add = (x2 as u128) + (*byte as u128) + if add_carry {1} else {0};
        
        // updates the number
        *byte = add as usize;

        // update shift and add carries
        shift_carry = temp;
        add_carry = add > usize::max_value() as u128;
    }
}

fn done(num: &[usize; SIZE]) -> bool {
    for byte in num.iter().skip(1) {
        if *byte != 0x0 {
            return false;
        }
    }
    return num[0] == 0x1;
}

this is my shitty rust code

13

I did 10 ^ 10,000,000, and a few hours later, my program have found its length to be 177,725,668 with an even ratio of 68.55%. I was also able to verify that 10^1,000,000 has a path length of 17,805,058.

14

Alright lemme go through the ones I haven’t reviewed yet

15

Updated

16

I decided to give this a try and i got very good results (should take first place):
i used: 8^9^9*3^10^7 (short form as exponent is right associative) or 8^(9^9) * 3^(10^7)
It takes 1_276_807_623 iterations (± 1), with a even ratio of: 0.97%
I programmed it in rust using rug and runtime was of 5454 secs

(i say ±1 because i double checked imated’s and i got 1 less so maybe my code counts it differently. i say that the path to 1 from 4 takes 2 iterations)

17

As specified in the post, the path starting at 3 is considered to be 8 long [3, 10, 5, 16, 8, 4, 2, 1] since we count including both the starting value and 1.

18

Updated. I included the margin of error for Kuggo’s but would appreciate knowing which specific value it is based on my previous reply. I assume it’s the value +1 but I don’t want to get it wrong.

19

Figured out how to put icons in the table, would y’all be interested in that as the format for the full table? I only did my own for now. Also it still can show text when you hover, so I’d set that to be the actual usernames.

20

in that case the correct amount is 1_276_807_624 which is +1 of what i said earlier. I corrected my code so now it aligns with everyone else’s :+1:

1 Like